Hello Code Recipian! Here we meet again with yet another LeetCode problem solution . Today let's solve LeetCode problem 234. Palindrome Linked List . Let's check out the problem statement! Problem Statement: Palindrome Linked List Given the head of singly linked list, return true if it is a palindrome, false otherwise. Note: A palindrome is a sequence that reads the same forward and backward. Example 1: Input:  head = [1, 2, 2, 1] Output:  true Explanation: Given linked list node values form a palindrome. Hence output is true. Example 2: Input:  head = [1, 2, 3, 4] Output:  false Explanation:  Given linked list is not a palindrome. Solution This is another singly linked list problem which can be solved optimally using the slow and fast pointer technique which we have discussed in some of our previous articles like 141. Linked List Cycle , 142. Linked List Cycle II , Finding The Middle Element . Algorithm Below is detailed explanation for the working of the algorithm: Find the middle node: Initialize two pointer variables: slow , fast . Initially both slow  and fast  point to the head  node. Traverse through the linked list using slow , fast pointers. In each iteration perform the following steps: Move slow pointer ahead by one node. Move fast pointer ahead by two nodes. When the fast pointer reaches the last node, the slow pointer will reach the middle node of the linked list. Reverse second half of linked list: Now that slow pointer points to the middle node of the linked list, the next step is to reverse the second half the list i.e. all nodes starting from slow pointer. If you are looking for a detailed explanation on how to reverse a linked list, you can check our article on How To Reverse A Linked List . The idea behind reversing the 2nd half is that, once we have the second half reversed, we can simultaneously traverse the list from two extreme ends and compare corresponding node value to check if it is a palindrome or not. Compare first and second half: The reverse() function returns the last node (in the original list) as the head node for the reversed second half. Let's call this l2Head . To begin with initialize two pointers variables: curr1 and curr2 . Initially, curr1 points to the head node of the first half and curr2 points to the l2Head . Initialize a boolean result variable to store our final result (i.e. palindrome or not). Initially it is set to true . Now traverse through the first and second lists using the curr1 and curr2 pointers respectively. In each iteration, Compare the corresponding curr1 and curr2 node values. If at any point during the traversal, if node values do not match, set result to false and stop traversal. Revert second half to original form: Now since we are done processing the linked list, we restore the second half that we reversed earlier, by reversing it back again. Return final result: Return value in result as the final result. 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 Complexity Analysis Time Complexity Finding the middle node: We need to traverse through the list using slow and fast pointer in order to get the middle node. So the time complexity is O(n) . Reversing the second half: If n is the number of nodes in the given linked list, it takes n/2 iterations to reverse the second half. So the time complexity is O(n) . Check if palindrome: Checking for palindrome also takes O(n) time as we have to compare every node value in first half with the corresponding value in the second half. Restoring the list: Before returning result we revert the list to original form. This also takes O(n) time. Overall time complexity: Considering all the above factors, the overall time complexity of this solution is O(n) + O(n) + O(n) + = O(n) . Space Complexity Since we only manipulate the pointers in the given linked list and do not use any extra space, the space complexity is O(1) . That concludes this article. But hey! Don't stop here! Master more problems on linked lists and palindrome. Explore now: 141. Linked  List Cycle 142. Linked  List Cycle II Finding The Middle Element 125. Valid Palindrome  - LeetCode Fastest Solution 680. Valid Palindrome  II - LeetCode Fastest Solution 9. Palindrome Number Code Recipe Limited Time Offer:   Enjoy a 100% discount on the Code Recipe Membership Plan. Sign up now to access exclusive premium content for free. Act fast—offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Hello Code Recipian! In our last article we discussed the solution for LeetCode 141. Linked List Cycle . Today let's solve an extension of this problem, LeetCode 142. Linked List Cycle II . If you haven't read the earlier article yet, we strongly recommend reading it first before diving into this one. This article is part of our LeetCode problem solutions series. So hey, don't stop here! Make sure you check them out after you are done here! Problem Statement: Linked List Cycle II Given the head node of a linked list, return the node where the cycle starts. If cycle does not exist, return null . Do not modify the linked list. Example 1 Input:  head = [3, 2, 0, -4] Output: Node with value 2 Explanation:  Cycle exists in the given linked list and it begins at node with value = 2. Example 2 Input:  head = [1, 2, 3, 4] Output: Null Explanation:  Linked list does not contain any cycle. Constraints The number of the nodes in the list is in the range [0, 10^4] . -10^5 <= Node.val <= 10^5 Solution This problem can be efficiently solved using the Floyd's Cycle Detection algorithm that we discussed in our previous article . Algorithm Initialization: Initialize two pointer variables: slow , fast and point both of them to the head node of the given linked list. Linked list traversal (detect cycle): Traverse through the linked list using the slow , fast pointers. In each iteration perform the following steps: Move the slow pointer one node at a time. Move the fast pointer two nodes at a time. Check if slow pointer is equal to fast pointer: If at any point during the traversal, if slow is equal to fast , it means we have found a cycle. Find the cycle start node by calling cycleStart() function. Return the cycle start node as result. If slow is not equal to fast , continue iterating. Finding the cycle start node (cycleStart() function): Once a cycle is found, in order to get the starting node of the cycle: Let the fast pointer point to the node where slow and fast met. Point the slow pointer to the linked list head node. Now move both slow and fast pointers together, 1 step at a time. The node at which slow and fast meet again is the starting node of the cycle. Hence, return this node as result. Return null result: If the execution comes out of the main loop without returning, it means the given linked list does not contain a cycle. Therefore return null node as result. Why this approach works In order to get the result we point slow to head and fast to the meeting point of slow and fast and they move them by one step to meet at the starting node. Let's understand the intuition behind this: Let's denote the following: L: Distance from the head node to the node at which the cycle starts. C: Be the length of the cycle. K: Distance from the start of the cycle (cycle start node) to the node where slow and fast pointers meet. Since fast  pointer moves at twice the speed of slow  pointer, by the time they meet, fast  pointer would have traversed twice the distance of slow  pointer. Let's denote the total distance traversed by the slow  pointer till the meeting point as d . Then the distance traversed by the fast  pointer to reached the meeting point is 2* d . At the point where two pointers meet: Distance travelled by slow pointer = L + K . Distance travelled by fast pointer = L + K + n * C . n is the number of full cycles (laps) completed by the fast pointer within the cycle before meeting. Setting up the equation: 2 * (L + K) = L + K + n * C Simplifying the above equation we get: L + K = n * C or L = n * C - K The above equation means, the distance from head of the list to the start of cycle, is equal to the distance from the meeting point of slow and fast to start of the cycle. And that is why, when we position slow pointer at the head and fast pointer at the meeting point and move them one node at a time, they meet at the start node of the cycle. 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 Complexity Analysis Time Complexity Detecting the cycle: Detecting the cycle takes O(n) time complexity (to understand this in detail please to refer our previous article ), where n is the total number of nodes in the linked list. Finding cycle start node: For finding the cycle start node we initially point slow to head node and fast to the meeting point node and then move slow and fast again until they meet: This takes O(n-C) time, C is the length of the cycle. Overall time complexity: Combining all the above analysis, overall time complexity is O(n) + O(n-C) = O(n) . Space Complexity Space complexity of this algorithm is O(1) as we are not using any extra space. That brings us to the end of article. Do check out our other articles on LeetCode problem solutions . If you found this article helpful please consider signing up to Code Recipe. That's all for today, see you next time! Happy Coding! 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 .

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. Do not stop here! Master these problems on palindromes: 125. Valid Palindrome - LeetCode Fastest Solution 680. Valid Palindrome II - LeetCode Fastest Solution 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 .

Welcome back Code Recipian! Today, we'll tackle a popular coding interview question, LeetCode problem 141. Linked List Cycle . Having a solid understanding of this problem will help you solve advanced questions like 142. Linked List Cycle II . If you are someone who is new to linked list data structure, we recommend you to go through our article on linked list fundamentals before proceeding further in this article. This article is part of our LeetCode problem solutions series, so make sure to check out the other articles in this series once you are done with this one 😊. Let's jump into the problem statement! Problem Statement: Linked List Cycle Given the head node of a singly linked list, determine if the linked list has a cycle in it. A linked list has a cycle if some node in the list can be reached again by continuously following the next pointer. Return true if there is a cycle in the linked list. Otherwise, return false . Example 1: Input:  head = [3, 2, 0, -4] Output:  true Explanation:  Linked list has a cycle, node with value -4 connects back to the 2nd node with value 2. Example 2: Input:  head = [1, 2, 3, 4] Output:  false Explanation: Given linked list does not have a cycle. Constraints: The number of the nodes in the list is in the range [0, 10^4] . -10^5 <= Node.val <= 10^5 Solution This is a classic singly linked list problem and a very popular one in coding interviews, especially at the mid and entry levels. It requires you to have a good understanding of linked lists and basic pointer manipulation. We will be using Floyd's Cycle Detection algorithm (also known as Tortoise and Hare Algorithm), a widely used technique for detecting cycles in linked list. The idea behind this algorithm is that, if we make use of two pointers: slow , fast and traverse through the list by moving the fast pointer at twice the speed of slow pointer, if a cycle exists, these two pointers are guaranteed to eventually meet at some point within that cycle. Why this approach works? This approach works because of the varying speeds of slow and fast pointers. Since one pointer moves slower than the other, once both of them enter the loop, the fast pointer at some point must overtake the slow pointer and that's when they meet. This approach though conceptually simple and straight forward, is remarkably efficient both in terms of time and space complexity. Let's explore in detail how this works. Algorithm Below is a detailed explanation for the working of the algorithm: Initialization: Initialize two pointers: slow , fast . Initially both slow and fast point to the head node. Linked list traversal: Traverse through the linked using slow and fast pointers. In each iteration, Move slow pointer one step at a time (one node at a time). Move the fast pointer two steps at a time. Cycle Detection: If at any point during the traversal if slow  pointer becomes equal to fast  pointer, it means we have found a cycle, so return true  as result. If the loop exits without the pointers meeting, the list has no cycle. So, return false . Simulation Below diagram show a step-by-step simulation 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 Scala Solution Complexity Analysis Time Complexity If there is no cycle: If n is the number of nodes in the given linked list, if there is no cycle, the fast pointer takes n/2 iterations to reach the end of the list. Therefore the time complexity is O(n) . If there is a cycle: Let's analyze this case in a bit more detail. n is the total number of nodes in the linked list. Let us assume that the cycle starts after m nodes and let k be the length of the cycle. fast pointer moves at twice the speed of slow pointer and if there is a cycle, slow and fast meet within the cycle. The number of iterations required for them to meet is proportional to length of the cycle k . We know for sure that k <= n . Hence, the time complexity, though it might take a few more iterations compared to linked lists not having a cycle, it is still O(n) . Thus in general, the total time complexity is O(n) . Space Complexity We only use two extra variables slow and fast , both of which use a constant extra space. Apart from this we do not use any extra space. Hence the overall space complexity is O(1) . We hope this article has provided valuable insights. Thank you for taking the time to read it. If you have any questions or comments, please don't hesitate to share them below. We're always eager to engage with our readers and answer any inquiries you may have. To stay updated on the latest articles and receive exclusive content, consider subscribing to our website and Youtube channel . Your support fuels our passion for creating informative and engaging content. Special Offer: For a limited time, enjoy a 100% discount on the Code Recipe Membership Plan. Sign up now for free access to exclusive premium content. Don't miss out on this incredible opportunity! - Join now

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. Note 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: Container With Most Water ​ 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. 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 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). Video If you are looking for a video explanation for Container With Most Water problem, you can checkout the video in our Code Recipe YouTube channel: 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 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 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 .

This is another article in the series leetcode problem solutions and this article is a solution to leetcode 15 three sum problem. We solved the two sum problem in our earlier article , and this problem in some ways is a continuation of the two sum problem. So, if you have not yet solved the two sum problem we advice you to do so because it will help you understand the 3 sum problem better. Problem Statement Given an array of integers, nums, return all the triplets in the given array nums[i], nums[j], nums[k] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice: The solution set must not contain duplicate triplets. Example Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Example 2: Input: nums = [0] Output: [] Solution Let us try to understand the problem statement. The first part of the problem statement is clear, we are asked to find out all the triplets in the given array whose sum is equal to zero. A triplet is nothing but a set of three numbers in the given array. For example, if nums=[1,2, 3,4] is the given array, [1,2,3] [2,3,4] [1,3,4] etc. are triplets. What does the condition i != j, i != k, and j != k mean? It means that we are not allowed to reuse any number from the array within a triplet. Example, for the given array nums = [1,2,3,4], triplets [1,1,1] or [1,1,2] or [1,2,2] etc. are not considered valid triplets. The last condition that we need to consider is that we cannot have duplicate triplets in our final result. Example if [-2,-2,0,2] is the given array, we can only consider one of [-2,0,2] from indices 0, 2, 3 and 1, 2, 3 in our final result. The most simple and straight forward solution to this problem is to use the brute force approach. In brute force approach we find every possible triplet from the given array, check if its sum is equal to zero and return the result (ensuring there are no duplicate triplets in the result). However, the time complexity of this solution is O(n^3) as we have to run 3 nested loops in order to implement this. Three Pointer Approach We can use a variation of the two pointer technique to solve this problem with a better time complexity compared to the brute force approach. The idea is to sort the array, use three pointer variables tp process the triplets. We fix the outer loop and move the two pointers (indexes) of the inner loop inwards to arrive at the result. The intuition behind this algorithm is simple, when we sort the array all the duplicate elements are grouped together. And as we traverse the array, if we use two pointers from left and right, we can easily avoid duplicate triplets. For example is nums = [-2, 1, -3, 5, -3, 5] is the given array, when we sort this array we get: nums = [-3, -3, -2, 1, 5, 5]. As you can see all the duplicate elements [-3, -3] and [5,5] are grouped together. During our processing, if we consider all of these duplicate elements, it would result in duplicate triplets like [-3, -2, 5] and [-3, -2, 5]. We can avoid this if we use two pointers to traverse the array from either sides (one from start and one from end). We process only the 1st element and skip all the duplicate elements that appear after it. Algorithm For the given input array nums of size n this approach does the following steps: First step is to sort the given array nums. Sorting the array helps us identify duplicate triplets using our loops by skipping certain numbers that would result in duplicate triplets. This helps us avoid using a hashmap to identify the duplicates (like in solution 1 ) there by improving the space complexity(Keep reading to know how duplicate triplets can be skipped). Also sorting the array helps efficiently increment/decrement our index variables depending on whether the sum is less than or greater than 0. Next we need two loops. Outer loop index num1Idx represents the index of the first element in the triplet. Inner loop contains two indexes num2Idx and num3Idx representing the indexes of the 2nd and 3rd triplet elements respectively. Initially num1Idx points to the first element in the given array and num2Idx , num3Idx point to the 2nd and last elements in the given array. We fix the outer loop index num1Idx and move the two inner loop indexes inwards as long as num3Idx > num2Idx . Once the condition num3Idx > num2Idx is false we stop the inner loop and increment the outer loop index num1Idx , also update num2Idx and num3Idx , num2Idx=num1Idx +1 and num3Idx =n-1. Take a variable sum to store the triplet sum. sum = nums[num1Idx ] + nums[num2Idx ] + nums[num3Idx ]. Now there are three possibilities: a. If sum is equal to 0 we add it to our result. b. If sum is greater than 0 we need to decrease the sum value to make it equal to 0, so we decrement num3Idx index. c. If sum is less than 0 we need to increase sum value to make it equal to 0, so we increment num2Idx index. The inner loop should run as long as num3Idx > num2Idx for each iteration of the outer loop . We return the result once all the triplet combinations are processed. The above 4 steps ensure that we find all triplets whose sum is equal to 0. But it will also add duplicates to the result array. To skip duplicate triplets we need to add two conditions to our algorithm, one in the outer loop and one in the inner loop. In the outer loop if nums[num1Idx] == nums[num1Idx- 1 ] i.e. if current num1Idx value is same as previous number ( num1Idx -1) we skip the current number (we don't have to consider the current number for calculating our result). This condition ensures that we skip all duplicates from the left side of the array. Similarly to skip all numbers from the right side of the array, once we find a triplet with sum equal to zero we keep decrementing num3Idx until nums[ num3Idx ] != nums[ num3Idx +1] (in the inner loop). Simulation To make this more clear let us understand this algorithm with a simulation. Consider you are given the below input array nums of size n = 5: The first step is to sort the given array. After sorting nums will be: Iteration 1: For the 1st iteration of the outer loop num1Idx = 0, num2Idx = num1Idx + 1 = 1 and num3Idx = n-1 = 4. Same is show in figure below: Now we calculate the sum for array elements at current num1Idx , num2Idx and num3Idx . sum = nums [ num1Idx ] + nums [ num2Idx ] + nums [ num3Idx ] sum = nums [0] + nums [1] + nums [4] = (-1) + (-1) + 2 = 0 As you can see for the current values of num1Idx , num2Idx and num3Idx sum = 0, so we add it to our result . So result = [[-1, -1, 2]] and also decrement num3Idx . There is no need to make the duplicate check in the inner loop as num3Idx is the last element in the array. Now the updated values of index variables are num1Idx = 0, num2Idx = 1 and num3Idx = 3. Again calculate sum, sum = nums [0] + nums [1] + nums [3] = (-1) + (-1) + 1 = -1. Sum is less than 0, so we increment num2Idx . Now sum = nums [0] + nums [2] + nums [3] = (-1) + 0 + 1 = 0. Sum is equal to 0, so we add the current triplet [-1, 0, 1] to the result and decrement num3Idx . Also make the duplicate check in the inner loop, nums[num3Idx ] != nums[num3Idx +1], so there is no possibility of a duplicate for the current value of num3Idx , therefore no need to decrement num3Idx further. The updated values of index variables are num1Idx = 0, num2Idx = 2 and num3Idx = 2. As you can see num2Idx is equal to num3Idx , so we stop our inner loop and increment the outer loop index num1Idx by 1. Iteration 2: For the second iteration of the outer loop, the updated values for indexes are num1Idx =1, num2Idx=num1Idx +1=2 and num3Idx = n-1 = 5-1 = 4. Since the value of num1Idx is same as the previous iteration num1Idx value, we end up with duplicate triplets if consider this value again. Therefore we need to skip the current num1Idx , so increment num1Idx . Now num1Idx = 2, num2Idx = 3 and num3Idx = 4. And sum = nums [2] + nums [3] + nums [4] = 0 + 1 + 2 = 3 is greater than 0, so we decrement num3Idx . Again num2Idx is equal to num3Idx , therefore we stop the inner loop, also we have reached the end of array, so we stop our algorithm and return the result. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python 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 Dart Solution Erlang Solution Coming soon... Complexity Analysis Time Complexity Sorting the array: If n is the size of nums array, sorting the nums array takes O(n log n) . Outer Loop (num1Idx): The outer loop runs from index 0 to n-2 . So it iterates O(n) times. Inner Loop (num2Idx and num3Idx): For each iteration of the outer loop num1Idx , the inner loop iterates through the rest of the nums array elements using num2Idx and num3Idx indices. In the worst case this can make n iterations. As num1Idx increases the inner loop has to process lesser and lesser elements with each iteration. However the time complexity for this nested loop combination is O(n^2) . Overall Time Complexity: Considering the above analysis, the overall time complexity of this algorithm is O(n log n) + O(n^2) = O(n^2) . Space Complexity The algorithm uses constant space variable for its operations, so if we don't consider the result variable the space complexity is O(1) . If we consider the result variable, the space complexity is O(n^2) in the worst case when every triplet in nums array sums to zero. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe here . Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us on social media: YouTube , Facebook , Twitter , Linkedin , Tumblr , Instagram .

Hello Code Recipian! In this we will solve LeetCode problem 215. Kth Largest Element in an Array using the heap data structure. This article is part of our LeetCode problem solutions series—be sure to explore the rest of the series once you’ve finished reading this one! Brace yourself—it's time to tackle the problem statement! Problem Statement: Kth Largest Element in an Array Given an array of integers nums and an integer k , return the kth largest element in the array. Note: You have to return the kth largest element in the sorted order, not kth distinct element. Example 1: Input:  nums = [3, 2, 1, 5, 6, 4], k = 2 Output:  5 Example 2: Input:  nums = [3,2,3,1,2,4,5,5,6], k = 4 Output:  4 Constraints: 1 <= k <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 Solution This problem is classified as medium difficulty on LeetCode. While it can be easily solved using a sorting-based approach, the time complexity of this solution is O(n log n) . We can achieve a better time complexity using the max heap data structure. Since the max heap data structure maintains the largest elements at the top, the idea is to build a max heap using the given array and if we extract k elements from max heap we will get the kth  largest element. Many programming languages offer built-in heap libraries that can be easily imported and used in our code. However, in this solution, we will implement our own heap. Doing so will deepen our understanding of both the problem and the heap data structure, while also enhancing our preparation for coding interviews. What is a Max Heap? A max heap data structure is a binary tree, in which value of the parent node is always greater than that of its children and this property applies for all nodes in the tree. This property of max heap ensures that the largest element is always at the root. Heap Representation using an Array A heap can be efficiently represented using an array: Root of the heap is at index 0 . For a node at index i : The left child is located at index 2 * i + 1 in the array. The right child is located at index 2 * i + 2 . Parent is located at index (i-1)/2 . For example the max heap given below: can be represented in array form as: [10, 7, 8, 5, 6, 3, 4] This simplifies heap operations as we can directly calculate parent, child indices using formulas. Quick Glance: Heap Operations Heapify Down: Heapify down ensures that the heap property is maintained/restored, after we delete or modify elements in a max heap. Given the index of the node, heapify down pushes a node down to its correct position in the heap. Extract or Delete: In a heap, extraction/deletion is always performed on the root node.. In order to extract a value from heap: First copy the root value to be deleted into a temporary variable. Copy the value of the bottom-rightmost node (last node) into the root node. Finally, heapify down the newly copied root value to restore the heap property. Algorithm Here is a detailed explanation of how the algorithm works: Initialization: Get the length of nums array and store it in a variable, let's call it n . Build max heap from array: Next, we convert the given nums array into a max heap. We do this by repeatedly calling heapify down on every node value in nums . As a slight optimization, we can call heapify down only non-leaf nodes (since leaf nodes does not have children, heapify down does not make sense for a leaf node). For an array represented as a heap, the (n/2 - 1) th element points to the last non-leaf node. Heapify down function: The job of the heapify function in a max heap is to compare the parent node value with the maximum of left and right child value, and push it down the heap if needed to its correct position to maintain the heap property. The heapifyDown function takes 3 arguments: nums  array. i  the index of the node which needs to be heapified. n length of nums array. Initially, we assume the current index i  to be the index which has the largest value, let's call this index variable largestIdx . Calculate left and right child indices using the formulas described earlier. Let's call this leftChildIdx and rightChildIdx . Find the largest of left and right child and compare it with the parent. If max(left child, right child) > parent , then we swap it with the parent. Assign largestIdx as the current index i (for next iteration). If max(left child, right child)  <= parent , it means current element at index i is already in its correct position in max heap. Therefore, we stop and come out of the heapify function. Repeat steps b  to d  until the required element is pushed down to its correct position in heap. Extract heap elements: At this point we have the nums array converted to a max heap. Now extract k-1 elements from heap. To extract an element from max heap, perform the following steps: Copy the last heap element to the root. Either remove the last element from nums or simply decrement n . Call heapify down function for index 0 (to place the element copied to root in in its correct position in heap). Repeat steps a to c , k-1 times. Return final result: Now that we have extracted k-1 elements, the kth largest element is at the root of the heap ( 0th index in array). Therefore return the 0th index as result. Simulation Here is a visual representation of how the algorithm works: Above diagram shows how heapifyDown systematically pushes a particular element down the tree (observe the nodes marked with green) to restore/maintain max heap property. 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 Complexity Analysis Time Complexity Building the max heap: For building the max heap, we call heapifyDown on all non-leaf nodes. Each call to heapifyDown takes O(log n) time. In a binary tree there can be approximately n/2 non-leaf nodes. From the above analysis, it might appear that the time for building the heap is O(n/2 log n) or O(n log n) . However in reality it takes an overall linear time to build a heap. The intuition is that, even though a single heapify might take O(log n) time, the number of operations required decreases drastically as we move up the tree, leading to an overall linear time. At lower levels the heapify operation is cheaper (because nodes at lower level have less children below them) but applied more often (because we start heapify from the bottom of the tree). At higher levels the heapify operation is more expensive (because nodes at higher level have more nodes below them) but applied less often (since we start heapify from bottom of the tree, the initial heapify calls would have already put the nodes at its correct position by the time heapify reaches higher level nodes). Therefore time complexity for building a heap from an array is O(n) . Extracting k elements from max heap: The algorithm extracts k elements from heap for finding the kth largest element. Each extract operation makes a call to heapifyDown which have a O(log n) time complexity. Hence the time complexity for this step is O(k log n) . Overall time complexity: Combining the above two points, the overall time complexity of this algorithm is O(n) + O(k log n) = O(n + k log n) . Space Complexity The algorithm operates in place and uses only a constant amount of extra space. Therefore, the space complexity is O(1) . That concludes this article. We truly appreciate the time you've spent reading it. If you have any questions, feel free to leave them in the comments below. We're happy to assist and will gladly respond to your queries. If you found this article helpful, consider subscribing to our website and   Youtube channel . Your support motivates us to create more insightful articles in the future. Limited Time Offer from Code Recipe:  Enjoy a 100% discount on the Code Recipe Membership Plan. Sign up now to access exclusive premium content for free. Act fast—this offer is 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 113. Path Sum II . This problem is an extension of 112. Path Sum which we have discussed in one of our other articles. If you have not yet checked it out we recommend you to go through that first before proceeding further in this article. It will help you build a solid foundation for solving this problem. Problem Statement: Path Sum II Given the root node of the binary tree and an integer targetSum , return all root to leaf paths in this tree such that, sum of these paths is equal to targetSum . Return paths as a list of node values. A node in a tree that has no children is called a leaf node. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]] Explanation: There are two paths with targetSum = 22 highlighted in yellow: [5,4,11,2] and [5,8,4,5] Example 2: Input:  root = [1,2,3], targetSum = 5 Output:  [] Constraints: The number of nodes in the tree is in the range [0, 5000] . -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000 Solution Algorithm Below is a step-by-step explanation for the working of the algorithm: Initialization: Initialize a 2D array for storing our result. Let's call this result . Call DFS function: Next we call the DFS function by passing the following parameters: node , targetSum , currPath , result . node represents the tree node. Initially when we call the DFS function, we pass the root node. targetSum is the target sum given in question. currPath array is used to keep track of the nodes in the current path, when we perform DFS traversal of the tree. result is used to store the result. DFS Function: Base Case: The case for this recursive function is when we reach a null node. If we reach a null node, we stop further calls and return back to the caller. Subtract current node from target sum: Next we subtract the current node value from the given target sum. The reason behind doing this is that, if we reach a null node and if the targetSum after subtracting all the node values in that path is 0, it means we have found a path whose sum is equal to targetSum . Add to result if a path is found: Now we use the subtraction result from previous step to determine if we have found a path with targetSum . For a path to exist with the given targetSum, it must satisfy the following criteria: Current node must be a leaf node. Current targetSum value after subtraction must be equal 0. If we find any path that satisfies the above two criteria, we add the currPath to result array. Recursive calls to left and right child: Finally, we make recursive calls to left and right children of current node. Return final result: Return the final result from the main function. 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 Scala Solution Rust Solution Complexity Analysis Time Complexity DFS Traversal: If n is the number of nodes in the given tree, in general DFS traversal of a tree takes O(n) time complexity. Copying path values: After finding a path we copy all currPath values to result , this requires a time complexity of O(H) for each path found, where H is the height of the given tree ( O(H) since we are looking for a root to leaf path, so we will be copying only after we have reached the leaf node). For the given tree, if L is the number of leaf nodes, the overall time complexity for copying node values for every path found in the worst case is O(L * H) . Overall time complexity: Considering the above factors : For a balanced tree height H = log n , so the time complexity is O(n log n) . For a skewed tree, height is equal to the number of nodes in the tree, i.e. H = n , so time complexity if O(n ² ) . Space Complexity For recursion: To perform DFS using recursion, the space complexity for recursion stack is O(H) . In the worst case (for skewed trees) this can be O(n) . Current path storage: We use the currPath array to store the elements of current path during DFS. This space usage is directly proportional to the height of the tree and hence has a space complexity of O(H) . Storing the result: We use the result 2D array to store our result. In the worst case, every leaf node might yield a valid path. So, the space complexity is O(L * H) . Overall space complexity: Therefore the overall space complexity is O(n ² ) in the worst case for a skewed tree and O(n log n) in the average case for a balanced tree. 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 .

Introduction: Bubble Sort Algorithm Bubble Sort algorithm is one of the simplest and well-known sorting algorithms . Though it is not one of the most efficient sorting algorithms, its straight forward approach makes it an excellent starting point for anyone learning algorithms. Bubble sort works by iterating through 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. Bubble sort segregates the array into two parts: Sorted portion Unsorted portion Sorted elements are placed towards the end of the array. In every pass, one of the elements from unsorted portion is moved to its correct position in the sorted portion of the array. Once an element is placed in its correct sorted position, there is no need to check this element again. Let's see how this algorithm works in detail. Algorithm For a given input array arr that needs to be sorted in ascending order, bubble sort does the following steps: Compare adjacent elements: Iterate through the given array arr from start to end. In each iteration, compare adjacent elements. We start by comparing the 1st and 2nd elements in arr : If 1st element is greater than 2nd element, it means elements are not in correct order, so we swap them. If 1st element is smaller than or equal 2nd element, it means elements are in correct order. So no need to swap, continue to next iteration. In the next iteration, we compare 2nd and 3rd elements and repeat steps a and b . Next we compare 3rd and 4th elements and so on until we reach the end of array. Repeat step 1 until sorted: The procedure described in step 1, comparing and swapping elements from start to end is known as one "pass" on the array arr . For each pass through the array arr , one element is bubbled to its correct position towards the end of the array. For an array of size n , we need to do n-1 such passes to make it fully sorted. Note: In each pass, once an 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. Note: If two elements are equal, we do not swap them, 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). Simulation Below is a pictorial depiction of the working of the algorithm: Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python 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 Complexity Analysis Time Complexity The worst case time complexity for bubble sort algorithm is   O(n ² ) since we have to run two loops to implement it and in the worst case we would end up making nearly   O(n ² ) comparisons to get the final sorted array. Therefore the worst case time complexity of this algorithm is   O(n ² ) . 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 Bubble sort does not use any extra space to sort the given array, it sorts the given array in place . So the space complexity is O(1) . Conclusion 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. 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 on binary tree 112. Path Sum . Getting a good understanding of this problem will help you solve advanced level tree questions like 113. Path Sum II . Let's check out the problem statement. Problem Statement: Path Sum Given the root node of a binary tree and an integer targetSum , return true if the tree has a path from root-to-leaf such that, sum of all node values along the path equals targetSum . Return false otherwise. A node in a tree is called a leaf node, if it has no children. Example 1: Input:  root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22 Output:  true Explanation:  Node values in the path highlighted in yellow add up to targetSum . Example 2: Input : root = [5, 4, 8, 11, 2, 10, 4], targetSum = 23 Output:  true Constraints: The number of nodes in the tree is in the range [0, 5000] . -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000 Solution In this problem we are given a binary tree, we need to find the sum of any path originating from root to leaf node, whose node values add up to the given targetSum . In this article we will be discussing how we can solve this problem optimally using the depth first search traversal approach. The idea is to use recursion and perform depth first search (DFS) of the given binary tree. We traverse every root-to-leaf path in the given tree and in each step, we subtract the current node value from the given target sum. When we reach the leaf node, we check if the current sum value is zero in order to determine if the current path adds up to the given target sum. Let's see how this algorithm works in detail. Algorithm Below is a step-by-step explanation for the working of the algorithm: Base Case: We will be using recursion to perform depth first search of the given binary tree. Every recursive solution must have a base case to indicate when the recursion must stop. In our case, the base case is when we reach a null node. If we reach a null node, we stop and return false . Subtract current node from targetSum: In each recursive call we subtract the current node value from targetSum . The logic behind this is that, if there exists a root-to-leaf path that adds up to the given targetSum , as we subtract current node values from targetSum , when we reach the leaf node the targetSum value must become 0. If targetSum does not become zero when we reach leaf the node, it means that the current path sum does not add up to the given targetSum . Verify if path sum is possible: This is the part where we validate if the current path from root to leaf adds up to the given targetSum . We can verify this by checking if the following two conditions are satisfied: Current node is a leaf node and, targetSum after subtraction must have reached 0. If either of the a or b is not satisfied, we continue our DFS. If both conditions are satisfied, it means we have found a root-to-leaf path whose sum is equal to targetSum . Therefore, we return result as true . Recursive DFS calls: Final part is to define the recursive calls for DFS, one call for the left child and one for the right child. If either of these recursive calls return true , it means a valid root-to-leaf path with targetSum exists, so we return true . If both these calls return false , it means no such path exists, so we return false . Simulation Below diagram shows 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 Scala Solution Rust Solution Complexity Analysis Time Complexity If n is the number of nodes in the given binary tree, time complexity of this algorithm is O(n) , because in the worst case, we end up traversing every node in the binary tree once to arrive at the result. The worst case occurs when the the given tree is a skewed binary tree . Space Complexity This algorithm does not use any additional variables that have impact on space complexity. However, because we are using recursion here, the space complexity of this algorithm is O(n) for the recursion call stack . 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 .