Search Results

What is caching? A cache is a hardware or software component that acts as a temporary storage allowing fast access to data stored in it. The primary objective behind using a cache in any application is to improve performance. The process of storing and accessing the data from cache is known as caching. Caching is used everywhere. It is used in different layers like operating systems, CDN, DNS and also by various applications and services. If the requested data or item is available in the cache it is called a cache hit and if the requested data is not available in the cache it is called a cache miss. If implemented correctly, caches can help improve response times, reduce load on database, and save computation costs. Retrieving data from a persistent storage like database can take a considerable amount of time, caches reduce the response time of our API by providing fast access to data. Mainly caches are used to avoid frequency of network calls to database and to store the results of operations that are computationally expensive. Caches can help bring down the computation costs especially if your application is running on a cloud. How caching is useful? There are a wide variety of use cases where caching can be applied. Some of the scenarios where caching is useful are: Frequently Requested Data One of the popular scenarios where caching is useful is if you have to frequently query for some commonly used data. For example, in a service like twitter each time when we open a user profile, a common query is to get the count of followers/following for that user. This is not a very frequently changing data and is a good candidate for caching. You can fetch this data from database the first time when any user tries to access it, after which it can be cached and each subsequent request thereafter can be served from cache until the data becomes stale, which helps us avoid network calls to database for each request. Also, if you remember we have made use of caching in our URL shortener system design to cache the most frequently used short URLs, this is another example which shows the real life use case of a cache. Expensive Computations Some APIs are simple and have fast response times, while others might require you to do multiple intermediary steps involving slow and heavy operations that might delay the response time. A good example for this is a user feed API in a service like instagram or facebook. Displaying user feed for a particular user is mostly based on custom algorithms that may involve several computationally expensive operations like fetching all the people, public pages that a particular user follows from database, separating out the most recent posts made by his followers and pages, aggregating all of these posts and building a time sorted list using all of this data. Since we may have to make multiple calls to database and a lot of computation in order to get, aggregate and sort this data, our API response time can take a hit if we try to compute this on the go (as and when we get the request from user). And since a user feed is the first page that loads when we open an application like facebook or instagram, this can lead to a bad user experience. So in order to improve the performance and reduce the response time, we can precompute user feed for a particular user beforehand and store it in the cache (even before a request for user feed is made). We can serve this data to users directly from cache when he requests for it. This can potentially reduce the response time of our API from several seconds to few milliseconds. Avoid Load On Database If our service has a large number of users, and there are multiple microservices or replicas handling user requests which in turn call the database, this can put a lot of load on our database (especially during peak hours). This situation can be avoided by having a cache (most likely a distributed cache) which can ease the load on our database. 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 Why not cache everything? You might be wondering, if caches are so fast and efficient why not store all our data in cache instead of putting it in the database? Wouldn't that be an ideal thing to do? There are a few reasons mainly why we cannot do this: Firstly, the hardware used by caches are expensive as compared to the hardware used by traditional databases. Traditional databases mostly run on commodity hardware which are relatively inexpensive. So we may have to shell out a ton of money if we were to store everything in cache. Second, storing all our data on cache instead of a database is counter-intuitive because this defeats the purpose of using a cache in the first place. This is so because as you store more and more data on cache, this might increase the time needed to fetch the data from cache making it redundant. Where do a caches fit in? A typical web application backed by a data store would look like this: This data store can be a traditional database or another microservice. When client makes a request to our service, it initially hits one of the microservices responsible for handling the request. This microservice in turn connects to database to retrieve the data requested by the client. Calls to database can be slow and can utilize a lot of system resources. It would be a good idea to store at least some of these items in memory so that we don't have to reach the database for each and every request. What this does is firstly it can improve the response time of our API since we are responding directly from cache. Second even if our database is down due to some failure our service might still be able to serve some of the user requests. Also if there are lots of clients requesting for the same data again and again, having a cache in between can reduce load on our database. When we get a client request, our service first check to see if that data is present in cache, if yes our service directly responds from cache. If the data is not present or if the data is outdated it fetches the data from database. Cache Invalidation Ideally the data that is stored in cache is transient and not meant to be there forever. This data has to be cleaned up or updated from time to time to keep it coherent with the datasource. Data in cache can go stale if the original data (in database for instance) is changed or removed. The process of cleaning up or updating the data in cache with new values to keep it in sync with the original data is known as cache invalidation. One of the popular ways to invalidate a cache entry is by using the TTL strategy. In Time to live or TTL strategy each entry in cache is associated with a specific time after which the data is considered stale. Once the data expires, we can flush these stale entries using one of two ways: When the user requests for a stale data, we can actively expire it. We can also do this passively with the help of a job that runs periodically at specified intervals. Cache Eviction Policies Cache eviction policies control the way in which items are removed from cache, when the cache is full. Based on the algorithm selected a cache eviction policy decides which item to remove from cache when the cache limit is reached. Why is it needed? It is important that we store data in cache in such a way that no matter how much data is stored in our database, our cache only has relevant items considering the future requests that are expected to come into our system. While predicting the future requests we need to consider two things mainly: 1. When to add items to cache 2. When do we remove items from cache. Our cache performance almost entirely depends on our cache policy. Imagine having a very poor eviction policy, every time the service requests for some data from cache, it results in a cache miss. So hitting the cache is of no use in this case. Call to a cache is an extra step, and every time if it responds with no data, you would end up pulling data from the database almost all the time with an additional redundant call to cache as well, which can add to the delays instead of improving performance. In such a case having a cache becomes an extra overhead instead of improving application performance. Also as mentioned earlier hardware used by cache are expensive, so storing a ton of items in cache would not make any sense both in terms of budget as well as performance. So we need to set a limit on the maximum number of items that can be stored in a cache at any given time. When the cache is full we eliminate or remove certain items depending on the cache eviction policy selected. Some of the well known cache eviction policies are: LRU - Least Recently Used: In this policy, the oldest item is removed from cache when the cache is full. We have described LRU cache in detail in a separate article. LFU - Least Frequently Used: In this policy, items are evicted based on the frequency of usage. Each item in cache has a count of how many times it is requested, when the cache is full the item with the least count is evicted. MRU - Most Recently Used: This is exactly opposite to the LRU policy. When the cache is full, the item that is most recently requested is evicted from cache. RR - Random Replacement: When the cache is full, a random item is evicted from cache. FIFO - First In First Out: Items are evicted in the order in which they were added to cache. LIFO - Last In First Out: The cache evicts item that was added most recently regardless of how many times it was accessed before. Note: It is important to note that cache invalidation is different from cache eviction. We invalidate data from cache because it is either stale or has expired, but we evict data from cache when the cache limit is reached (memory is full). Distributed Cache If the amount of data from a service or an application is too large to be stored on cache memory of a single machine, the data in this case has to be distributed across multiple machines. Distributed cache is an extension of traditional cache. While a traditional cache is mostly a single server or machine, a distributed cache is can grow beyond the memory limits of a single machine, formed by the interlinking of multiple cache servers or cache clusters. A distributed cache has its data spread across several nodes (servers) in a cluster. It can also be across several clusters across geographically distributed data centers. Distributed caches have the ability to scale horizontally. As the data grows, we can add more machines (cache servers/nodes) to our cluster allowing our cache to grow along with the growing data requirements. Distributed caches are especially useful for applications with large data volumes. Some of the popular distributed cache solutions are Memcahed, Redis, Hazelcast. How cache is different from a CDN? CDNs are geographically distributed network of servers that work together to provide content (videos, images etc) to users more quickly. CDN acts as an intermediate layer between the end user and the server minimizing the number of requests that need to be served from the origin server. Consider a service like Netflix having origin server in United States. For a user viewing content say from India, if you have to serve this content from the origin server, this could result in a lot of delays and buffering for the user viewing the content because of distance the data has to travel from server to end user. This is where CDN comes to rescue. CDNs have servers distributed all over the world. These servers cache data and when user requests for data, instead of serving this data from origin server it is served from the CDN server nearest to the user thereby reducing the delay. The main difference between a cache and CDN is that while CDNs do perform caching, not everything that performs caching is a CDN. Also CDN servers are strategically placed at the network exchange points (IXPs) to avoid network round trips, while this may not always be true with a regular cache. Note: Internet exchange points (IXPs) are points where different internet providers connect to exchange traffic originating on their network. Caching Strategies There are a number of caching strategies and choosing the right one is an important step when you decide to incorporate caching into your system. Some of the popular caching strategies are: Write through cache: In this strategy data is written to both cache and database asynchronously. Write back cache: Service writes data to cache and it immediately responds back to the user. This data is written to the database after a specified interval or under certain condition. Write around cache: In this strategy data is directly written to database. When the user requests for this data at a later point, it is written into the cache. We will be explaining caching strategies in detail in our upcoming article. 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. Code Recipe New Year 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 solved the two sum problem.This is another article in the series leetcode problem solutions and this article is a solution to leetcode 7 two sum problem. Given a 32-bit signed integer x, reverse the digits in x and return the result. If after reversing, the result goes outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0. Example Example 1 Input: x = 123 Output: 321 Example 2 Input: x = -123 Output: -321 Example 3 Input: x = 120 Output: 21 Solution The problem statement is pretty straightforward. We are given an integer value x, our task is to write an algorithm that reverses this given input number. Also it is stated that the given number can be negative. If you have gone through our palindrome number article you already know that reversing an integer value was one of the sub-tasks we had to do in our palindrome number solution. The solution to this problem is almost the same as the reversing integer part described in palindrome number solution. This problem can be efficiently solved using the divide and mod operations. The idea is to reverse the given number by applying the divide (/) and mod (%) operations on it. To reverse the given number we need to do the following steps: Extract last digit from right to left from the given number using the mod operator. Put the extracted digit into its correct position in the result. Discard the currently processed digit from the original number using divide operation. Repeat steps 1 - 3 as long as the given value x is greater than 0. The above steps can be represented using the formula: result = result* 10 + currentDigit And, currentDigit = x%10 Lets understand this with an example: Consider x = 369 is the given number. Lets take a variable to store our result, lets call it result. Initially result = 0. One by one we process each digit in x from right to left, starting with the last digit 9. Iteration 1 Step 1 Extract last digit from x using the mod operator i.e. currentDigit = x%10 = 369 % 10 = 9. Step 2 Move currentDigit to its correct base position in result. This step is similar to the leetcode 8 problem where we had to move converted digit to its correct base position. As in leetcode 8 problem we can accomplish this by multiplying result with 10 and then adding the currentDigit to it. So result = result * 10 + currentDigit = 0 * 10 + 9 = 9. Step 3 Now that we have processed the digit 9 completely we need to remove it from x. We can do this using the divide operation, x = x/10 = 369/10 = 36. Iteration 2 Repeat the above three steps again for digit 6 in x = 36. Step 1 currentDigit = x%10 = 36 % 10 = 6 Step 2 result = result * 10 + currentDigit = 9 * 10 + 6 = 96 Step 3 x = x/10 = 36/10 = 3. Iteration 3 Again we repeat these steps for the final digit in x = 3. Step 1 currentDigit = x%10 = 3 % 10 = 3 Step 2 result = result * 10 + currentDigit = 96 * 10 + 3 = 963 Step 3 x = x/10 = 3/10 = 0 As you can see we have successfully reversed the given number 369. Finally we return result = 963. We do all these operations in a loop. Once x = 0 we stop our loop. How do we handle negative number in input? We take an integer variable signMultiplier to handle negative numbers. signMultiplier = -1 if the input number is negative and signMultiplier = 1 for positive numbers. Whenever we get a negative number we first convert it into a positive number first by multiplying it with the signMultiplier and then do the steps needed to reverse the number. Once the number is reversed we convert it back to negative number by multiplying the result again with signMultiplier. 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 Implementation Language: Go Language: Python Language: Java Complexity Analysis Time Complexity: O(n) n here is the no. of digits in the given input number. Time complexity is O(n) because we have to process each digit in the given number at least once to reverse the given number. Space Complexity: O(1) No extra space is used. Reversed an integer? Its time to reverse a list now! Check it out: Reversing a list 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. Code Recipe New Year 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.

Problem Statement In our previous article we solved the string to integer problem. This is another article in the series leetcode problem solutions and this article is a solution to leetcode 9 problem. Given an integer x, return true if x is a palindrome integer. An integer is a palindrome when it reads the same backward as forward. Example, 121 is a palindrome while 123 is not. Constraints: -2^31 <= x <= 2^31 - 1 Example Example 1 Input: x = 121 Output: true Example 2 Input: x = -121 Output: false Example 3 Input: x = 10 Output: false Solution This is one of the easier problems on leetcode and also an important one because the solution involves ingredients necessary to solve similar problems around number manipulation. Lets understand the problem statement first. In this problem we are given an integer value as input, our task is to write an algorithm that tells us whether the given number is a palindrome or not. So, what are palindromic numbers? A number is a palindrome if it remains same when its digits are reversed. In other words a number is a palindrome if we get the same sequence of digits whether we read the number from left to right or right to left. For example 121, 99, 2332 etc. are palindromic numbers. Solution 1 The first solution that might come to your mind when you look at this problem is to convert the given integer number to a string first, reverse it and then check if it is a palindrome or not as it is easier to reverse and compare individual characters in a string as compared to an integer. But converting an integer to a string is an extra overhead, is it possible to solve this problem by avoiding this extra overhead? It turns out this problem can be efficiently solved using the divide and mod operations. The idea is to reverse the given number by applying the divide (/) and mod (%) operations on it and then compare the reversed number with original number to see if it is a palindrome. If both original and reversed numbers are equal, then the given number is a palindrome, otherwise it is not a palindrome. To reverse the given number we need to do the following steps: Get individual digits from the given number from right to left using the mod operator. Put the digit obtained in step 1 into correct position in the reversed number. Discard the currently processed digit from the original number. Lets understand this with an example: Consider x = 123 is the given number. Lets take a temporary variable to store this given number, lets say tmp (this step is necessary because we need the original number x unmodified so that it can be compared with the reversed number in the final step). Also take a variable to store the reversed number, lets call it reversedNum. Initially reversedNum = 0. One by one we process each digit in tmp starting with the last digit 3. Extract last digit from tmp using the mod operator i.e. lastDigit = tmp%10 = 123 % 10 = 3. Next step is to move lastDigit to its correct base position in reversedNum. This step is similar to the leetcode 8 problem where we had to move converted digit to its correct base position. As in leetcode 8 problem we can accomplish this by multiplying reversedNum with 10 and then adding the lastDigit to it. So reversedNum = reversedNum * 10 + lastDigit = 0 * 10 + 3 = 3. Now that we have processed the last digit completely we need to remove it from tmp. We can do this using the divide operation, tmp = tmp/10 = 123/10 = 12. Repeat the above three steps again for digit 2 in tmp = 12. lastDigit = tmp%10 = 12 % 10 = 2 reversedNum = reversedNum * 10 + lastDigit = 3 * 10 + 2 = 32 tmp = tmp/10 = 12/10 = 1. Again we repeat these steps for the final digit in tmp = 1. lastDigit = tmp%10 = 1 % 10 = 1 reversedNum = reversedNum * 10 + lastDigit = 32 * 10 + 1 = 321 tmp = tmp/10 = 1/10 = 0 As you can see we have successfully reversed the given number 123. Now we compare the reversedNum 321 with original number x = 123, clearly these two are not equal, so it is not a palindrome, therefore we return a boolean false as result. We do all these operations in a loop. Once tmp = 0 we stop our loop. Note: We perform mod the given number specifically with 10 (and not some other number) because, when we do mod on any given number the remainder would result in the unit's place digit of that number. For Example: 123%10 = 3 (% is the mod or modulus symbol, which gives the remainder of the division as the result). We use %10 in this case to extract the unit's place digit in the number. But if we use any other number, it would not give us the exact digit. Implementation Language: Go Complexity Analysis Time Complexity: O(d) d here is the no. of digits in the given input number. Time complexity is O(d) because we have to check each digit in the given number at least once to determine if the given number is a palindrome. 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: Optimized solution 1 In solution 1 we are using extra space to store the input number in a temporary variable tmp. We do this because we need the original number x in order to compare it with the reversed number and therefore cannot manipulate the original number x. However we can avoid using the tmp variable by slightly modifying solution 1. The idea is to do the steps mentioned here to reverse the given number only up to the middle digit in x and then compare x with the reversedNum. Basically what we do here is reverse only half of the given number x and compare x with reversed number. This algorithm involves the following steps: Reverse half of the digits of the given number x. (Reversing is done using same steps described in solution 1). Once half of the digits in x are reversed, reversedNum will contain the reversed second half of the original input number and x (modified) will contain the first half of the original input number. For example if the given input is x = 123321, then after reversing half of the digits, reversedNum will be 123 and modified x will be 123. Now compare the modified x with the reversedNum. If both x and reversedNum are equal then return true as result, otherwise return false. Let take one more example to understand this. Consider x = 1221 is the given number, our algorithm reverses the last two digits in x i.e. 21 (until middle digit). So, at the end of our loop x = 12 and reversedNum = 12. Now compare (x, reversedNum) and return the result. Note: If x contains odd number of digits as in x = 12321, at the end of our loop reversedNum = 123 and x = 12. So we need to divide reversedNum by 10 if x contains odd number of digits before comparing x and reversedNum. Implementation Language: Go Language: Python Language: Java Complexity Analysis Time Complexity: O(d/2) d here is the no. of digits in the given input number. Time complexity of this algorithm is O(d/2) because we only have to check half of the digits in the given number x (last to middle) to determine if the given number is a palindrome. Space Complexity: O(1) No extra space is used. 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 In our previous article we solved the longest distinct substring problem. This is another article in the series leetcode problem solutions and this article is a solution to leetcode 8 problem. Implement myAtoi(string s) function, which converts a string to a 32-bit signed integer. Conditions for converting string to integer: Read in and ignore any leading whitespace. Check if the first character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2). If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1. Return the integer as the final result. Note: Only the space character ' ' is considered a whitespace character. Do not ignore any characters other than the leading whitespace or the rest of the string after the digits. Example Example 1 Input: s = "42" Output: 42 Example 2 Input: s = " -42" Output: -42 Example 3 Input: s = "4193 with words" Output: 4193 Solution This problem is rated medium difficulty in leetcode. However it is a pretty straightforward solution if you understand the logic behind converting a string to an integer. Rest of the handling is needed mainly to cover boundary conditions for various types of input values. How to convert a string type to an integer type? Given a string s how can we convert this to an integer? One way to do this is by manipulating the ASCII value of characters. Each character in a string has a specific ASCII value associated with it. Numeric values 0 - 9 have an ASCII value in the range 48 - 57(For more details refer ASCII table). We can use this information to convert a character to an integer type. Lets see how: For each character in the given string we need to do the following steps in order to convert it into an integer: First we need to check if the given character represents a numeric value.This can be done by checking if its ASCII value is in the range 48 - 57. Once we determine that the character represents a numeric value, we convert this character type into an integer type. To do this we need to subtract the characters' ASCII value with 48 (which is the ASCII value of number 0). Once the character is converted to an integer we need to move the integer to its correct base position in result by multiplying the previous result with 10 and adding the answer obtained in step 2 to it. These three steps can be represented by the formula: result = (result * 10)+ (ASCII value of current character - ASCII value of '0') 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 Lets understand this with an example. Consider s = "123" is the given string. Lets take a integer type variable result to store our result. Initially result = 0. We will start with the first character in string s = "123" i.e. character'1'. First step is to check if it is a numeric value, so we get the ASCII value of '1', which is 49, this is in the range 48 - 57, so we can conclude it is a numeric value. Next step is to subtract the ASCII value of 1 with ASCII value of 0, i.e. 49 - 48 = 1, which is our required integer type value. So now we have converted the character '1' to its integer representation 1. Next we move 1 to its correct base position in result by using the above formula. So at the end of first iteration result will be , result = result * 10 + (49-48) = 0 * 10 +1 = 1. Next we move on to the second character in string "123", i.e. character '2'. So, result = (result * 10)+ (ASCII value of '2' - ASCII value of '0') Thus result = (1* 10)+ (50 - 48) = 10 + 2 = 12. As you can see we have successfully converted the first two characters of the string s into integer format. Next we move on to the 3rd character '3'. Again we calculate result using the same formula. result = (result * 10)+ (ASCII value of '3' - ASCII value of '0') Thus result = (12* 10)+ (51 - 48) = 120 + 3 = 123, which our final result. How to handle input values containing +/- sign? We take a int variable, lets call it signMultiplier. We make signMultiplier = -1 for input values starting with '-' sign and 1 for input values starting with '+'. If the input contains any of +/- sign we start processing the string from 2nd character and we multiply the signMultiplier to our final result. Code Language: Go Language: Python Complexity Analysis Time Complexity: O(n) The worst case time complexity of this algorithm is O(n) since we have to go through each character in the string at least once to fully convert the given string to integer. n here is the length of the string. Space Complexity: O(1) No extra space is used. 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 Bubble sort is one of the simplest sorting algorithms. Bubble sort works by scanning (passing) the given array multiple times and repeatedly swapping adjacent elements until all elements in the array are sorted. In each pass, the largest element is pushed or bubbled to its correct position towards the end of the array. Hence the name bubble sort. During its processing bubble sort segregates the array into two parts, sorted portion and unsorted portion. Sorted portion (sorted elements) will be towards the end of the array. In each pass once the elements are moved to their correct position in the array (sorted portion), there is no need to compare those elements again. For a given input array arr that needs to be sorted in ascending order, bubble sort does the following steps: Bubble sort compares adjacent elements and swaps them if they are not in correct order. We start by comparing the first and second element in the array. If first element is greater than second element, that means they are not in correct order, so we swap them. If first element is less than second element, that means they are in correct order, so there is no need to swap. If first and second elements are equal then also there is no need to swap, because whether we swap them or not it doesn't make any difference to the output (however if you want your algorithm to be stable, then you should not be swapping them). Next we move on to compare the second and third element and repeat the comparisons mentioned in step 2. Then we compare third and fourth elements and so on until we reach the end of the array. This comparison procedure, described in step 2 to 3, from first element to the last element is known as one "pass" on the array. For an array of size n, we need a total of n-1 such passes on the array for it to be fully sorted. Also in each pass one element is moved to its correct sorted position in the array, we don't have to consider this element again in the next pass as it is already sorted. Simulation Consider we are given the below input array: Below is a simulation of how bubble sort sorts the given array in each pass. Elements marked in green are the elements to be compared and elements marked in grey are sorted elements. Pass 1 The largest element in pass 1, i.e. 19, is bubbled to the last position in the array. Pass 2 Pass 3 Pass 4 Color code used in above diagrams: Implementation The implementation for bubble sort is pretty straight forward, we need to run two loops. The outer loop keeps track of the number of "passes" and in the inner loop we compare the adjacent elements. 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 Below code shows a basic implementation of bubble sort: Code Language: Go Note: In the above code "n-i-1" ensures that we are not processing the already sorted elements again. Language: Python In the above implementation, the algorithm does all the comparisons even if the given array is already sorted. Clearly this takes extra time and is not an efficient way to implement bubble sort. In bubble sort it takes just one pass to determine if the array is already sorted. We can use this to our advantage, we can make a minor tweak to our basic implementation by introducing a boolean flag to optimize it as show in code below: Language: Go Language: Python This optimized solution does not improve to the worst case time complexity of bubble sort, which is still O(n^2) for both the approaches, however we can save a few unnecessary comparisons using this optimized solution. Complexity Analysis Time Complexity: O(n^2) The worst case time complexity of bubble sort is O(n^2) since we have to run two loops to implement it and in the worst case we would end up making nearly O(n^2) comparisons to get the final sorted array. The worst case occurs when the input array is in non-increasing or descending order. The best case time complexity of bubble sort is O(n). The best case occurs when the input array is already sorted. Bubble sort just needs one pass in this case to determine that the array is already sorted. Space Complexity: O(1) Bubble sort does not use any extra space to sort the given array, it sorts the given array in place. Key Points Bubble sort works well for large arrays where the given data is mostly sorted since it takes just one pass on the array to determine if the array is already sorted. But if most elements in the array are not sorted and if it is a large array then it is not preferred to use bubble sort as it is not efficient, algorithms like quick sort would be a better choice in such cases. Bubble sort is only useful for very small and nearly sorted arrays. Now you know how bubble sort works. Don't stop here, you can explore more sorting algorithms from code recipe here. 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. You can explore more algorithms in our algorithms 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 In our previous article we solved the two sum problem. This is another article in the series leetcode problem solutions and this article is a solution to leetcode 3 problem. For a given input string s, return the length of the longest substring in s without repeating characters. s consists of English letters and digits. Example Example 1: Input: s = "abcabcbb" Output: 3 Example 2: Input: s = "bbbbb" Output: 1 Example 3: Input: s = "pwwkew" Output: 3 Solution Let us try to understand the problem statement first. This is a pretty straightforward problem if you know what a substring is for a given string. A substring a continuous sequence of characters in a given string. For example, the substrings of string "abcd" are: "a", "ab", "abc", "abcd", "b", "bc", "bcd", "c", "cd" and "d". If the characters are not continuous it is not considered a substring. "bd", "ad", "acd" etc. are not substrings because the characters are not continuous as compared to the original string s. Note: Substring is different from a subsequence which may not be consecutive in nature. Now that we know what a substring is, we need to write an algorithm that returns the length of the longest substring in string s. But wait, remember we cannot just return any substring that is longest as clearly mentioned in the problem statement, we are only allowed to consider substrings without repeating characters. "Substring without repeating characters" is nothing but a substring containing all unique characters, there should not be any duplicate characters/letters in the substring. Now that the problem statement is clear, lets see what approach we can use to solve it: Solution 1: Naive Approach The most simple and straightforward solution to this problem is to check every possible substring for the given string s and return the length of the longest substring without repeating characters. This algorithm involves the following steps: For the given string s, generate all possible substrings. We can generate all possible substrings by using two loops. Fix the outer loop and move the inner loop (second loop) index to generate all possible substrings (refer code for more details). As and when you obtain the substrings using the loops (described in step 1), you can check if the current substring contains only distinct characters or has duplicates. We can do this by going trough all the characters of the obtained substring using another loop and adding it to a hashmap. During the iteration of the third loop, if you encounter any character that is already in the hashmap, the obtained substring contains duplicate characters. Otherwise all the characters in the substring are unique. If the substring contains duplicate characters, skip the current substring, do not consider it for calculating the result. If the substring contains all unique characters, check if the length of the current substring is greater than the length of all the unique character substrings obtained so far. If yes, update the result, else move on to the next substring and repeat steps 1-5. The running time complexity of this algorithm O(n^3). Code Language: Go Complexity Analysis Time Complexity: O(n^3) Time complexity is O(n^2) for finding the substrings using first and second loops and O(n) to find out if it is contains non repeating characters. So the total time complexity is O(n) * O(n^2) = O(n^3). Space Complexity: O(1) You might ask, we are making use of a hashmap to store characters of string, so how is the space complexity O(1). If you look at the problem statement carefully, it clearly states the given input string can contain only English letters and digits. Therefore the space needed to store these characters in a hashmap is constant i.e. 26+26 for upper and lower case English letters and 10 for digits. So in the worst case the space needed to store this in a hashmap is O(26+26+10) = O(62), which in general can be represented as O(1). This approach can be optimized to improve the time complexity to O(n^2) which is better than our earlier time complexity of O(n^3), but can we do better? 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: Sliding Window Technique This problem can be efficiently solved by using the two pointer sliding window technique. We slide the window forward each time we find a duplicate character. In this approach we need to process each character in the given string only once to find out the result. For a given input string s this algorithm does the following steps: We take two variables start and end to indicate the start and end of the window. The string between the start and end is our current substring. Initially both start and end point to the 0th index (1st character) of the string s, i.e. start = 0 and end = 0. Also create a result variable to store the required result. Next we create a hashmap which helps us to efficiently check if the current substring contains any duplicate characters. Lets name it charIndexMap. Key to this hashmap is the current character and value of this hashmap is the position of the character represented by the hashmap key in the given string s. In each iteration we check if the current character at end index is present in the charIndexMap or not. If the character is not present, add it to the hashmap along with the index. If the character is present in the map already, it means that the current character is a duplicate and we should not be considering the substring with this character while calculating the result. So, take the length of the substring from the start of the window until the previous character. If the current length is greater than the result, update the result. Also since we have found a duplicate character, we need to update the start index. Another important step here is to remove all characters from the previous window from our hashmap (since we have moved our window by updating the start variable). Finally add the current character to our hashmap along with its index. How do we update the start variable once a duplicate character is found? Remember along with storing the characters in hashmap, we also store the index of the character in the string as hashmap value. When we get a duplicate character during our iteration what does this value in hashmap mean? It simply means that the current duplicate character was earlier found at this index represented by the hashmap value (first occurrence). Using this info we discard all the characters before the first occurrence of the duplicate including the first occurrence (discard all characters from previous window). So our new start value will be start = map[current character] + 1. Note: Character literals are represented by uint8 or rune datatype in go. Simulation Lets see the working of the above algorithm with an example: Consider s = "abcabcbb" is the given string. Initially start = 0 and end = 0 and our hashmap is empty as shown in the figure below. Also we initialize result = 0. Now we check if s[end] = 'a' is present in our hashmap. Obviously 'a' is not present in hashmap, so we add 'a' as hashmap key and 0 as hashmap value indicating 'a' is found at 0th position in string (index based position). Same is shown in figure below: Next we increment end pointer. Again check if s[end] = 'b' is present in map. As 'b' is not present we add it to hashmap as shown in diagram below. Increment the end pointer, s[end] = 'c', and since it is not in map we add it to our hashmap. Increment end again. Now s[end] = 'a'. Now s[end]='a' is present in map, which means it is a duplicate character. Since we are looking only for substrings without repeating characters, we cannot consider the current substring "abca" for our result, so our valid substring is only till the previous character, i.e "abc". Since we have found a duplicate the next step is to update result. result = max(result , length of substring from index 0 to 2) = max(result , length of substring "abc") = max (3,3) = 3. Also since the current character is a duplicate, we need to update out start pointer. We update start as start = first occurrence of duplicate + 1. We can get the first occurrence of duplicate from our hashmap. So start = map['a'] + 1 = 0+1 = 1. Next, remove all the characters before our new start index and previous start index from hashmap (in this case our previous start index was 0 and new start index which we calculated a just before this step is 1) since they are no longer in our new window, so we remove 'a' from hashmap. Add the current character 'a' to map along with its index to hashmap. Now our diagram looks as shown below: Increment end pointer, s[end] = 'b'. Again 'b' is present in map. Update result = max(result , length of substring from index 1 to 3) = max(result , length of substring "bca") = max(3,3) = 3. Delete previous window characters, i.e. delete 'b' from hashmap. Update start = map['b']+1 = 1 + 1 = 2 and update hashmap, map['b'] = 4 for current character. Again we increment end pointer, end = 5 which is character 'c' which is a duplicate. We repeat the steps of calculate result, removing previous window characters from map, updating the start pointer and adding the current character to map. result = max(result , length of substring from index 2 to 4) = max(result , length of substring "cab") = max(3,3) = 3. start = map['c'] + 1 = 2+1 = 3. Remove character 'c':2 from previous window. Add the current character 'c': 5 to our hashmap. Now our diagram looks as below: Increment end pointer again, now end = 6, which is character 'b'. 'b' is also present in our map(we found it earlier at 4 index in our string s). result = max(result , length of substring from index 3 to 5) = max(result , length of substring "abc") = max(3,3) = 3. start = map['b'] + 1 = 4+1 = 5 and remove all characters before our new start ('c':5, 'a':3 and 'b':4) from our map. Also we update the current character 'b':6 into map. Finally we increment end again, our new end = 7. Again 'b' is present in hashmap. result = max(result , length of substring from index 5 to 6) = max(result , length of substring "cb") = max(3,2) = 3 and start = map['b'] + 1 = 6+1 = 7. Add 'b':7 to map. The end has now reached the end of the string s, so we terminate the loop and return the result. Note: The order in which elements are stored in the map does not matter. Code Language: Go Complexity Analysis Time Complexity: O(n) We check each character in the string only once. Yes we would also have to delete the elements from the hashmap once a duplicate character is found, but this is a constant time operation because at max the map can store only 62 elements in our case before a duplicate is found. Space Complexity: O(1) In the worst case we would have to store all n characters of the string s in hashmap, but this is a constant value which at max can go up to O(62) as explained in solution 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, 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. 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: Facebook, Twitter, Linkedin, Tumblr, Instagram.

Algorithm Binary search is one of the most commonly used search algorithms. It is also one of the fastest searching algorithms in terms of time complexity. Binary search works only sorted arrays. The algorithm divides the given array into two halves and does its searching on these halves based on certain conditions. Hence the name binary search (since it splits the array into two halves). Binary search works by reducing the search space by half each time, in each iteration half of the elements are eliminated from the current search space. Binary search starts searching from the middle of the array and moves outwards (either left or right), unlike some other search algorithms like linear search that begin their search from the first element of the array. For a given input array arr and a target element lets say x, binary search does the following steps: To begin with the algorithm considers the entire array as its search space. We create two variables left and right representing the index of the first and last elements in the search space. Next we need to find the middle element by dividing the search space into two halves. If our search space has n elements, we can find the middle element by using the formula: mid = (left+right)/2. Now our search space is divided into halves, one half on the left of middle element and the other half on the right of the middle element. Now compare the target element x to the middle element arr[mid] obtained from the previous step. There are three possibilities here: 1. x is equal to middle element 2. x is greater than middle element 3. x is less than middle element. If x is equal to middle element we have found our answer, so we return the index of the middle element as our result. If x is greater than middle element, we can discard all the elements on the left of middle element. We can safely do this because we know that the input array given to us is sorted, so if x is greater than middle element it should obviously be greater than all elements before the middle element. So, definitely you cannot find x by searching in the left half of the array. Hence we discard all the elements in the left half. Therefore our new search space now is the right half (all the elements on the right of middle element), so we update left = mid+1 and right remains the same. Thus our new search space is from index mid+1 to index right. Similarly if x is less than middle element, we know there is no benefit searching the right half elements, since x will obviously be less than all elements on the right of middle element. Therefore update right= mid-1 and left remains the same. Thus our new search space is from index left to index mid-1 (left half). We repeat steps 2-6 until we find the middle element or the search spaces reduces to 0 elements (target element not present in the array). If the given target element is not found we return -1. Note: Our above formula to calculate middle element, mid = (left+right)/2, can result in overflow for large arrays. We can alternately use the below for to calculate middle element to prevent overflow condition, mid = left + (right-left)/2 How mid=left + (right-left)/2 prevents overflow? Please refer the detailed explanation here. Working Consider we are given the array [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] and the target element is x = 19 as shown below: Initially our search space is the entire array as highlighted in grey. We create two variables left and right representing the indexes of the first and last elements in the search space, as shown in the below diagram. Initially left = 0 and right = 9. So, mid = (0 + 9)/2 = 4.5 ~ 4. Now we compare x to middle element 9. Clearly 19>9, so we discard all the elements on the left of mid (Discarded elements are shown using X mark). Also now our new search space is all the elements on the right of middle element (highlighted in grey). So we update left = mid+1 = 5 and right remains same. Again we calculate middle element using our new left and right values. mid = (5+9)/2 = 7. We repeat the step of comparing x to the middle element. Again x is greater than middle element (19 > 15). So we shift our search space to the right half by updating left = mid + 1 = 7+1 = 8 and right remains same. Thus our new search space now is from index 8 to 9 as highlighted in grey in the below diagram. Now mid = (8 + 9)/2 = 8.5 ~ 8. Same is shown in diagram below: Again 19 > 17, so left = mid + 1 = 8 + 1 = 9 and right remains same. Now the target element x is equal to the middle element, i.e. arr[9] = x = 19, therefore we have found the target element we are searching for, so return 9 as our result indicating that the target element is found at 9th index in the given input array. Implementation We can implement binary search using both iterative as well as recursive approaches. Below code shows both these implementations: Iterative Approach Language: Go Recursive Approach Language: Go 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 Complexity Analysis Time Complexity: O(log n) In the worst case our algorithm would end up doing log n comparisons to find the target element . The worst case occurs when the target element is the first or last element in the input array or the target element itself is not present in the array. How time complexity is O(log n)? Consider you are given an array with 8 elements arr={2, 4, 6, 8, 10, 12, 14, 16} and your target element is 2. As we know binary search discards half the elements in each comparison. In the first comparison the search space reduces to 4 elements, in the second comparison it reduces to 2 and then 1. So in total we had to make 3 comparisons. Similarly if the array had 16 elements, it would take 4 comparisons, i.e. 16 - >8 - >4 -> 2 ->1 in the worst case. Now if you observe both the cases where n=8 and n=16, the number of comparisons we had to do corresponds to a logarithmic function with base 2. For n=8, log2 8 = 3 and for n=16 it is log2 16 = 4 which correlates to 3 and 4 comparisons that our algorithm had to do respectively. And this relation is true for all values of n and hence the time complexity is O(log n). Space Complexity: O(1) No extra space is used is used for iterative approach. For recursive approach space complexity is O(log n) if you consider the recursion call stack otherwise O(1). Output We can test our algorithm with the below code snippet: We get the below output after executing the test: Note: Position displayed in the above output is array index based. Advantages Binary search eliminates half the elements in each iteration, thus has a time complexity of O(log n), therefore it is more efficient as compared to other search algorithms like linear search. Binary search is preferred over other search algorithms especially when the size of the input array is large. Disadvantages Binary search cannot be efficiently implemented for linked lists as linked list does not allow random access in O(1) time as compared to arrays. Remember quick access to elements is needed to reach the middle element efficiently in binary search. Binary search only works on sorted arrays. 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. 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 Educative IO Tutorials Fiverr Qualify for a better job in weeks instead of years, with skills-based training & certification courses at Unmudl today!

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.

Introduction Singleton Design Pattern is a creational design pattern. Singleton pattern lets you ensure that only one instance of a class (struct in go) is created. This single instance created is called singleton object or singleton instance. Singleton pattern lets you ensure that a class has only one instance, thereby providing a global access to this instance. The singleton pattern usually provides a global method which is responsible for creating and returning this singleton instance. This global method wraps the object creation logic thereby hiding the complexity from the client. The user of this object might not even realize that he is working with a singleton object. When we say singleton object is accessible globally, it is important we make sure that we wont allow clients to modify this global object. Once the singleton object is created the pattern should ensure that it is immutable. Otherwise the client or application may end up seeing an unexpected behaviour while using this object. The singleton pattern ensures that the object is created only once, and once it is created the pattern returns the same object without any modification, no matter how many times the client tries to get the object. To ensure that the singleton object is accessed globally and that it cannot be modified once created, singleton pattern encapsulates the singleton object inside a globally accessible method, also you need to make the instance unexported which guarantees it is not accessible directly outside the package. Use cases where singleton pattern is useful: Database connection object: In case of a database, creating a database connection object is usually an expensive operation since it needs a lot of heavy-lifting to be done in the background. So, ideally what we would want in this case is to create the database connection object once and reuse it across our application rather than creating a new object for each call. This makes singleton pattern an ideal choice for this use case. Logger: Even in case of logging for an application, enabling or disabling logs, changing the severity of logged messages etc needs to be done on a single instance which makes singleton pattern suitable for this case. Implementation As mentioned earlier, we need to provide a global GetInstance() method to our users. The first caller who calls this method creates the singleton instance. For rest of the callers we return the same instance which was created earlier. As simple as it may seem, it is very easy to get the singleton pattern wrong. Lets discuss some of the correct ways to create the singleton pattern in go. In go the singleton pattern can be implemented in two ways mainly: Using mutex locks. Using the Once.Do() method in sync package. Using Mutex Locks One way to implement the singleton pattern in go is to make use of mutex locks. You can find the mutex lock methods (Lock and Unlock) in go "sync" package. Below is a implementation using mutex locks: The idea here is simple. During the program execution, the first thread or go routine to call the GetInstance() method acquires the lock and continues execution to the next line of code. After this point no matter how many threads try to call the GetInstance() method, they will be locked at line 13 in code, they wont be allowed to proceed further since the first thread has already acquired the lock. The first thread satisfies "if instance == nil" condition and therefore enters the if block and creates a singleton instance (line 17) and returns it (line 19). Once the first thread returns from GetInstance() method the mutex lock is released and next thread (in order as they are called) acquires the lock. But now onward "if instance == nil" condition is always false since the first thread has already created a singleton instance. Therefore all threads after the first thread simply return from the GetInstance() method without creating a new instance. Thus the GetInstance() method returns a single instance of singleton struct no matter how many times it is called. This approach works fine and does serve its purpose of creating a singleton instance. But there is one slight drawback in the above implementation. Mutex locks can be expensive because it needs to do some bookkeeping in the background to ensure that no more than one thread or go routine acquires lock at a time, among other things. This is especially true when there are multiple threads trying to acquire a lock. In the above implementation, if there are 100 calls to GetInstance() method, all 100 threads will acquire a lock before returning the singleton instance. But we know acquiring a lock after the first thread (after the singleton instance is created) is unnecessary. The purpose of using mutex lock is to ensure that if multiple threads try to access the GetInstance() method at the same time, in parallel, the GetInstance() methods doesn't create multiple instances (multiple copies) of our singleton struct. However, we can modify the above implementation slightly to overcome this drawback. All that we have to do is wrap lines 13-18 within another "instance == nil" check. This way all calls to GetInstance() method that come after the first call doesn't have to acquire a lock, our GetInstance() method can simply return the singleton instance after the outer "instance == nil" check. Below is the modified solution: The first (outer) if statement checks if the thread needs to acquire lock, and the second (inner) if statement tell us if the singleton instance is already created or we need to create it. 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 Using "Once.Do()" Method Another way to implement the singleton pattern in golang is by using the Once.Do() method in sync package. The library ensures that the code within once.Do() block is executed only once, this guarantee is implicitly provided by go. Note: To know more about the internal working of Once.Do() method refer this. Below is the implementation using Once.Do(): In this method we place the singleton instance creation code inside the Once.Do() block instead of using the mutex locks. The Once.Do() method also uses mutex locks internally, so it is necessary to use the outer if statement even for this approach. Output We can test both these implementations using the the below code snippet: The above snippet creates 1000 go routines which call the GetInstance() method almost in parallel. You can notice from the below output that both of our solutions print the "Creating a new singleton instance" message only once indicating only one instance of the singleton struct is created even though 1000 goroutines are invoking the GetInstance() method. 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 ​ Netflix system design is a common question asked in interview these days. Before we begin with the Netflix system design it is important to understand the general behavior of the system we are trying to design. Systems like Netflix, Youtube etc are generally read heavy i.e. there would lesser number of people uploading the video as compared to people viewing it. So there would be higher number of reads on our database or storage where we store our videos(a and video metadata) than writes to it. We need to keep this in mind while designing our system. We will be using microservice based architecture to design our system as compared to a monolith because of the obvious benefits. Now coming to the choice of storage, we have different kinds of data to store like user data, video metadata and the video file itself. Where does our onboarding service save the uploaded video? Can we store this in a database? It is generally not a good practice to store video files in a database because this can put a lot of pressure on our database and consume a of lot of bandwidth since fetching a video can be a slow and heavy operation(in terms of bandwidth). Distributed storage like amazon S3 are designed to store flat files like images and videos. So we would store our actual video file on S3 and store only the link to S3 on our database. Coming to user data and video metadata, data, considering the size of the user data may not be that huge we could store this on a SQL database. But we are talking about 1 billion user here, the amount of data is still considerable and can only grow overtime. Using No-SQL database would provide us better flexibility in terms of scaling horizontally or sharding if there comes a need to do so at a later point. Also looking at the use case we don't see a requirement to make complex relational queries or ones requiring joins here. So no-SQL would be a better choice. Which No-SQL solution would be a better choice for our use case? Since we know read to write ratio is high for our use case, a wide column database like Cassandra which is optimized for fast reads would suit our needs. Also since we are looking for high availability and consistency can take a back step in the interest of availability for our use case, Cassandra makes a ideal choice. Having said that it is important to note that Cassandra does promise eventual consistency. High Level View At a high level our service need to support the following main functionalities: 1. Upload videos 2. Search for videos 3. Stream videos To start with let us have three microservices to handle each of these responsibilities. We will call them onboarding service, video search service, streaming service. Let's see each of these functionalities in detail. Onboarding Videos(Uploading Videos) Uploading a video would be done by content creators. In case of a service like youtube it could be the individual creators, in Netflix it could be done by production houses. Also the length of the uploaded videos might vary slightly from platform to platform. We would not get into the details of user type discussion here, also we will assume the videos uploaded are fairly large(movies, web series etc). In either case this should not majorly impact the way we design our system. When the user uploads a video, the request hits the onboarding service. The onboarding service is responsible for uploading this video into s3. Uploading to a object storage is important because, If the size of the video is more, this would consume a lot of resources(memory) if it was to be stored in memory in video processing service during processing. It would serve as a back up in case our video processing service goes down due to some failure while processing the video. Object storage services like amazon s3 are mostly distributed services, so the chances of the uploaded videos getting lost is extremely low. After this the onboarding service saves the video metadata to our metadata database. Video Processing Once the video is uploaded to S3, we need to process the video further before making it available to our viewers. Processing a video can be a time consuming task, we may have to pass the video through multiple intermediate stages before it is ready for consumption for viewers. It would be a good idea to distribute various responsibilities involved in processing a video into different microservices because some stages of the processing might be computationally intensive and take more time, other stages might finish faster. So having a microservice to handle each stage of processing gives us more control if we had to selectively scale specific stages to improve performance. For instance, for the stages that are slow and require more time, we can have more replicas of that microservice to handle the job. Other stages that are faster may not require that many replicas. Also having a microservice to handle each stage helps in parallel processing, a faster stage does not have to wait for a slower stage until it finishes its job, after a stage finishes its job it can simply put that event in queue and take up the next task. Once the other stage is ready it can poll it from the queue. Doing a parallel processing of stages reduces the overall time needed to process the video. Video Splitter Service In system like Netflix, the size of the uploaded videos can be very large, and we would not want our microservices processing the video to have the whole video in memory for the duration of processing. Processing the whole video can increase the time needed to process the video. If the processing fails midway for some reason we would have to process the whole video again. Also having a large video in memory during processing can be expensive in terms of memory. Therefore we need to split the video into chunks and do our processing on these chunks, rather than processing the whole video. Splitting the video this way helps distribute the work and also process in parallel. In case of a failure we don't have to start from the beginning but start from the chunk until which we have successfully processed. Client apps these days have the ability to request for video of various quality and formats while viewing the video, dividing the video into chunks helps better the viewing experience as our service doesn't have to respond with the whole video again, it only needs to respond with the chunk for the requested quality and format that the user has requested. Let's call this service responsible for dividing the video into chunks as video splitter service. The video splitter service is responsible for dividing the given video into multiple chunks of smaller size. Once the video is divided into chunks the video splitter service uploads these chunks into S3. Also it updates the split video metadata in the metadata database. But you may ask how does the video splitter know when the video is uploaded to S3. And also how does the next stage(microservice) in video processing know when the video splitter service has successfully completed its job? That is a valid question. One way to achieve this is, onboarding service can explicitly notify this to video splitter service via a REST or gRPC call when it finishes its job, same can be done by video splitter service and so on. This approach works fine and should serve the purpose. But the problem with this approach is that our microservices needs to be aware of the next microservice in the video processing queue. Also this approach tightly couples the video processing stages to the microservices involved, which is something which we might not want especially when we have to scale our services later. Another way to achieve this is using a pub sub mechanism using a distributed queue like Apache Kafka. Each microservice that needs co-ordination in this case needs to register with Kafka queue. After a microservice has done its part of processing it registers a completed event in Kafka queue. The microservices in the next stage of processing poll/listen to these events and take it forward from there. In this approach each microservice need not know other microservices in the processing stage, neither do they need to communicate with them. Microservices only communicate with Kafka and hence this would also scale well. If tomorrow we had to add another microservice into our video processing sequence, all that we have to do is add another microservice to handle the processing for that stage and register it with Kafka, the next service can listen to this even and take it further from there. We need not have knowledge of other microservices or what they do. Video Encoder Service The next step in our video processing sequence is to encode these chunks. We can have another microservice, lets say video encoder service, that handles this part of the processing. The video encoder service is responsible for encoding the video into different formats, quality and resolution. This is necessary because, Our video will be viewed on multiple types of devices. By users with different network bandwidth, so users might request for video of various quality depending upon their network speed. Once the encoder service successfully encodes each of these chunks into various combinations of video format, quality and resolution it registers a completed event in the Kafka queue. It updates the encoded video metadata in the metadata database. Content Verification Service The next stage in our processing is verification of the contents of the video. The content verification service is responsible for checking the video for restricted content like violence, nudity etc. If this check fails a notification will be sent to the uploader of the video along with the reason for rejection. If the video is successfully verified, content verification service registers a completed event in the Kafka queue. Video Tagging service Video tagging service is responsible for creating tags for uploaded videos. These tags could be created based on the description provided by the client during video upload among other things. All the created tags are then pushed to the elastic service. These tags can be used at a later point during video search, video recommendations etc. Once it finishes its task the video tagging service registers an event in queue. Also it uploads the fully processed video into S3. Note: We have covered some of the general steps for processing a video. Actual stages may vary for depending on the requirements. The idea is to give a general perspective on how this requirement can be handled irrespective of the stages involved. Video Distribution Service So now we have a fully processed video ready to be viewed by ours users in S3. A platform like Netflix or youtube has a global audience. If our servers and infrastructure is located in United States, someone requesting for a video from India for instance would face a lot of delay because of the network round-time. To serve our audience worldwide without delays, it may not be feasible for us to place our servers in each of these locations. This is where the video distribution service comes into play. Video distribution service is responsible for picking up the final processed video and pushing it to our caching servers(CDN). There are several strategies how we can cache our data in these CDN servers located worldwide. We can employ a push model where we push the data into these CDN servers. There is also a pull model, in which data is pulled into the cache servers when the user requests for it the first time. Both approaches have their own pros and cons. The choice to select between the two really depends on what suits our requirements. Suppose we decide to go with the push model, it is important to consider that it may not be a good idea to push our content to all CDN servers. For instance, a bollywood released in India being cached in African CDN might not be of that much useful. The video distribution service should intelligently push these video to specific CDNs based on some intelligent algorithm. One such way may be to ask the uploader to provide target audience for the video during upload and we push only to CDN servers in provided as target regions. For a region where the content is not cached in a CDN, the first user might experience some delays while requests for the video since it has to be streamed from our servers, but later ones wont see the delay since the request would be served from nearest cached CDN server. 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 Video Search Video search is made simple because of the processing and tag creation done by Video tag service. Whenever a user searches for a video it is passed to the video search service and this service talks to elastic search. Remember we have provided elastic all the tags it needs during video tagging process. Elastic search provides out of the box solution for searching the given text(JSON input/output). Streaming video and managing likes, dislikes, views count When the user requests to view a video, the request is first sent to the nearest CDN server. If the video is cached, it is served from CDN. Also a copy of the video metadata containing the total likes, dislikes and views for that video is sent to the user. If the video is not cached in CDN, both the video and metadata has to be obtained from the origin server. The request hits the video streaming service which queries the metadata database which contains the URL for the requested chunk of video. The video streaming service then pulls this chunk from S3 based on the URL obtained from metadata database. Also since this data was not found in the CDN this can now be cached in the CDN server so that the next user requesting for this video doesn't have to reach the origin server to get the content. Below is the final design diagram: Netflix System Design Diagram Summary So did we cover all the functional and non-functional requirements? Our design supports uploading, streaming, searching searching videos and also viewing the like/dislike , view counts. So functional requirements are covered. Our system is reliable, Amazon S3 is promises to provide 99.999999999% durability of objects over a given year. So the chances of a video getting lost is very low. Pushing our content to CDN servers distributed across geographies ensures our users face minimum latency while streaming videos. For availability we have multiple replicas of a service running so that if one of them goes down it doesn't result in downtime for the users. Also we can take availability to another level by having multiple data centers distributed across regions, so that even if a data center in a goes down users can still be served from the other available data center. They might experience slight delays due to network round time but our service will still be available. So this covers all the functional and non functional requirements mentioned. Let me know if you have any questions by commenting below. Make sure you checkout our other posts. 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. You can explore more such amazing articles from code recipe in our blogs section. Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.

Problem Statement ​ In our previous article we solved the two sum problem. This is another article in the series leetcode problem solutions and this article is a solution to leetcode 11 problem. Consider you are given n non-negative integers say a1, a2, ..., an, where each element in the array represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water. Notice that you may not slant the container. Example Example 1: Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Example 2: Input: height = [1,1] Output: 1 Example 3: Input: height = [4,3,2,1,4] Output: 16 Example 4: Input: height = [1,2,1] Output: 2 Solution ​ Let us try to understand the problem statement first. In this problem, we are given an array of integers representing the heights. The distance between these heights is uniform (1 unit). Our job is to write an algorithm to find the largest container or largest area that can be formed by joining any of these two heights. We can calculate the area using the formula, Area = minimum{height 1, height 2} * width. Note: We take minimum of two heights for area calculation because, any water over the minimum height cannot be held by the container, as it spills over. For example, if (3,4) are the given pair of heights, the container formed using these two heights would look as in the below diagram: As you can see from the above diagram, the maximum possible water level for heights (3,4) is height=3. Even if you try to pour more water into the container, it gets spilled over from the left side where height is 3. That is the reason why we take minimum of heights 1 and 2 while calculating the area. Solution 1: Brute Force The brute force solution to this problem is to check every possible combination of the given heights. For example if [4,3,2,6] is the given heights array, we start by comparing the 0th and 1st index elements, i.e. heights (4,3). So, Area = minimum{4,3}*1 = 3*1 which is equal to 3 (calculated using the above area formula). Then we check for heights at 0th and 2nd index i.e. (4,2) for which Area = minimum{4,2}*2 = 2. Similarly we check all the possible combinations (4,6), (3,2), (3,6), (2,6) and finally return the maximum area obtained out of all the combinations as the result. This algorithms involves the following steps: Use two loops, fix the the outer loop and move the inner loop to check every possible combination of two heights in the given array. Outer loop runs from 0 to n-1 and inner loop runs from outerLoopIndex + 1 to n. For each iteration of the inner loop you will get a pair of heights. Check if the area formed using this pair of heights is greater than the max area so far. If yes update the result, else continue to check the next pair. Repeat step 1-4 for all possible pair of heights. Finally return the maximum area obtained as the result. Since we need to check every possible pair of heights in the given array in order to find the maximum area, the running time complexity of this solution is O(n^2). Code Language: Go Complexity Analysis Time Complexity: O(n^2) Space Complexity: O(1) 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: Optimized Solution This problem can be solved efficiently in linear time using two pointer technique. If you observe the previous solution carefully, you will notice a pattern. For instance, if [1,8,6,2,5,4,8,3,7] is the given array, if you start with the combination of first and last heights and move inwards i.e. (1,7), (1,3), (1,8), (1,4) and so on, you can see that you get no benefit by using combinations (1,3), (1,8), (1,4) so on after (1,7) to calculate area, as the minimum height obtained by using any of these combinations remains same. This is so because in all cases 2nd height is greater than the 1st height (height1= 1, which is same for all the pairs), and since we take the minimum of 1st and 2nd heights while calculating the area, we always end up with 1 as the result(for minimum height) for all the above combinations. This is true for all such cases where for a set of combinations one of the heights is same and it is smaller than the other height in all pairs. Also the width keeps decreasing as we move inwards, for (1,7) width is 8, for (1,3) width is 7, for (1,8) width is 6 and so on. Therefore the area also will decrease. We can use this to our advantage to solve this problem in linear time. This approach involves the following steps: We need to start our algorithm with left pointer pointing to the 0th index and right pointer pointing to the last index of the heights array. We calculate the area using the left and right heights using the previous formula. After this we need to retain maximum of left and right pointers (heights) and move the other pointer. For example if our (left, right) = (1,7), after calculating the area, we check which of (left height, right height) is larger. In this case, right height i.e. 7 is the larger of the two. So, we keep the right pointer at the same position and increment the left pointer by 1. Similarly if the left element was larger as in (8,3) then we keep the left pointer at the same index and decrement the right pointer after calculating the area for (8, 3). We can do this because we know, we do not get any benefit (in terms of area obtained) by retaining the smaller height, and thus this would have no impact on the output. We have to repeat the above steps as long as our left pointer is less than right pointer, after which we return the maximum area obtained thus far as the result. This algorithm goes through each array element only once to find the result, so the time complexity of this algorithm is O(n). Code Language: Go Complexity Analysis Time Complexity: O(n) Space Complexity: O(1) Output We can test both these solutions using the below code snippet: Below is the execution result: 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.