Hello Code Recipian! Welcome back to another article on   leetcode problem solutions . Today we will be solving leetcode problem 1189. Maximum Number of Balloons . Problem Statement: Maximum Number of Balloons Given a input string text , use the characters of text to form as many instances of the word "balloon" as possible. You are only allowed to use each character at most once. Return the maximum number of times "balloon"  can be formed. Example 1: Input:  text = "nlaebolko" Output:  1 Explanation: nla e bol k o Example 2: Input:  text = "loonbalxballpoon" Output:  2 Explanation: loonbal x ball p oon Example 3: Input:  text = "leetcode" Output:  0 Constraints: 1 <= text.length <= 10^4 text consists of only lower case English letters. Solution We can use the hashmap to efficiently solve this problem in linear time. The idea is to count the frequency of characters in input string and using this character count determine how many times the word "balloon" can be formed. Let's see how this works in detail. Algorithm Below is a step-by-step explanation for the working of the algorithm: Initialization: To begin with, initialize a hashmap charCount that takes a character key and an integer value. This hashmap is used for counting the frequency of each character in the input string. Count characters: Iterate through the characters of the input string text from start to end. In each iteration we increment the current character count by one. Count instances of balloon: Next step is to use the frequencies we got in the previous step, to calculate how many times we can form the word "balloon". To get this we perform the following steps: Initialize result variable: Initialize a variable minCharCount , this is our result variable, this should be initially set to some max value. Normalize charCount for 'l' and 'o': Since characters 'l' and 'o' appear two times in the word "balloon", we divide 'l' and 'o' by 2 to normalize it. This division would mean, now we need a single occurrence of the letters 'b', 'a', 'l', 'o' and 'n' in order to form one instance of the word "balloon". This division is done in order to make our calculation simpler for the next steps. Calculate maximum no. of instances of balloon: Next in order to get the final result, we have to find the minimum of the charCount among 'b', 'a', 'l', 'o' and 'n'. The intuition behind this is that, in order to form the word balloon we need 'b', 'a', 'l', 'o' and 'n' to be present at least one time each. For forming 1 instance of balloon, we need 1 'b', 1 'a', 2 'l', 2 'o' and 1 'n'. But, since we have divided 'l' and 'o' by 2, we need just 1 occurrence even for 'o' and 'l'. Therefore for forming once instance of balloon we need 1 occurrence of 'b', 'a', 'l', 'o' and 'n'. For forming two instances of balloon we need 2 occurrences of 'b', 'a', 'l', 'o' and 'n'. Even if one of the these letters has count = 1 we can only form one instance of balloon. That is the idea behind taking minimum of character counts. The maximum number of instances of balloon that can be formed depends on the minimum of the frequencies among 'b', 'a', 'l', 'o' or 'n'. Return result: Finally we return the minCharCount as result. 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 Scala Solution Complexity Analysis Time Complexity Time complexity of this solution is O(n) , where n is the length of string text . This is because we iterate each character of text for counting the frequency of characters. Apart from this all are constant time operations. Space Complexity Even though we use a hashmap for storing the character count, as per the problem constraints text can only have lower case English letters. Therefore, in the worst case the maximum number of elements that the hashmap can have is 26 . Hence the space complexity 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! Another day and we are back with another article on leetcode problem solutions . In this article we will be solving leetcode 136. Single Number . Once you get a good grip of this problem, you should be able to solve advanced level problems like 260. Single Number III , a very popular MAANG interview question. Let's dive into the problem statement! Problem Statement: Single Number Given a non-empty array of unsorted integers nums , every element in nums appears twice except for one number. Find that single number. Your solution must have a running time complexity of O(n) and use only constant extra space. Example 1: Input:  nums = [2,2,1] Output:  1 Example 2: Input:  nums = [4,1,2,1,2] Output:  4 Example 3: Input:  nums = [1] Output:  1  Constraints: 1 <= nums.length <= 3 * 10^4 -3 * 10^4 <= nums[i] <= 3 * 10^4 Each element in the array appears twice except for one element which appears only once. Solution One approach that might straight away come to your mind looking at this problem is to use a hashmap. We can use the hashmap to keep track of the frequencies of each element in input array and using these frequencies we can determine the single number that is missing. But, since we are using hashmap, space complexity of this solution is O(n) . A more effective way to tackle this problem is to utilize the characteristics of bitwise XOR operation. XOR has the following properties: If we XOR a number with itself, we get 0. If we XOR a number with 0, we get back the same number. Num1 Num2 Num1 XOR Num2 0 0 0 0 1 1 1 0 1 1 1 0 We can take these XOR properties to our advantage in solving the given problem. The idea is simple, we perform XOR operation on all the numbers in the given input array nums . Once we do this, all numbers that appear twice will cancel each other out and we will be left with the number that appears only once. Let's see how this works in detail. Algorithm Below is a step-by-step explanation for the working of the algorithm: Initialization: To begin with, we create a result variable to store our result and initialize it with the value of the first element in nums . Find the single number: Next, iterate through the nums array from start to end. In each iteration, XOR result with the current number. We must repeat this until we reach the end of array. Return the final result: At the end of step 2, we would have performed XOR operation on every number in nums . What this will effectively do is that, all the numbers that appear 2 times in nums will cancel out each other (result will be 0). And the number that appears only once, when XORed with this 0, will give back the same number. Hence, at the end of step 2, the result variable will have the required result (number that appears only once). Therefore, we return this as our result. 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 Scala Solution Complexity Analysis Time Complexity In order to perform XOR operation on all elements, we will have to iterate through every element in nums array. Therefore the time complexity of this solution is O(n) . Space Complexity The space complexity of this algorithm is O(1) as 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 bring out more such articles in 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 solution to LeetCode 136. Single Number . Today we will be solving a variation of this problem 260. Single Number III . This is a very popular FAANG interview question. If you have not yet gone through our article on 136. Single Number , we recommend you to go through that one first, it will help you establish a solid base to solve this problem. Problem Statement: Single Number III Given an integer array nums , every element in nums appears exactly twice except for two numbers that appear only once. Find these two numbers. You can return the answer in any order . You must write an algorithm that runs in linear time and uses only constant extra space . Example 1 : Input: [1, 4, 2, 1, 3, 5, 6, 2, 3, 5] Output: [4, 6] Explanation: 4 and 6 appear only once in the input array. Example 2 : Input: [ 1, 2, 1, 3, 2, 5 ] Output: [3, 5] Constraints: 2 <= nums.length <= 3 * 10^4 -2^31 <= nums[i] <= 2^31 - 1 Each integer in nums will appear twice, only two integers will appear once. Solution For solving the Single Number problem we used the XOR approach. To solve this problem as well, we can use the same XOR approach with a slight modification. Before we begin, a quick recap on XOR properties: If we XOR a number with itself, we get 0. If we XOR a number with 0, we get back the same number. Algorithm Below is a step-by-step explanation for the working of the algorithm: Initialization: Create a variable num1XorNum2 , and initialize it with the value of the first element in nums array. Perform XOR on all elements in nums: Iterate through the nums array from start to end. In each iteration we perform the XOR of the current element with num1XorNum2 . Perform step b for all elements in nums . At the end of step b, all numbers that appear twice cancel each other out, leaving behind the XOR of only two numbers that appear only once, and at the end of step 2 this is what will be stored in num1XorNum2 . Separate Num1 and Num2: In order to return the result, we need to separate out num1 and num2 from num1XorNum2 . How can we do this? We know num1 != num2. If we think logically, if num1 and num2 are different, at least one of the bits in these numbers must be different. If we can find out any one bit in these 2 numbers which is different, we can use this information to separate them into two different buckets or groups based on whether this bit is set or not set (1 or 0), thereby placing num1 and num2 along with other numbers in two different buckets. Then we can perform XOR independently on these two groups leaving behind only num1 and num2. Separating num1 and num2 is done in 2 parts. Let's discuss each of these steps in detail: Find out the set bit in num1XORNum2: So, our first task to find out any one bit in num1XorNum2 which is set (or 1). The logic behind doing this is, XOR returns a set bit only when the other bit is different (only 0 1 =1 and 1 0 = 1 ). So if we can somehow find a set bit in num1XorNum2 we know for sure that, this particular bit is different in both num1 and num2 (since num1XorNum2 is an XOR of num1 and num2). We can find out the set bit by using AND operator properties. As you can see AND operation returns 1, only one both are one. We can use this to our advantage to determine the set bit (1 bit) in num1XorNum2 . We just need to find any one of the set bit in num1XorNum2 , it can be in any position. For the sake of simplicity, we will find the right most set bit in num1XorNum2 . For this we create a variable rightMostSetBit and initialize it to 1. Next we perform AND operation on num1XorNum2 and rightMostSetBit . If it is not a set bit it will return 0. If it is a set bit it will return a non-zero result. We check every bit in num1XorNum2 by left shifting rightMostSetBit in each iteration. Put numbers into two separate groups: Once we know the set bit in num1XorNum2 , next step is to group numbers in nums based on this bit. All numbers in nums that have this bit set are put in one group. All numbers in nums that have this bit not set, we put in another group. With numbers divided into two groups, half of the numbers in nums including num1 are now placed in one group and other half including num2 are placed in another group. Now if we take the XOR of numbers in these two groups separately, since num1 and num2 in two different groups, all numbers in each group that appear twice will cancel each other out and num1 and num2 will be left behind. Return result: Now we have separated num1 and num2. These are the two numbers which appear only once in nums , and this is our required result. 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 Scala Solution Complexity Analysis Time Complexity First loop: In the first loop we iterate through all the elements of the array to calculate XOR of elements. This has a time complexity of O(n) . Second loop: The second loop runs until a set bit is found. In the worst case, when the maximum size of the number can go upto 32 bits (from problem constraints). So, in the worst case the loop will iterate upto 32 times, so it has a constant time complexity of O(1) . Third Loop: The third loop also iterates through the entire array once again to perform XOR. This also has a time complexity of O(n) . Therefore, the overall time complexity of this algorithm is O(n) + O(1) + O(n) = O(n). Space Complexity Space complexity for this solution is O(1) as we are not using any extra space. That brings us to the end of this article. We appreciate the time you have taken to read through it. If you have 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 bring out more such articles in 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 to back to another article on LeetCode problem solutions . Today we will be solving LeetCode problem 125. Valid Palindrome . Let's dive into the problem statement. Problem Statement: Valid Palindrome Given a string s , return true if it is a palindrome, otherwise return false . A given sentence is a palindrome if, after converting all upper case letters into lowercase and after removing all the non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Example 1 : Input: sentence = "A man, a plan, a canal, Panama!" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. Example 2 : Input: sentence = "No lemon, no melon!" Output: true Explanation: "nolemonnomelon" is a palindrome. Example 3 : Input: sentence = "Never odd or even." Output: true Explanation: "neveroddoreven" is a palindrome. Constraints: 1 <= s.length <= 2 * 10^5 s consists only of printable ASCII characters. Solution This problem can be efficiently solved using the two pointer technique . The idea is to use two pointers, one pointing to the start and one to the end, compare the characters and move the pointers inwards in each iteration. If all characters match then it is a palindrome, otherwise it is not. Let's see how this works in detail. Algorithm Below is a step-by-step explanation for the working of the algorithm: Initialization: Initialize two variables: start , end . start is the index variable used to iterate the string from the start. start is initialized to 0 to point to the first element in the string s . end is the index variable used to iterate the string from the end. end is initialized to the index of the last element in the string s . Compare start and end characters: We use the start and end variables to iterate through s . In each iteration, we perform the following steps: As long as the current character pointed by start is not an alphanumeric character, ignore the current character, increment start . As long as the current character pointed by end  is not an alphanumeric character, ignore the current character, decrement end . At the end of step a and b , both start and end will be pointing to a alphanumeric character. Convert both these characters to lower case and compare the characters pointed by start  and end . If they are matching, continue iterating. If they are not matching, the given string s is not a palindrome. Therefore, straightaway return false as your result. Return result: If the execution comes out of the main loop after iterating through all the characters in the string s , that means s reads same forward and backward and it is a palindrome. Therefore, return result as true . 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 C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Scala Solution Rust Solution Coming soon... Complexity Analysis Time Complexity Even through we make use of nested loops, if you observe carefully we process each character in string s only once. If n is the length of the string s , in the worst case, when the given string is a palindrome, we end up iterating through all the characters of the string s . Thus the time complexity of this algorithm is O(n) . Space Complexity The algorithm uses couple of extra variables start , end for its operation, these variables only use constant extra space. Hence, the space complexity of the algorithm is O(1) . That brings us to the end of this article. We appreciate the time you have taken to read through it. If you have 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 bring out more such articles in 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 .