Category: two_pointers
-
LeetCode 2824: Count Pairs Whose Sum is Less than Target
Sort and two pointers In sorted order, if nums[i] + nums[j] < target, then with nums[i] as the first element there are (j-i) second elements that can make a valid pair. Time: , space: .
-
LeetCode 1650: Lowest Common Ancestor of a Binary Tree III
link Since we have parent pointer, we can find the path from p -> root and q -> root and then traverse the two paths in sync to find the LCA. Time: , space: . We do not need to precompute the paths. Say p and q are traversing towards the root. Below, by the…
-
LeetCode 1842: Next Palindrome Using Same Digits
link Since num is a palindrome, if there is a center, it cannot be rearranged because the center is the only digit having odd count. We can rearrange the digits in one of the two halves only because, the other half would be mirror-image. So, we rearrange left half. If the digits were sorted in…
-
LeetCode 647: Palindromic Substrings
link We can check if a string is a palindrome in two ways: Both ways take time. However, there is a difference: the count of possible pairs of end points is whereas the count of possible centers is . Process inwards from two ends Brute force Try all possible substrings. Time: , space: . Dynamic…
-
LeetCode 2193: Minimum Number of Moves to Make Palindrome
link Similarly to how we validate if a string is a palindrome, we turn the string into a palindrome starting with the two ends and converging towards the center. If the two ends do not match, we change one end into another, taking the cheaper of the two available options. Time: , space: .
-
LeetCode 246: Strobogrammatic Number
link Two ends must form a Strobogrammatic pair and if there is a center it must be Strobogrammatic. Time: , space: .
-
LeetCode 408: Valid Word Abbreviation
link Non-numeric portion of abbr must match char-by-char with word. For numeric portion: Time , space: .
-
LeetCode 151: Reverse Words in a String
link Time: , space: . We can do the reversing in-place: Since Python’s str is immutable, we first convert s to a List[str] and once reversing is done, return s[0:n] as a str. Time: , space: .
-
LeetCode 75: Sort Colors
link We count 0’s, 1’s, and 2’s. Then fill up nums starting with 0’s, then 1’s followed by 2’s. Time: , space: . We could sort an array around a pivot in one pass. We shall use pivot == 1 for this problem. We shall maintain nums like below: Initially, the entire nums consists of…
-
LeetCode 125: Valid Palindrome
link Try matching lowercase left and right skipping over non-alphanumeric characters. Time: , space: .
unreasonably effective 