Introduction Binary search is one of the most popular searching algorithms in computer science. If you know the binary search algorithm already, you may have come across a section in this algorithm where you try to find the middle element in the array (or search space to be more precise). Note : It is important to note that this overflow error is not limited to binary search alone. It applies all algorithms that have a similar use case for getting middle element. A very basic implementation of binary search uses the below formula for calculating the middle element: mid = (left + right)/2 where left and right represent the indexes of the first and the last element in the current search space. A first glance on this basic formula for middle index calculation, everything looks correct and in fact the formula works perfectly fine for most cases, until you start noticing that your algorithm is producing an unexpected output (or even error in some programming languages) for some specific values of input. The reason for this unexpected failure may not be fairly obvious at first. It occurs due to a hidden flaw in this seemingly straight forward formula for middle index calculation. At the root, the reason for this failure is something called an overflow condition in computer programming. Basic Formula: Overflow Explained Why does the above basic formula to calculate middle value result in an overflow? The max value an integer (data type in a programming language) can hold can vary from machine to machine, OS to OS or even based on the programming language itself. For the sake of our example and for easier understanding, assume this value, lets call it MAX_INT , is 100. Consider we are given an array with n=90 elements and our target element is the last element in the array, at 89th index. Binary search algorithm starts with left=0 and right=89. Since the target element is the last element in the array our search space keeps shifting to the right (refer binary search for more details). So (left,right) will be (0,89) for the first iteration and (45,89) for the second iteration. Now using our basic formula to calculate mid value for the first iteration, we get mid = (0+89)/2 = 45, for the second iteration, mid = (45 + 89), but (45 + 89) exceeds our MAX_INT value of 100 resulting in overflow. Thus our program might produce some unexpected output or result in an error depending on the programming language we are using. This is how the basic formula for middle element calculation fails. Also note that, generally the MAX_INT will be much higher, we assumed it as 100 just for the ease of understanding. Optimized Formula Now that we know why the overflow occurs when we use the basic formula, lets see how it can be prevented using the optimized formula mid=left + (right - left)/2 . Mathematically both the equations (one used in basic formula and the other in optimized formula) are same and they produce the same output, i.e. left + (right - left)/2 = (left + right)/2 . We can prove this as shown below. Lets say, left + (right - left)/2 = x Multiplying 2 on both sides of the equation we get: 2 * left + (right - left) = 2 * x Simplifying the equation will result in: left + right = 2 * x which implies x = (left + right)/2 Therefore we can say that, left + (right - left)/2 = (left + right)/2 which means both equations will produce the same output for all values of left and right. Now that we know both equations are same, lets see why left + (right - left)/2 does not result in an overflow as compared to (left + right)/2 . Remember left and right represent indexes of the leftmost and rightmost element in our search space. To prevent overflow we have to ensure that, the value of the equation left + (right - left)/2 equating to mid (which is also an index), Does not exceed the max integer value. Also that the value isn't negative. Lets see how the equation left + (right - left)/2 ensures the above two conditions are met. As a matter of fact we know that left , right >= 0 and right is always greater than or equal to left for all cases for the given input array. Thus we can safely say that, (right-left) >= 0 for all values of right and left. Therefore it is safe to say (right - left)/2 in equation left + (right - left)/2 cannot be negative, and hence the optimized equation left + (right - left)/2 cannot be negative. Therefore we have taken care of the lower bound (first condition). Now coming to the second condition, for the given input array, by definition (left,right) <= MAX_INT value. So (right - left) will result in a value smaller than MAX_INT always. And therefore, (right - left)/2 is also smaller than MAX_INT. Mathematically, if you add left to this value i.e. left + (right - left)/2, it can't exceed MAX_INT. So the new equation satisfies the second condition as well. Therefore the equation mid = left + (right-left)/2 doesn't result in an overflow. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Summary Binary search is a fairly simple algorithm. But it has a few subtleties, one of which we have tried to address in this article. At first glance this might seem like a simple and straightforward thing to be even missed. However such things when missed, even though they seem minor, can really come to bite you at a later point. There are many variations of binary search and caveats associated with it. We will try to cover them in our upcoming articles. Until then stay tuned! That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section . Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time. Join now . Follow us on social media: Facebook , Twitter , Linkedin , Tumblr , Instagram .

Algorithm Linear search is one of the simplest searching algorithms . Linear search finds the target element by sequentially checking every element in the given input array. This is why linear search is sometimes also referred to as sequential search. Linear search works on both sorted and unsorted arrays. For an input array arr and a target element lets say x, linear search does the following steps: Iterate through the input array from start to end (or end to start, traversal order does not matter). In each iteration compare the current element to the target element x . If current element is equal to the target element x, you have found the element you are looking for. Stop the iteration and return the current element index as result. If current element is not equal to x , continue to the next element and repeat the above steps until you find the target element or you have reached the end of the array. If the target element x is not found then return -1 as the result indicating the target value is not present in the given array. Working Consider the given input array is [3, 7, 1, 5, 11] and the target element x=1 as shown below: Lets say i is our index variable. Linear search algorithm starts by checking the element at index 0, as shown in the below diagram. Now the algorithm checks whether the current element arr[0] is equal the target element x. Clearly arr[0] is not equal to the target element x. So, the algorithm continues to the next element at index i=1 as shown below: Again arr[1] is also not equal to the target element x. So our algorithm continues to the element at next index i=2. Now the element at index 2, arr[2]=1. This is nothing but the target element we are looking for which means we have found our answer. So the algorithm returns 2 as the result indicating that the target element x is found at index 2 in the given array [3, 7, 1, 5, 11]. Implementation Language: Go Complexity Analysis Time Complexity : O(n) Time complexity of linear search algorithm is O(n). In the worst case our algorithm would end up comparing every element in the given input array to the target element x. The worst case occurs if the target element is the last element in the input array or the target element itself is not present in the array. Space Complexity : O(1) The algorithm doesn't use any extra space. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Applications Linear search is mostly used in cases where the size of the given input array is small. When the size of the array is large it is preferable to use other search algorithms like binary search which has a better time complexity than linear search. Unlike some other search algorithms like binary search, jump search, exponential search etc. which work only on sorted arrays, linear search works on both sorted and unsorted arrays. So linear search could be useful in this case. It is also important to note that for cases where the input array is not sorted, it might make sense to sort the array first and then search using faster algorithms like binary search. But if it is a frequently changing list, sorting every time and then sorting using binary search might not be worth it. Output You can test your code using the below code snippet: Language: Go Below is the result of test execution: That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section . Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time. Join now . Follow us on social media: Facebook , Twitter , Linkedin , Tumblr , Instagram .

Problem Statement ​ Design a video streaming service like Netflix, Amazon Prime, Youtube. For your Netflix system design you can assume our platform needs to support a total 1 billion users, with 500 million being daily active users. Functional Requirements Our platform should allow users to upload videos. Users should be able to watch videos on our platform. Users should be able to search for videos. User should be able to see likes/dislikes, view count for videos. Non-Functional Requirements High availability. Our system should be reliable (We should make sure uploaded videos are not lost). Low latency (Users should not experience lag while watching videos). Consistency is important, but not at the cost of availability. It's okay if one user sees a video little later than the other user. Netflix System Design ​

In our previous article we learnt what a singly linked list is and how to implement it in various languages. In this article we will see how to find the middle element or middle node in a singly linked list. Note: Same approach can be used to find the middle element in a doubly linked list as well. Problem Statement Given a singly linked list, find the middle element in it. If there are even number of nodes in the given linked list then return the ceil value node as the middle element. E.g. if there are 6 nodes in the given linked list, then node 4 should be considered as the middle node. Examples Example 1: Input : 1 -> 2 -> 3 -> 4 -> 5 Output : 3 Example 2: Input : 2 -> 4 -> 6 -> 8 -> 10 -> 12 Output : 8 Solution 1: Counting Nodes This method works on the idea of counting the total no. of nodes in the given linked list and using this information to find out which is the middle element. This algorithm involves the following steps: Traverse all the nodes in the given linked list starting from the head node. Take a variable to keep track of the count of total nodes traversed. Lets call this variable nodeCount . Once you have the count of total nodes in a linked list, you can get the middle node using middleNode = nodeCount /2. Now traverse the linked list again from the head node until middleNode . To do this take a variable currentNodeCount to keep track of the current node count. As you visit each node, increment this counter by 1. When currentNodeCount is equal to middleNode we have reached the middle node, return the middle node. Implementation Note: For linked list, node class/struct definitions please refer our singly linked list article . Language: Go Language: Java Complexity Analysis Time Complexity: O(n) Since we make 2 passes (one full pass and one pass till the middle node) on the given linked list, time complexity is O(n) + O(n/2) which in general can be represented as O(n). Space Complexity: O(1) No extra space is used. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Solution 2: Two Pointer Technique As you might have noticed in solution 1 , we have to traverse the given linked list twice in order to find the middle node, first to count the total number of nodes and then till the middle element to return the result. This problem can be solved more efficiently using the two pointer technique. In this method we have to traverse the list just once to arrive at the result. This approach works on the idea that, when we move the two pointers, one pointer twice as fast as the other, by the time the fast pointer reaches the end of the list, the slow pointer would have moved till the middle of the list. This algorithm involves the following steps: Take two pointers variables, lets call them fast and slow . Initially both fast and slow points to the head node of the given linked list. slow pointer moves one step at a time and fast pointer moves two steps at a time. We need to move the fast and slow pointers from the head node until the fast pointer reaches end of the list. When the fast pointer reaches the last node, slow pointer would have reached the middle node since it is moving at half the pace as the fast pointer. So when the fast pointer reaches the last node, return the slow pointer node as your result. Lets understand this with an example. Consider you are given the below linked list: We point the slow and fast pointers initially to the head node as shown in figure below: Now, in each iteration we move the slow pointer one step at a time and fast pointer two steps at a time until fast pointer reaches the last node. Same is shown in the below diagrams. Iteration 1 Iteration 2 Once the fast pointer reaches the last node (node 5 in this case) we return the slow pointer which is currently pointing to the middle node (node 3 in this case) as the result. Implementation Language: Go Language: Java Complexity Analysis Time Complexity: O(n) Time complexity is O(n) since we need to make one pass on the given linked list. Space Complexity: O(1) No extra space is used. Now you know how to find middle element in a singly linked list. Do not stop here, deepen your knowledge by exploring more articles on linked lists . That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe here . Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time : Join now Follow us on social media: Facebook , Twitter , Linkedin , Tumblr , Instagram .

In our previous article we learnt how to find the middle node in a singly linked list. In this article we will discuss how to reverse a given singly linked list. Problem Statement Write an algorithm to reverse the given singly linked list. Examples Example 1: Input : 1 -> 2 -> 3 -> 4 -> 5 Output : 5 -> 4 -> 3 -> 2 -> 1 Example 2: Input : 2 -> 4 -> 6 Output : 6 -> 4 -> 2 Prerequisites Fundamental understanding of singly linked lists . Solution 1: Using Stack We can use the properties of a stack data structure to reverse a given linked list. Problems involving reversing something (strings, series of characters, numbers, lists etc), can mostly be solved using stacks. Stack is a last in first out (LIFO) data structure. We push and pop elements from the top of stack. We can use this to our advantage to reverse the given list. Notice: We will soon publish a detailed article on stack data structure. The idea is to first push all the nodes of the given linked list into the stack, then pop them one by one and reconnect the nodes thereby reversing the list. The intuition behind this approach is based on the fact that the list nodes that are pushed into stack (from start to end) when popped out will be in reverse order. For a given linked list this algorithm does the following steps: Traverse the given singly linked list starting from the head node. As we visit each node, we add it to the top of stack. We need to do this for all the nodes in the list. Once all the nodes are added to stack, pop them one be one. Make the first node to be popped from stack as the head of linked list (this is the last node in the original list). For all the other popped nodes, connect the next pointer of previously popped node to the current popped node. Lets understand this with an example. Consider you are given the below linked list: Lets take a stack to store these nodes. Initially the stack is empty as shown below: Traverse the linked list starting from the head node and add them to stack. So we begin by adding node 1 to stack. Next we move our current pointer to node 2, add node 2 to stack. Finally we add node 3 to stack. Now that all the linked list nodes are added to stack, we need to pop them one by one from stack. First we pop node 3 from stack. Since node 3 is the first node to be popped, we make it the head node of the linked list. Next we pop node 2 from stack. Also we need to connect the next of previously popped node, node 3, to the current node, node 2. Finally we pop node 1 from stack and connect the next of node 2 to node 1. As you can see, we have successfully reversed the given linked list using stack. Implementation Language: Go Stack Implementation Complexity Analysis Time Complexity: O(n) In this approach we need to visit each node in the list twice to reverse it (once to add it to the stack, and again to pop it from stack). So, the time complexity is O(n) + O(n) = 2 * O(n) which in general can be represented as O(n). Space Complexity: O(n) Space complexity is also O(n) since we store each node in stack. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Solution 2: Flipping the next pointer Solution 1 reverses the list in O(n) time but it also needs O(n) space because we use stack to store nodes. Also we need to visit each node twice. This problem can be efficiently solved by simply flipping the next pointer of each node (to point to the previous node). For a given linked list, this algorithm does the following steps: Take 3 pointer variables: current , previous and next each of which point to the current, previous and next nodes respectively. Initially current points to the head node and previous points to null. In each iteration, point next to current.next , and connect current.next to previous which flips the next pointer of the current node. After that move the next and previous pointers ahead by one node. Repeat this for all the nodes in the list. Finally make the last node as the new head of the list. Let us understand this with an example. Consider you are given the below linked list: Iteration 1 To begin with current points to head node and previous points to null as shown in the figure below: Now flip the next pointer of the current node by first pointing next to current.next and then pointing current.next to previous. Node 1 is now completely processed, so move the current and previous pointers ahead by one step. Iteration 2 Now node 2 is the current node. Process node 2 similar to node 1 to flip its next pointer. Move the current and previous pointer to the next node. Iteration 3 Finally process node 3 in the same way by pointing next to current.next, current.next to previous. Since node 3 is the last node in our list, we stop our algorithm here. Also one final thing we need to do is to make the last node as our new head as shown in figure below: Implementation Language: Go Language: Java Complexity Analysis Time Complexity: O(n) In this algorithm we need to visit each node in the given linked list only once. So time complexity is O(n). Space Complexity: O(1) No extra space is used. Now you know how to reverse a singly linked list. Do not stop here, deepen your knowledge by exploring more articles on linked lists . That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe here . Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time : Join now Follow us on social media: Facebook , Twitter , Linkedin , Tumblr , Instagram .

This is another article in the series leetcode problem solutions . In this article we will be solving leetcode problem 13   Roman to Integer . Problem Statement Convert the given roman numeral into an integer value. Roman numerals are represented using seven different symbols as shown below: Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, in Roman numerals: 1 is written as I. 2 is written as II i.e. by adding two "ones" I+I together. 12 is written as XII which is X + II. Number 27 is XXVII, which is XX + V + II. Roman numerals are usually written from largest to smallest from left to right. However, there are certain exceptions to this rule, for example, 4 is not written as IIII, instead it is IV. This is written by subtracting one from five (i.e. V - I). Similarly 9 is written as IX i.e. X - I. There are six such instances where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9.  X can be placed before L (50) and C (100) to make 40 and 90.  C can be placed before D (500) and M (1000) to make 400 and 900. Note: For a quick recap of roman numerals you can refer this article. Constraints: 1 <= s.length <= 15 s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M'). It is guaranteed  that s is a valid roman numeral in the range [1, 3999]. Examples Example 1: Input:  s = "III" Output:  3 Explanation:  III = 3. Example 2: Input:  s = "LVIII" Output:  58 Explanation:  L = 50, V= 5, III = 3. Example 3: Input:  s = "MCMXCIV" Output:  1994 Explanation:  M = 1000, CM = 900, XC = 90 and IV = 4.   Solution So, how can we approach the problem statement? Our objective here is to convert the given roman numeral to an equivalent integer value. If you observe carefully, you can see that we can get the required result by simply adding up all the roman numerals in the input. For example, if s="LVIII" is the given input, its equivalent integer value is 58, which can get by adding all roman numerals in the given input, i.e. result = L + V + I + I + I = 50 + 5 + 1 + 1 + 1 = 58. Similarly if CCLXXXIII is the input, the result would be, result = C + C + L + X + X + X + I + I + I = 100 + 100 + 50 + 10 + 10 + 10 + 1 + 1 + 1 = 283. But (It cannot be that simple! There is always a "but" isn't it 😉 ), as stated in the problem statement, there are exceptions, we cannot always get the required result simply by adding up all the roman literals in the given input all the time. For instance if s="CDXCVII" is the input, the correct result is 497, but if we do result = C + D + X + C + V + I + I, we get 100 + 500 + 10 + 100 + 5 + 1 + 1=717, which obviously is not the correct answer. The correct result should be (-C + D - X + C + V + I + I) = 497. So, how can we detect and handle such scenarios in our code where we have to subtract some values in order to get the needed output? Again, if you analyze the given input, for all cases where we have to do "addition only" to get the result, the adjacent numerals in the input are in decreasing order from left to right. If we consider our previous example again of s="LVIII", if we scan the input from left to right: L >= V >= I >= I >= I Similarly, for input s="CCLXXXIII", C >= C >= L >= X >= X >= X >= I >= I >= I Now, if you check the same for inputs where we have to do subtraction, you can see that it does not follow this decreasing order rule. For example, in case of s="CDXCVII", C < D and X < C. And you will observe a similar trend if you take any other input involving subtraction. So, what is the conclusion? From all the above observations, we can conclude that, if s="[N1][N2][N3]...."as we read adjacent values in the given input from left to right, as long as the left numeral >= right numeral, we add the left numeral to result, otherwise we subtract it from the result. We have to repeat this procedure for all the roman numerals in input to get the final result. Algorithm With the understanding that we have so far, we can use the sliding window algorithm to solve this problem. For any input s our algorithm needs to do the following set of steps: First, take a variable to store our result, lets name this variable as result . Traverse the given input s from left to right and compare each adjacent roman numerals. During comparison, If N1 >= N2, add N1 to result. If N1 < N2, subtract N1 from result. Move the window to the next set of adjacent numerals N2 and N3 and repeat step 3. Once all the numerals in s are compared, result will have the final answer, return result . To make it easier for you to understand, let me explain this algorithm with the help of an example. Example 1 Consider s="LVIII" which is the roman numeral for 58. First step is to create a result variable. Initially result =0. First we compare L and V as shown in below diagram. L > V (50 > 5), therefore we add L i.e. 50 to the result . Next we move our window ahead by one and compare V and I. V > I, hence we add V or 5 to the result . Now result = 50 +5 = 55. Again we move window ahead and compare I and I. I is equal to I, so we I to result . result = 55+1=56. We again move the window and compare the remaining 2 numerals, Since I is equal to I we add 1 again to the result making result =57. Finally we add the last remaining I to the result . Now result = 57 + 1 = 58 which is the required answer, so we return it as the final result. Example 2 Lets now take an example involving subtraction, s="DXCIX" which is 599. First we create variable result =0. Next we compare D and X. D > X, therefore we add D to result . result = 0 + 500=500 Next we compare X and C. X < C, therefore we subtract X from result . result = 500 - 10 = 490 Next we compare C and I. C > I, add C to result . result = 490 + 100 = 590 Next compare I and X. I < X, subtract I from result . result = 590 - 1 = 589 Finally add the remaining X to the result . result = 589 + 10 = 599, which is the required result . Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python 3 Solution Java Solution JavaScript Solution C++ Solution C Solution Complexity Analysis Time Complexity: O(n) Since we iterate the given string s only once to get the result, if n is the length of s, the time complexity of this algorithm is O(n). Space Complexity: O(1) This algorithm uses a HashMap to store roman numerals. But since this is a fixed value (7 roman numerals) the space complexity is O(7) or in general we can say O(1). That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website and YouTube channel , your support motivates us to bring out more such articles in future. You can explore more such amazing articles from code recipe in our blogs section . Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us on social media: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

In our last article we solved Roman to Integer problem. Today let's discuss another leetcode problem Integer to Roman . Problem Statement Convert the given integer to a roman numeral. As we saw in our previous article, roman numerals are represented using seven different symbols as shown below: Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, in Roman numerals: 1 is written as I. 2 is written as II i.e. by adding two "ones" I+I together. 12 is written as XII which is X + II. Number 27 is XXVII, which is XX + V + II. Roman numerals are usually written from largest to smallest from left to right. However, there are certain exceptions to this rule, for example, 4 is not written as IIII, instead it is IV. This is written by subtracting 1 from 5 (i.e. V - I). Similarly, 9 is written as IX i.e. X - I. There are six such instances in roman numerals where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9.  X can be placed before L (50) and C (100) to make 40 and 90.  C can be placed before D (500) and M (1000) to make 400 and 900. Note:  For a quick recap of roman numerals you can refer this  article. Constraints: 1 <= num <= 3999 Examples Example 1: Input:  num = 3 Output:  "III" Explanation:  3 is represented as 3 ones. Example 2: Input:  num = 58 Output:  "LVIII" Explanation:  L = 50, V = 5, III = 3. Example 3: Input:  num = 1994 Output:  "MCMXCIV" Explanation:  M = 1000, CM = 900, XC = 90 and IV = 4. Solution To solve this problem, we need to first extend the given roman to integer table to include all the exceptional cases. We also need to arrange the values in this table in decreasing order (we will see why this is needed in more detail later in this article). With these changes our new table would look like this: 1000 M 900 CM 500 D 400 CD 100 C 90 XC 50 L 40 XL 10 X 9 IX 5 V 4 IV 1 1 Now with the modified table in place let's see how we can convert a given integer value to roman numeral. next to map the given integer to roman numeral we break the given integer first and then map it to the respective roman numeral. We can break any given integer by dividing it with appropriate values. For example, if 153 is the given integer, the corresponding roman value is CLIII. To get this, we first break 153 into 3 parts: 100, 50 and 3. Next, we map each of these parts into roman values i.e. 100 is mapped to C, 50 is mapped to L and 3 is mapped to III, which in turn gives us CLIII. Similarly, if 2024 is the given integer we break it into 2000, 20 and 4. This in roman numerals is MM, XX and IV respectively or MMXXIV. I hope you get an idea of how we need to approach this problem statement. Now let's see how we can translate this logic into code. Below algorithm shows how we can do this through code. Algorithm Create a list/array to store the extended integer to roman mapping, let call it intToRomanList . Store the integer to roman mapping in this list in decreasing order. Create a variable, let's say result to store the final result. Next, we traverse intToRomanList from start to end, and in each iteration, we perform the following steps: Divide the given number with the integer from intToRomanList . This will give us the no. of times we have to append the roman numeral. Example, if num =2000, if we divide it with M or 1000 from intToRomanList we get 2000/1000 = 2. This 2 is an indication that we need to append two M's i.e. MM in order to make a 2000. We will store this in a variable called count . Now, only if count is greater than 0 we need to append the corresponding roman numeral to the result variable. Example, if num =500, for intToRomanList values M:1000, count = ( num / intToRomanList integer) = 500/1000 = 0, Therefore, we need not append it to the result variable. In the next iteration, intToRomanList key:value is 500:D, so, count = ( num / intToRomanList  integer) = 500/500 = 1, Now count is greater than 0, therefore we need to add it to result . After this we mod num with intToRomanList integer value to process its remaining part. Repeat a-c until we reach the end of intToRomanList . Finally return the value in result variable. I know this is a bit confusing 😁. To make it easier let me explain it with the help of an example. Let's say num =2024. First step is to create a list, lets create a list and name it intToRomanList . We will fill the list with the following key value pairs/values: {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} Let's also declare a variable result and initialize it to "". Next traverse intToRomanList  starting from the first pair 1000:M. { 1000:M , 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} Now, divide num with the current intToRomanList integer value i.e. 1000. This will give us the count (i.e. no. of times we need to append the current roman numeral to result). count = ( num / intToRomanList  integer) = (2024/1000) = 2 This indicates that we need to add the current roman numeral in intToRomanList which is M, twice to result . Therefore, we append result with MM. Now result =MM. Since 1000th place is now processed, we need to remove it from num , so mod it with 1000: num = num % 1000 = 2024 % 1000 = 24 After this we move to the next pair in intToRomanList 900:CM. {1000:M, 900:CM , 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} Repeat the previous steps again: count  = ( num / intToRomanList  integer) = (24/900) = 0 Now since count =0, no need to append anything to result . num  = num  % 900 = 24 % 900 = 24 Again, we move ahead in intToRomanList by one: {1000:M, 900:CM, 500:D , 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} We follow the same procedure again: count  = 24/500 = 0, hence result remains unchanged and, num = 24 % 500 = 24. In the same way count , result and num remain unchanged for 400:CD, 100:C, 90:XC, 50:L, 40:XL . So, let's skip to 10:X . {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X , 9:IX, 5:V, 4:IV, 1:I} Now, count  = 24/10 = 2, therefore result = "MM" + "XX"= "MMXX" num  = 24 % 10 = 4. For 9:IX and 5:V again count , result  and num remain unchanged. Now when our iteration reaches 4:IV , {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV , 1:I} count  = 4/4 = 1, therefore result = "MMXX" + "IV"= "MMXXIV" num  = 4 % 4 = 0. We stop the iteration, after we process the last element in rMap 1:I and return whatever is present in result as the final result. Want to master coding? Looking to learn new skills and crack interviews? We recommend you explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution C Solution C++ Solution C# Solution Complexity Analysis Time Complexity: O(1) In this algorithm we iterate over a list of size 13, which does not depend on the input size of num . Inside the loop, it performs division and modulus operations, which are constant time operations. The code where we append to result also runs in constant time because the maximum possible value of count is limited and does not have any considerable impact on time complexity. Therefore, regardless of the value of num , the number of operations is bounded by a constant, leading to a time complexity of O(1). Space Complexity: O(1) The space complexity is also O(1) since the algorithm uses a fixed size list for its computation. That brings us to the end of this article. We sincerely appreciate the time you've taken to read through it. If there are any questions or doubts, don't hesitate to voice them in the comments section below. We're here to assist you and will be more than happy to provide answers. If you found value in this article, we encourage you to subscribe to both our website and YouTube channel . Your support fuels our motivation to continue producing more insightful articles like this one in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello coders! Today, let's solve yet another leetcode problem, Longest Common Prefix . This is an article in our series leetcode problem solutions , so make sure to check out other leetcode problem solutions in this series, after you finish this one 😉. Problem Statement Find the longest common prefix from the given array of strings. Return an empty string "", if no common prefix is found. Example 1: Input:  strs = ["preview","prepare","prevent"] Output:  "pre" Example 2: Input:  strs = ["pan","can","dog"] Output:  "" Explanation:  There is no common prefix among the input strings. Constraints: 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] consists of only lowercase English letters. Solution This is marked as an easy problem on leetcode, and it is indeed an easy solution except for a couple of edge cases that we have to cover. Here we are asked to find the longest common prefix from the given array of strings. A prefix is a continuous sequence of letters at the beginning of the string. For instance, for string "leetcode" these are the possible prefixes: "l" "le" "lee" "leet" "leetc" and so on. We need to find the common prefix that is longest among all the strings in the given string array. For example, if strs = ["can", "cant", "candy"], the longest common prefix here is "can". Similarly for strs = ["bad", "bat", "bank"], the longest common prefix is "ba". This problem can be easily solved using a O(m*n) solution. In this solution, we compare each character in the first string with the corresponding characters in all the others strings in the given string array. If all corresponding characters match we continue checking. We stop checking and return the result as soon as a mismatch is found. Algorithm Here is how the algorithm works: Create two for loops. Outer loop iterates through the characters in the first string in the array. Inner loop iterates through the characters in all the others strings in the array. In each iteration, we check if each character in the first string matches the corresponding characters in all the others strings in the array. If they match, continue iterating. If there is a mismatch in any of the strings, stop the iteration and return the prefix up to which there was a match as the result. Simulation Lets understand this algorithm with an example. Consider strs=["flower", "flow", "flight"]. The expected result here is "fl" which is the longest common prefix among the three strings in the input array. Lets see how our algorithm works to arrive at the result. The algorithm uses two for loops. Outer loop is used to keep track of the letter in the strings we compare. Inner loop keeps track of the strings in the array. i is the outer loop index and it runs from 1st letter in the 1st string till the last letter (Index 0 to n-1. Where n is the length of the first string). j is the in inner loop index and it runs from 2nd string in the array till the last string (Index 1 to m-1. Where m is the length of the array). Initially we start i =0 and j =1, which means that we will be comparing the first letter in the first string i.e. "f" with the first letter in the 2nd string "f". As you can see the first letters of both strings match, so we increment j by 1. Now i =0 and j =2. Again the first letters in both these strings match. Now, we have reached the end of the array, and the first characters in all the strings match. Therefore, we can consider it for our result. So, our current result="f". We now move to the next iteration of the outer loop i =1 and j =1. Again, the 2nd characters of first and second strings match, so increment j by 1. Now i =1 and j =2. As you see from above diagram, the second letters of all strings in the array match, hence we add it to our result. We perform similar steps in the third iteration of the outer loop i =2 and j =1. Again as seen in above diagram 3rd characters of 1st and second strings match. So, we move to i =2 and j =2. Now if you observe, 3rd character of first string is "o", but the 3rd character of third string is "i". Clearly they do not match, which means that the 3rd character is not same in all strings in the given input array, hence it cannot be part of our result. At this point we need to stop the algorithm and return "fl" as the result. One edge that we need to cover here for other examples is if i goes out of bounds in either strings that we are comparing. In such cases we need to stop the iteration and return the matched prefix so far as result. We can detect such cases using the condition i>=length(strs[j]) as shown in code below. Want to master coding? Looking to learn new skills and crack interviews? We recommend you explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Complexity Analysis Time Complexity In this algorithm, we iterate through the characters in the first string and compare it with the corresponding characters in the rest of the strings. So, if m is the length of the first string and n is the total number of strings in the array, in the worst case outer loop runs m times and inner loop runs (n-1) times. So the worst case time complexity of this solution is O(m*n) . Space Complexity The space complexity is O(1) because the algorithm does not use any extra space. That brings us to the end of this article. We sincerely appreciate the time you've taken to read through it. If there are any questions or doubts, don't hesitate to voice them in the comments section below. We're here to assist you and will be more than happy to provide answers. If you found value in this article, we encourage you to subscribe to both our website and YouTube channel . Your support fuels our motivation to continue producing more insightful articles like this one in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Introduction Linked list is a linear data structure. Each element in a linked list is an individual object. These individual objects are called nodes. As the name suggests a linked list is formed by interconnecting a series of such nodes. Nodes are connected using pointers. Each node internally contains data and a link to the next node (address of the next node). In general a node in a linked list appears as shown in figure below: The first node in a linked list is called a head node . The head node is the entry point to a linked list. Unlike arrays linked list elements are not indexed, we cannot access any random element using an index like arrays. We always start traversing the linked list from the head node no matter which element we need to access in the list. The last node in a linked list is not connected to any node. The next pointer of the last node always points to null. Linked list can contain any type of data like int, string, character etc. Elements can all be unique or it can also contain duplicates. Also the elements in a linked list can be sorted or unsorted. Unlike arrays elements in a linked list are not stored in contiguous locations in memory. Each node is stored in arbitrary location in memory and connected to each other using next pointer. Why Linked List? Arrays are fixed size structures. Once an array is declared you cannot change its size. If the array is full and a new element needs to be added, you need to declare a new array (of larger size) and copy all the elements from the old array into the new array. This can be an expensive operation especially for large arrays. Linked list unlike arrays are dynamic in nature, they do not have a fixed size. We just a have to create a new node and link it to our list each time a new element needs to be added. Another scenario where a linked list is useful is when you do not know the size of input beforehand, declaring a large array to accommodate such an input is a waste of memory. For such use cases linked list is useful because you need not specify the size while declaring a linked lists. Linked lists (especially doubly linked list) are often used because of their efficient insert and delete operations. Linked list allows you to efficiently add a new node between existing nodes in a list. This cannot be efficiently done in case of arrays. If a new element is to be added in between existing elements in arrays, you need to shift all the other elements to make space for the new element. Linked List Drawbacks Unlike arrays linked lists do not support indexing. To find nth element in a linked list we have the traverse the list from first node till nth node. Linked lists use comparatively more space than arrays since each node needs to store a link to the next or previous node in addition to storing the actual data. Arrays have a good locality of reference since the elements are stored in contiguous location in memory. But linked list nodes are placed in arbitrary locations in memory. As a result CPU can't efficiently cache linked lists like arrays. Linked List vs Arrays Arrays give you the ability to access elements in O(1) time. In linked lists you start the traversal from the first element, so the worst case time complexity for search an element in linked list is O(n). Arrays have fixed size. Linked lists have no size constraints, any number of new elements can be added to a linked list (as long as you have memory). Since linked list nodes need to store pointer to the next node in the list, they comparatively take more space as compared to arrays. Linked lists give you the flexibility to easily add and remove elements from the middle (between any nodes) as compared to arrays where you will have to shift all other elements in order to achieve this. Unlike arrays, elements in a linked list are not stored at contiguous location in memory. Elements are connected using pointers. Types Of Linked List Depending on how the nodes are connected there are various types of linked lists: Singly linked list Doubly linked list Circular linked list In this article we will discuss about singly linked list. We will cover doubly and circular linked lists in detail in a separate article. Singly Linked List A singly linked list is formed by connecting nodes using a single link between them. This single link is formed using the next pointer of the node. A singly linked list looks as shown in figure below: To implement singly linked list we need to define two structures, one for the node and one for the linked list itself. Lets define the structure for linked list first: type LinkedList struct { head * Node } The LinkedList structure has one field head which is a pointer to head node (address of the head node). As stated earlier a head node is an entry point to a linked list. So when a linked list is first created we store the address of the head node in this field and we always start traversing the linked list from the head node using the address defined in head . Next lets define the linked list node: type Node struct { data int next * Node } Node structure contains two fields: data which represents the node data (for simplicity lets assume it is of int type) and next which is a pointer to the next node in the list. In an object oriented language like Java, Python we use Class instead of struct to represent the linked list. Linked List Class Node Class Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Inserting A Node Usually we insert new data at the end of the linked list. But there are cases where we may have to insert at head, insert after a specified node, insert before a specified node or insert at a specific position in the given linked list. Insert At The End To insert an element at the end of singly linked list we need to do the following steps: Take a temporary node pointer. We need to move this pointer from start of the list to end. Lets call this temporary node as currentNode . At the beginning currentNode points to the head node. Keep moving the currentNode pointer until it reaches the last node. Once the currentNode reaches the last node in the list, make the next pointer of the last node to point to the new node to be added i.e. currentNode.next = newNode . Implementation Language: Go Language: Java Insert Before A Node To insert a new node before a certain node, traverse the list until the node just before the specified node, then point the next of current node to the new node and next of new node to the before node. To insert a new node before a certain node in a singly linked list we need to do the following steps: Let beforeNode be the node before which we have to insert the new node and let the new node to be inserted be called newNode . Take a temporary node pointer. Lets call this temporary node as currentNode . To begin with currentNode points to the head node. Move the currentNode pointer from start of the list until the node just before the beforeNode . Now connect the next of currentNode to newNode and next of newNode to the previous next of currentNode . Lets understand this with an example. Consider you are given the below linked list: Lets say we have to add a new node with data = 3 before node 4( with data = 4). First we need to traverse the list from head the head node until node 2 (node before beforeNode ). Once we reach node 2 we break the link between node 2 and 4 as show in figure below: Then we connect the next of node 2 to node 3 (new node). After that we connect the next of node 3 to node 4 as shown in figure below: As you can see in above figure node 3 is now inserted in the list before node 4. Implementation Language: Go Language: Java Insert After A Node Similarly to insert a new node after a specified node we have to traverse the list from head node until the afterNode . After that, we need to point the next of the afterNode to the newNode and next of newNode to the node previously pointed to by the afterNode . Lets understand this with an example. If we were given the below linked list and we had to insert a new node with data = 3 after node with data=2: We traverse the list from head node to until node 2. Then point next of node 2 to newNode and next of newNode to node 4. Implementation Language: Go Language: Java Deleting A Node Deleting a node from a linked list is straight forward. We need to check if the given node is present in the list. If present remove it from the list and return the deleted node. Else return null. Language: Java Get All Elements To get a list of all elements present in a linked list we need to traverse the list from the head node to the last node and return the values present. Implementation Language: Go Complexity Analysis Time Complexity Search : O(n) Worst case time complexity for search operation is O(n) as we may end up checking each node to find an element in the worst case. Worst case time complexity occurs when the node to be searched is the last node in the list or if the given node is not present in the list. Insert: O(n) Insert operation also has a worst case of O(n) as we have to go through all the nodes before inserting the new node similar to search operation. Delete: O(n) Worst case complexity of delete is also O(n). Space Complexity: O(n) Each node in a linked list needs to store link to the next node along with the actual data. This means the space needed increases linearly for each new node added. Therefore, space complexity for a singly linked list is O(n). Now you know what a singly linked list is and how to implement it. Do not stop here, deepen your knowledge by exploring more articles on linked lists . That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe here . Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time : Join now Follow us on social media: Facebook , Twitter , Linkedin , Tumblr , Instagram .

Today lets solve yet another leetcode question Remove All Adjacent Duplicates In String . This article is part of our leetcode problem solutions  series, so be sure to explore other articles in this series after you are done with this problem. Let's now jump to the problem statement. Problem Statement: Remove All Adjacent Duplicates In String We are given a string s consisting of lower case English letters. Write an algorithm that removes two same/equal adjacent letters from this string. Your algorithm should repeatedly remove all such adjacent duplicate letters from s until none are left. Return the final string after all such duplicate removals have been made. Example 1: Input: s = "abccba" Output: "" Explanation: Here we first remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string. Example 2: Input:  s = "azxxzy" Output:  "ay" Constraints: 1 <= s.length <= 10^5 s consists of lowercase English letters. Solution If you encounter such questions involving removing characters from a given input string based on certain conditions, there is a good chance that this problem can be solved using a stack. Because problems involving such a pattern can be efficiently solved using stack in most cases. We will be using the stack approach here as well to solve this question. Below is a step by step explanation of how this algorithm works: Algorithm To begin with, initialize an empty stack (you can choose to use an array that acts like a stack for this purpose). Next, iterate through the characters of the given input string one by one. In each iteration, you do the following things: If the stack is empty or if the top element in the stack is not the same as the current element (in our iteration), add the current element to the stack. Otherwise (if stack is not empty and top element in stack is same as the current element), pop the top element from the stack (since we have found a duplicate). Continue step 2 & 3 until we reach the end of string s . Finally, return whatever characters are left in the stack as the result. Want to master coding? Looking to learn new skills and crack interviews? We recommend you explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Complexity Analysis Time Complexity This algorithm uses a loop to iterate over the characters in the given string once which has a time complexity of O(n), where n is the length of the given input string. And in each iteration we perform constant time, operations like pushing/popping elements from the stack which has a time complexity of O(1). Therefore, the overall time complexity of this algorithm is O(n) + O(1) = O(n) . Space Complexity Since we are using a stack here, and in the worst case we might end up storing all elements of s in the stack (this happens when all characters in s are unique), the space complexity is O(n) . That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .