Hello Code Recipian! Welcome back to another article on leetcode problem solutions . Today we will be solving leetcode problem 739, Daily Temperatures . Problem Statement: Daily Temperatures Given an array of integers, temperatures , where each element in the array represents the daily temperature for that day, return an integer array result  such that, result[i]  is the number of days you have to wait after the iᵗʰ day to get a warmer temperature. If there is no future day for which this is possible, then result[i]  = 0. Example Example 1: Input:  temperatures = [73,74,75,71,69,72,76,73] Output:  [1,1,4,2,1,1,0,0] Explanation: We have to wait 1 day after 73 in order to get a warmer temperature, 1 day after 74 and 4 days after 75 in order to get a warmer temperature. Example 2: Input:  temperatures = [30,40,50,60] Output:  [1,1,1,0] Example 3: Input:  temperatures = [30,60,90] Output:  [1,1,0] Constraints: 1 <= temperatures.length <= 10 ^5 30 <= temperatures[i] <= 100 Solution This is a classical problem that can be efficiently solved using a monotonic stack , more specifically a monotonically decreasing stack . If this is the first time you have come across monotonic stacks, we highly encourage you to go through this article on monotonic stacks before you proceed further in the article. Interview Tip: Whenever you encounter problems involving keywords like "Next Greater Element", "Next Smaller Element" or something along this line (like the problem statement given here), it could be a hint that you should be using monotonic stack 😊. We can solve this problem efficiently using a monotonically decreasing stack (MDS). A monotonically decreasing stack maintains the stack elements in decreasing order from bottom to top. Below is the step by step explanation for this algorithm: Initialize two arrays: result and stack result array as the name indicates is used for storing the result. Initially all elements of result array are initialized to 0. We store the index of element in temperatures array in MDS (If this sounds confusing, don't worry; it will become clear as you continue reading the article). stack represents our monotonic decreasing stack. Now, iterate through the elements of temperatures array using a for loop. For each iteration of this outer loop we perform the following operations on MDS: As long as the stack is not empty and if the current temperature value is greater than the temperature at the index stored at the top of the stack , this means we have found a warmer day for the day represented by the index at the top of the stack . Therefore, we need to do two things: Update the result, for the day indicated by the index at the top of stack . Pop the top element from stack . If condition a is not satisfied, it means the current temperature is less than the element at the top of the stack . So, we add the current temperature index to the stack . Once all elements in temperatures array are processed we return the result array. Simulation Below is the simulation for this algorithm: Want to master coding? Looking to learn upskill and crack interviews? We recommend you explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Complexity Analysis Time Complexity This solution makes a single pass through the given temperatures array and uses a monotonic decreasing stack to solve the problem. Let's analyze the time complexity: Outer loop: This loop iterates through all elements of temperatures array once. If n is the size of the given temperatures array, then the time complexity of the outer loop is O(n) . Inner loop: Each temperatures element is pushed and popped from the stack at-most once. This means that, overall, the total number of iterations made by the inner loop during the execution of this algorithm is bounded by O(n) . Therefore the overall time complexity of this algorithm is O(n) + O(n) = O(n) . Space Complexity This algorithm uses a stack to store indices of the temperatures array. In the worst case (when all elements of temperatures array are in decreasing order) we will end up storing all the element indices on the stack making space complexity O(n) . That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another article on leetcode problem solutions . Today we will be solving leetcode problem no. 387, First Unique Character in a String . Problem Statement: First Unique Character in a String Given a string s find the first unique/non-repeating character in it, return its index as result. If it does not exist return -1. Example Example 1: Input: s = "leetcode" Output: 0 Explanation: The character 'l' at index 0 is the first character that does not occur at any other index. Example 2: Input: s = "loveleetcode" Output: 2 Example 3: Input: s = "aabb" Output: -1 Constraints: 1 <= s.length <= 10^5 s consists of only lowercase English letters. Solution If we read through the problem statement, it is mostly obvious what data structure we should be using to solve this problem. Since we are dealing with character count here, hashmap should be the first data structure that should come to our mind. This problem is labeled as an easy problem on leetcode, and it is indeed an easy one, but it comes with a slight caveat. And if this doesn't strike to you right away, it could prove a bit tricky sometimes. Let's see how we can go about solving this problem using hashmap data structure. Algorithm Below is the step by step explanation for this algorithm: As mentioned earlier this algorithm makes use of a hashmap. Initialize a hashmap with a char type key (byte in some languages) and integer type value. Let's call this hashmap freq (short for frequency). After this, we iterate through the given input string s from start to end. In each iteration we increment the current character count by 1 in our hashmap freq . At the end of step 3, we have all the characters in the string s in our hashmap along with the frequency of occurrence of each character. Now, we iterate through the string s one more time and in each iteration we perform either of the below two steps: If the current character count in freq is equal to one, we have found the first unique character in string s and hence our result. So, we return the current index as result. If count is not equal to one, it is not a unique character. Therefore we simply continue iterating through the string. If the execution comes out of the second for loop, without returning, it means there are no unique characters in the input string s . Therefore we return -1 as result as mentioned in the problem statement. Simulation Below diagram shows a pictorial depiction of the working of this algorithm: Want to master coding? Looking to learn upskill and crack interviews? We recommend you explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Complexity Analysis Time Complexity First Loop: The first loop iterates through string s from start to end, once. This has a time complexity of O(n) , where n is the length of string s . Second Loop: The second loop iterates through string s until it finds the first unique character. In the worst case if i.e. when a unique character is at the last position in string s or if unique character is not found, then this loop has to iterate till the end. So, the time complexity of this loop is also O(n) . Hashmap Operations: All hashmap operations inside both these loops are constant time operations with time complexity O(1) . Therefore the overall time complexity of this solution is O(n) + O(n) = O(n) . Space Complexity This solution uses a hashmap freq to store the frequencies of characters in string s . Apart from this we do not use any additional storage for our computation. In the worst case when all the characters in string s are unique, this algorithm ends up storing the count for all characters in freq . But since we dealing with only lower case english letters (as mentioned in constraints) the space complexity in the worst case is O(26) , which in general can be represented as O(1) . That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another article on coding questions . Today we will be solving GeeksForGeeks problem, Maximum Sum Subarray of Size K . Problem Statement: Maximum Sum Subarray of Size K Given an array of positive numbers and a positive number 'k', find the maximum sum of any contiguous subarray of size 'k' . Example 1: Input: arr = [2, 1, 5, 1, 3, 2], k=3 Output: 9 Explanation: Subarray with maximum sum is [5, 1, 3]. Example 2: Input: arr = [2, 3, 4, 1, 5], k=2 Output: 7 Explanation: Subarray with maximum sum is [3, 4]. Solution This is a classical sliding window technique problem. If you are new to sliding window concept, we would suggest you to go through this article on sliding window concept before you proceed further in this article. Algorithm Below is the step by step explanation for this algorithm: Initialization: Initialize two variables maxSum and windowSum . Both maxSum and windowSum are initially set to 0. maxSum is used to store the maximum subarray sum found so far. windowSum is used to store the subarray sum for the current window. Calculate the subarray sum for the first window: Loop through the first k elements of array arr and calculate its sum. This initial window sum forms the basis on which we further build our algorithm. Update maxSum: Since this is the first subarray sum, we update maxSum with the current windowSum . Slide the window: Now for each iteration, slide the window to right by one element and perform the following operations: Remove (subtract) the previous array element from the windowSum . Add the current element to windowSum . If current windowSum is greater than maxSum , update maxSum with current windowSum . Return the result: Once sliding window reaches the end of array, return the final value in maxSum as result. Simulation Below diagram shows a pictorial depiction of the working of this algorithm: Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Complexity Analysis Time Complexity Calculating first subarray sum: In the first loop, we calculate the sum of the first subarray window by iterating from index 0 to kth index. This has a time complexity of O(k) . Sliding the window for the remaining subarrays: For calculating the window sum of remaining subarrays, we iterate arr from 1st index to (n-1)th index ( n-k elements in total). This has a time complexity of O(n-k) . Therefore the overall time complexity of this algorithm is O(k) + O(n-k) = O(n) . Space Complexity Apart from maxSum and windowSum variables, this algorithm does not use any extra space for its computation. Therefore, the space complexity of this algorithm is O(1) . That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another article on leetcode problem solutions . Today we will be solving leetcode problem no. 209, Minimum Size Subarray Sum . This problem also features in GeeksForGeeks, Smallest subarray with sum greater than a given value . Problem Statement: Minimum Size Subarray Sum Given an array of positive integers nums and a positive number target , find the length of the smallest contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0. Example 1: Input:  target = 7, nums = [2,3,1,2,4,3] Output:  2 Explanation:  [4,3] is the minimal length subarray with sum = 7. Example 2: Input:  target = 4, nums = [1,4,4] Output:  1 Example 3: Input:  target = 11, nums = [1,1,1,1,1,1,1,1] Output:  0 Constraints: 1 <= target <= 10^9 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^4 Solution To solve this problem we will be using the sliding window technique that we discussed in our previous article . The difference here is that, in the previous solution we made use of a fixed sliding window, but here we will be using a window that expands or contracts as needed. If windowSum is less than target we expand the window (towards right) and we shrink the window (from left) if windowSum is greater than or equal to target . The logic behind this expanding and shrinking is, as per problem statement, we need a subarray sum greater than or equal to target , and when: windowSum >= target , if we expand the window, we we will only get a bigger sum (since nums is a positive numbers array). This is the reason we shrink the window. windowSum < target , if we shrink the window, we will obviously get a smaller sum. Hence, we expand the window. If this point is clear, let's now see how we can solve the problem using this logic. Algorithm Below is a step by step explanation of how this algorithm works: Initialize variables: Initialize 4 variables: minLength , windowSum , windowStart , windowEnd . minLength is used to store our result (minimum length of subarray greater than or equal to target ). This is initially set to maximum value for comparison purpose (since we want to calculate minimum length). windowSum is used to store the sum of the current window. This is initially set to 0. windowStart is used to store the starting index of our window  in nums . This is initially set to 0. windowEnd is used to store the ending index of our window in nums . This is initially set to 0. Define outer loop: Using windowEnd we loop through the nums array starting from the 0th index till the last the last index. In each iteration of the outer loop, we perform the following operations: Add the number represented by the current windowEnd index to windowSum. This step is used to expand the window (towards the right) for the case where, windowSum >= target . Define an inner loop that executes only if our current windowSum is greater than or equal to target . This loop is used to shrink our window as long as windowSum >= target . The inner loop does the following things: Since windowSum  >= target , we update our result minLength , if necessary. Since we need to shrink the window (from left), we subtract the first element in the original window from windowSum . Also, since we are discarding the first element, we increment windowStart variable. Return result: Finally, before returning the we need to handle the case when no subarray with sum greater than or equal to target exists. For such cases, our result variable minLength , will never be updated (since the execution does not enter the inner loop). Hence it's value will still be maxInt value that we had set initially. Therefore, we return 0, as mentioned in the problem statement. For all other cases, we return the value in minLength as is. Simulation Below diagram shows a pictorial depiction of the working of this algorithm: Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Complexity Analysis Time Complexity Even though we have nested loops, if you observe carefully, we process each elements in nums array at most twice, once for adding in the outer loop and once for removing in the inner loop. Hence, the overall time complexity of this algorithm is O(n) + O(n) = O(n) . Space Complexity The space complexity of this solution is O(1) , since we are not using any extra space apart from variables like minLength , windowSum , windowStart , windowEnd which require constant auxiliary space, O(1) . That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another article on leetcode problem solutions . Today we will be solving leetcode problem no. 200, Number of Islands . This problem also features in GeeksForGeeks, Number of Islands . Problem Statement: Number of Islands Given a 2D m x n array (matrix) grid containing only 1s (land) and 0s (water), count the number of islands in it. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically (not diagonally). You may assume all four edges of the grid are all surrounded by water. Example 1 Input : grid = Output : 3 Explanation : The matrix has three islands. See the highlighted cells below. Example 2 Input : grid = Output : 1 Explanation : The matrix has only one island. See the highlighted cells below. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1' . Solution Questions on island pattern are a popular choice in coding interviews. We can solve these problems efficiently using both depth first search (DFS) or breadth first search (BFS) approaches. We have explained the BFS approach in detail in another article . In this article we will be discussing the DFS solution. The idea behind DFS approach is that, as soon as we find a land cell, we go to the depth, find all the connected land cells (vertically and diagonally) and count the number of islands. Algorithm Below is a step by step explanation for the working of the algorithm: Initialization: Initialize 3 variables: row , col and count . row represents the no. of rows in the input matrix. col represents the no. of columns in the input matrix. count represent our result, count of no. of islands. Find a land cell or 1: The first step in this algorithm is to find a land cell. Starting from the (0,0) position, we start iterating through the given 2D array until we find a land cell. Each time we find a land cell, we call the DFS function and perform a recursive DFS  from this land cell, to find all the land cells connected to it, vertically and horizontally. Depth first search: For each call (in step 2) the DFS function does the following things: Check if our DFS function is within the bounds of the given 2D array. If it is not in bounds, we simply return from recursion stack. Check if the current cell is a land. Since we want to count islands we must only process land cells. If we encounter a water cell, we return from recursion stack. Next, if the current cell is a land, we mark the current cell as processed, by making it 0. This step is important and is needed to prevent recounting already processed islands. After this we recursively call the DFS function in all 4 directions (right, down, left and up) and repeat steps a-d until there are no more connected land cells left to be processed. Increment island count: Once the control returns to the main caller in step 2, we increment the count by one, since we have processed one island (set of connected land cells). Repeat island counting steps: Repeat steps 2-4 for all the land cells in the given 2D array. Return final result: Finally, return the result count after all land cells in the input array are processed. Note: The above algorithm modifies the input array to arrive at the result. If the interviewer asks you to do this without modifying the input array, you can easily modify the above algorithm by taking a boolean hashmap to keep track of the processed elements instead of modifying the given input array. Simulation Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution C Solution Rust Solution Complexity Analysis Time Complexity Nested Loop: The nested loop is used for iterating through all elements of the input 2D array exactly once. Hence, the time complexity is O(row x col) , where row and col represents number of rows and columns in grid respectively. DFS Function: The DFS function also processes each element at most once. Hence, the time complexity of the DFS function is also O(row x col) . Therefore the overall time complexity of the algorithm is O(row x col) . Space Complexity The worst case space complexity of the algorithm is O(row x col) because of the recursion call stack. The worst case occurs when all the elements of the given input array are 1s. That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another leetcode problem solutions article. In our previous article we discussed the depth first search solution for leetcode problem no.200, Number of Islands . Today let's see how we can solve the same problem using the bread first search (BFS) technique. Problem Statement: Number of Islands Given a m x n 2D binary array grid which represents of map of '1's (land) and '0's (water), return the number of islands in this grid. An island is formed by connecting adjacent lands vertically or horizontally and it should be surrounded by water. You may assume all four edges of the grid are all surrounded by water. Example 1 Input : grid = Output : 1 Explanation : The matrix has only one island. See the highlighted cells below. Example 2 Input : grid = Output : 3 Explanation : The matrix has three islands. See the highlighted cells below. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j]  is '0'  or '1' . Solution If you have not yet gone through our previous article on DFS solution, we highly recommend to you to check that out first because, it will provide you with key insights which will help you understand this problem better. Tip: DFS solutions are typically implemented using stack data structure or recursion . BFS solutions mostly involve the use of queue data structure. Algorithm Below is a step-by-step explanation for the working of the algorithm: Initialization: To begin with, we initialize 3 variables: rows , cols and islandCount . rows represents the total number of rows in grid matrix. cols represents the total number of columns in grid matrix. islandCount is used to store the result, total number of islands in grid matrix. Iterate through the matrix elements to find land cells: Traverse through each element in the input grid matrix. In each iteration perform the following steps: If the current cell is a water cell, ignore. Continue iteration. If the current cell is a land cell: Increment islandCount since we have found a island. Call the BFS function (defined in step 3). BFS function: The BFS function will be called from step 2 with the coordinates (row,col) of the land cell. For each call, the BFS function does the following things, as long as the current cell is in bounds and is a land cell : Initially add coordinates (row,col) to queue. Next, de-queue the front element from queue. Mark the current cell as processed by making it 0. Add all current cell neighbours (vertically and horizontally) to the queue. Repeat steps b, c & d until the queue becomes empty. Repeat island counting steps: Repeat steps 2-3 for all land cells in the given input grid . Return final result: Finally, return the result islandCount , after all the cells in the input matrix are processed. Simulation Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution C Solution Rust Solution Complexity Analysis Time Complexity Grid Traversal: The nested loop iterates over all elements of the input 2D array once, this results in a time complexity of O(rows x cols) . BFS Function: The BFS function also process each element in the input array at most once, so time complexity is O(rows x cols) . Therefore the overall time complexity of this algorithm is O(rows x cols) . Space Complexity The space complexity is dependent on the queue used. In the worst case when all cells in grid are land cells, the queue can grow upto min(rows, cols) . Thus the space complexity of this solution is O(min(rows, cols)) . That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another article on leetcode problem solutions . Today we will be solving leetcode problem no. 26, Remove Duplicates from Sorted Array . Problem Statement: Remove Duplicates from Sorted Array Given an integer array nums sorted in ascending order , move all single occurrences of elements in it to the beginning of the nums array in-place . The original order of the numbers in the final result array must be maintained for all the moved single occurrences. If there are k unique elements in nums , your final output must be computed by taking into account the following considerations: Modify nums array such that the first k elements in nums are all unique numbers and in the same order as in the original nums array. Return k . Example 1 : Input: [2, 3, 3, 3, 6, 9, 9] Output: 4 Explanation: The final array after moving the unique elements will be [2, 3, 6, 9, _, _, _]. Example 2 : Input: [2, 2, 2, 11] Output: 2 Explanation: The first two elements after moving elements will be [2, 11, _, _]. Constraints: 1 <= nums.length <= 3 * 10^4 -100 <= nums[i] <= 100 nums is sorted in non-decreasing order. Solution The problem statement is pretty straightforward. We are asked to modify the given nums array by grouping every single occurrence of each element (one copy of each element) at the beginning of the array and in the same order as in the original array. We don't care about the position of the rest of the elements and they can be in any order. Also, we have to do this in-place, meaning we must arrive at the final result just by manipulating the nums array, we cannot use any extra space. This problem can be solved using the two pointer technique . The idea is to make use of two pointers: uniqueIdx and i . uniqueIdx is used to keep track of the last unique element index in nums . i is used to iterate through the nums array. As and when we find a unique number we move it to the beginning of the nums array (pointed by uniqueIdx ) and increment uniqueIdx . Let's see how this works in detail. Algorithm Below is a step by step explanation for the working of the algorithm: Initialization: As mentioned earlier, we will be using two pointer technique. Initialize two variables representing two pointers: uniqueIdx , i . uniqueIdx is used to keep track of the last unique number index in nums array. uniqueIdx is initially set to zero (points to 0th index of nums array). i is used to iterate through the nums array. i starts from the 1st index. Modify nums array in-place: Using i , start iterating through the nums array from 2nd element. In each iteration, compare current element (ith element) with the last unique element (represented by uniqueIdx ): If current element is equal to the last unique element, no operation, continue iterating. If current element is not equal to the last unique element, that means we have found a unique element (first occurrence for that element). Therefore, increment uniqueIdx and copy the current element to the uniqueIdx index. Return result: Finally, return uniqueIdx + 1 as result (+1 because we need to return the total number of unique elements, but uniqueIdx is an index which starts from 0). Simulation Below is a pictorial depiction of the working of the algorithm: Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution C Solution Rust Solution Complexity Analysis Time Complexity Time complexity of this algorithm is O(n) as we iterate through the entire array once to find the result. Apart from this we only perform constant time operations which have no impact on the overall time complexity. Space Complexity Space complexity is O(1) since we modify nums array in-place and do not use any extra space which is dependent on the input size. That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another article on   leetcode problem solutions . Today we will be solving leetcode problem no.217 Contains Duplicate . This question also features in GeeksForGeeks problem set, Check if array contains duplicates . Problem Statement: Contains Duplicate Given an array of integers nums , write an algorithm that returns true if any value appears at least twice in the array, and return false if every element is unique. Example 1 : Input: nums= [1, 2, 3, 4] Output: false Explanation: There are no duplicates in the given array. Example 2 : Input: nums= [1, 2, 3, 1] Output: true Explanation: The given array contains duplicates at indices 0 and 3. Constraints: 1 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 Solution There are a couple of popular ways to solve this problem. One approach is to using sorting. When we sort the given array, if there are any duplicates they will be placed adjacent to each other. Then we can easily iterate through the array and find out if there are any duplicates by comparing adjacent elements. However, since we need to sort the array, this algorithm has a time complexity of O(n log n) . If we are looking for a better time complexity, hashmap is the way to go! We can use the hashmap data structure to efficiently detect duplicates. Let's see how this works. Algorithm Below is the step-by-step explanation of the working of the algorithm: Initialization: Initialize a hashmap, seenNums , that takes a integer key and boolean value. Check for duplicates: Next, iterate through the given nums array from start to end. In each iteration perform the following operations: Check if we have encountered (seen) the current number before this iteration, by checking if it is present in the hashmap. If it is present in the hashmap (hashmap value for the current number is true ), it means we have found a duplicate. Therefore, we return true as result. If hashmap does not have this number (hashmap value for the current number is false ), we add the current number as hashmap key and value as true , to indicate that we have seen this number, so that it can be used in the next iterations to check duplicates. Return false: If we reach the end of array, it means we have not found any duplicates, all the elements in the nums array are unique. Therefore, we return false indicating there are no duplicates. Simulation Below diagram show a pictorial depiction of the working of the algorithm: Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Rust Solution Complexity Analysis Time Complexity In the worst case, when all the elements in the nums array are unique, the algorithm iterates through the entire array to find the result. Therefore, in n is the size of the given input array, the time complexity is O(n) . Space Complexity As we iterate through the input array we also need to add it to the hashmap if it is not a duplicate. In the worst case, if all the elements in the input array are unique, we will end up storing all the elements in nums array in the hashmap. So, in the worst case this algorithm has a space complexity of O(n) . That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another article on leetcode problem solutions . Today we will be solving leetcode problem no. 268 Missing Number . This question is similar to Find All Numbers Disappeared in an Array problem that we discussed in another article. Problem Statement: Missing Number Given an integer array nums , containing n distinct numbers in the range 0 to n , return the only number in the range that is missing (Return the missing number, not index). Example 1 : Input: [4, 0, 3, 1] Output: 2 Explanation: Range is 0 to 4. 0, 1, 3, 4 are present in array. 2 is the missing number. Example 2 : Input: [8, 3, 5, 2, 4, 6, 0, 1] Output: 7 Constraints: n == nums.length 1 <= n <= 10^4 0 <= nums[i] <= n All the numbers of nums are unique . Solution There are multiple approaches to solve this problem. In this article we will be discussing one of the most efficient ways to solve this problem, by using cyclic sort technique . Cyclic sort technique is one of the fastest ways to solve problems involving missing numbers in a given range. As you can see, it is also evident from the from the leetcode submission results: The idea behind cyclic sort is simple, for an unsorted array containing n numbers in the range 1 to n, cyclic sort iterates through the given array, and in each iteration we place one of the numbers in its correct position in the array. We do this repeatedly until the array is sorted. Let's see how this works in detail. Algorithm Below is a step-by-step explanation for the working of the algorithm: Cyclic sort: Iterate through the elements of the given nums array from start to end. In each iteration perform the following steps: Calculate the correct index where the current number should be placed. Since there are n elements and the range is 0 to n , nth number should be placed at (n-1)th position in the array, i.e. 1 should be placed at 0th index, 2 should be placed at 1st index, 3 should be placed at 2nd index and so on. Therefore the formula to calculate correct index is: correctIdx = current number - 1 or correctIdx = nums[i] - 1 Once the is correctIdx calculated, check if the current number is in its correct position in the array. If the current number is not in it's correct position, we move it to the correct position by swapping the number at the current index with the number at the correctIdx . If the current number is in it's correct position, we increment current index and move to the next iteration. Repeat steps a and b until all the elements in the nums array are placed at the correct position. Find the missing number: After step 1, cyclic sort places all the elements in its correct position, except the missing number . So, we iterate through the array once more from start to end and in each iteration we check if the current index has the correct number. If the current index does not have the correct number, that means we have found the missing element. Therefore, we return the missing number, i + 1 as result. Note: In the formula for calculating the correct index, correctIdx = nums[i] - 1 , since the range is 0 to n , we need to handle an edge case where nums[i] = 0. For such cases, correctIdx = -1, if we encounter this, we need to continue iterating without performing any operation. We need not handle this edge case if the range was from 1 to n . Simulation Below is a pictorial depiction of the working of the algorithm: Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Rust Solution Complexity Analysis Time Complexity Cyclic Sort (First loop): Since we are not incrementing current index i for every iteration, it might seem that the time complexity is not linear. However if you observe carefully, in each iteration we either swap and place an element in its correct position or increment i if the number is already in its correct position. So, overall our algorithm makes a maximum of O(n) + O(n-1) iterations, which although is more than n iterations, it is asymptotically equivalent to O(n) . Finding the missing number (Second loop): Finding the missing number takes O(n) time as we having to iterate through the given nums array and in the worst case when last number is missing we will end up iterating entire the nums array. Therefore, the overall time complexity is O(n) . Space Complexity Space complexity of this algorithm is O(1) since it is an in-place algorithm and we are not using any extra space. That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! Welcome back to another article on leetcode problem solutions . Today we will be solving leetcode problem no.448 Find All Numbers Disappeared in an Array . Problem Statement: Find All Numbers Disappeared in an Array Given an integer array nums , where nums[i] is in the range nums[1,n] , return all the missing numbers in the range [1,n] that do not appear in nums . Example 1 : Input: [2, 3, 1, 8, 2, 3, 5, 1] Output: 4, 6, 7 Explanation: The given array has numbers in the range 1 to 8. 4, 6 and 7 are the numbers missing from the given range. Example 2 : Input: [2, 4, 1, 2] Output: 3 Example 3 : Input: [2, 3, 2, 1] Output: 4 Constraints: n == nums.length 1 <= n <= 10^5 1 <= nums[i] <= n Solution This question is an extension of the Missing Number problem that we discussed in our previous article . We can use the same cyclic sort technique to solve this problem as well, with slight modification. If you have not yet gone through that article we suggest you to go through that one first because it will help you understand this one better. Let's see how the algorithm works in detail. Algorithm Below is a step-by-step explanation for the working of the algorithm: Cyclic sort: The goal of cyclic sort is to put all numbers in its correct position in the array. 1 is placed at 0th index, 2 is placed at 1st index, 3 is placed at 2nd index and so on. Iterate through the elements of the array from start to end. In each iteration we perform the following operations: Calculate the correct index where the current element should be placed. We can use the below formula to calculate correct index: correctIdx = current number - 1 Next check if the current element is in it's correct position ( nums[i] == nums[correctIdx] ): If yes, we don't have have to do anything, just increment the current index and move to the next iteration. If no, move the current number to its correct position by swapping the current number with the number at the correct index. Repeat steps a and b until we reach the end of nums array. Find all the missing numbers: Iterate through the array once again from start to end. In each iteration check if the current number is in its correct position: If yes, do nothing, continue to next iteration. If no, it means we have found a duplicate. Therefore add the number that was actually supposed to be here (current index + 1) to the result array (let's call it missingNums ). Return final result: Finally, return missingNums array as result. Simulation Below is a pictorial depiction for the working of the algorithm: Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Rust Solution Complexity Analysis Time Complexity Cyclic sort (First loop): Time complexity for placing the elements in its correct position using cyclic sort takes O(n) time complexity. We explained why it is O(n) in greater detail in the time complexity section in the Missing Number article . Finding the missing numbers (Second loop): For finding the missing numbers, we iterate through the given nums array from start to end. Hence time complexity is O(n) . Therefore the overall time complexity of this algorithm is O(n) . Space Complexity Space complexity is O(1) since it is an in-place algorithm and does not use any extra space. That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries. If you enjoyed this article, please subscribe to our website and Youtube channel . Your support inspires us to create more such articles in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section . There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .