Buckets:
| tags: | |
| - notes | |
| - two-pointers | |
| ### [Valid Palindrome](https://neetcode.io/problems/is-palindrome) EASY | |
| Given a string `s`, return `true` if it is a palindrome, otherwise return `false`. A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters. | |
| ``` | |
| Input: s = "Was it a car or a cat I saw?" | |
| Output: true | |
| Explanation: After considering only alphanumerical characters we have | |
| "wasitacaroracatisaw", which is a palindrome. | |
| Input: s = "tab a cat" | |
| Output: false | |
| Explanation: "tabacat" is not a palindrome. | |
| ``` | |
| #### **Solution** | |
| ```python | |
| class Solution: | |
| def isPalindrome(self, s: str) -> bool: | |
| l, r = 0, len(s) - 1 | |
| while l < r: | |
| if not s[l].isalnum(): | |
| l += 1 | |
| elif not s[r].isalnum(): | |
| r -= 1 | |
| else: | |
| if s[l].lower() != s[r].lower(): | |
| return False | |
| l += 1 | |
| r -= 1 | |
| return True | |
| ``` | |
| To determine if a given string is a valid palindrome, we can use two pointers approach. We initialize two pointers, one at the beginning of the string (left) and the other at the end of the string (right). We then compare characters at these two pointers. If they are both alphanumeric characters and equal in value (ignoring case), we move both pointers towards the centre of the string. If they are not equal, we know the string is not a palindrome. We continue this process until the two pointers meet or cross each other. | |
| 1. Start with two pointers, one at the start other at the end of string, and start moving both towards each other. | |
| 2. if any of the characters at `l` or `r` is not alphanumeric, the pointer is moved forward or backward. | |
| 3. If the character at `l` and `r` are not same when they are lowercase, `False` is returned, else the pointers are moved forward and backward. | |
| 4. At the end, `True` is returned, indicating the string is palindrome. | |
| ### [Two Sum II](https://neetcode.io/problems/two-integer-sum-ii) MEDIUM | |
| Given an array of integers `numbers` that is sorted in non-decreasing order. Return the indices (1-indexed) of two numbers, `[index1, index2]`, such that they add up to a given target number `target` and `index1 < index2`. Note that `index1` and `index2` cannot be equal, therefore you may not use the same element twice. | |
| There will always be exactly one valid solution. Your solution must use O(1)_O_(1) additional space. | |
| ``` | |
| Input: numbers = [1,2,3,4], target = 3 | |
| Output: [1,2] | |
| Explanation: | |
| The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1, | |
| index2 = 2. We return [1, 2]. | |
| ``` | |
| > [!info] Time & Space Complexity | |
| > You should aim for a solution with `O(n)` time and `O(1)` space, where `n` is the size of the input array. | |
| #### Solution | |
| ```python | |
| class Solution: | |
| def twoSum(self, numbers: List[int], target: int) -> List[int]: | |
| l, r = 0, len(numbers) - 1 | |
| while l < r: | |
| two_sum = numbers[l] + numbers[r] | |
| if two_sum < target: | |
| l += 1 | |
| elif two_sum > target: | |
| r -= 1 | |
| else: | |
| return [l + 1, r + 1] | |
| ``` | |
| 1. Start with two pointers, `l` and `r` , one in the starting of string and other at the end. | |
| 2. Calculate the sum of the numbers that are in the `l` and `r` pointers. If the sum is lesser than target, move `l` forward and if sum is greater than target, move `r` backward. | |
| 3. If both cases fail, we have our answer, which is `[l+1, r+1]` . Return it. | |
| ### [3 Sum](https://neetcode.io/problems/three-integer-sum) MEDIUM | |
| Given an integer array `nums`, return all the triplets `[nums[i], nums[j], nums[k]]` where `nums[i] + nums[j] + nums[k] == 0`, and the indices `i`, `j` and `k` are all distinct. The output should _not_ contain any duplicate triplets. You may return the output and the triplets in any order. | |
| ``` | |
| **Example 1:** | |
| Input: nums = [-1,0,1,2,-1,-4] | |
| Output: [[-1,-1,2],[-1,0,1]] | |
| **Explanation:** | |
| nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. | |
| nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. | |
| nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. | |
| The distinct triplets are [-1,0,1] and [-1,-1,2]. | |
| **Example 3**: | |
| Input: nums = [0,0,0] | |
| Output: [[0,0,0]] | |
| **Explanation**: The only possible triplet sums up to 0. | |
| ``` | |
| #### **Solution** | |
| To find all unique triplets that sum to zero, we can use a three-pointer approach. First, we sort the input array `nums` in non-decreasing order. Then, we iterate through the array with a fixed first element (`i`). For each fixed first element, we use two pointers (left and right) to find the other two elements that sum to the negation of the fixed first element. As the array is sorted, we can move these two pointers towards each other to efficiently find all possible triplets. | |
| ```python | |
| class Solution: | |
| def threeSum(self, nums: List[int]) -> List[List[int]]: | |
| res = [] | |
| size = len(nums) | |
| nums.sort() | |
| for i in range(size - 2): | |
| if nums[i] > 0: | |
| break | |
| if i > 0 and nums[i] == nums[i - 1]: | |
| continue | |
| l, r = i + 1, size - 1 | |
| while l < r: | |
| three_sum = nums[i] + nums[l] + nums[r] | |
| if three_sum < 0: | |
| l += 1 | |
| elif three_sum > 0: | |
| r -= 1 | |
| else: | |
| res.append([nums[i], nums[l], nums[r]]) | |
| l += 1 | |
| r -= 1 | |
| while l < r and nums[l] == nums[l - 1]: | |
| l += 1 | |
| return res | |
| ``` | |
| > [!info] Time and Space complexity | |
| > **You should aim for a solution with** `O(n)` **time and** `O(1)` **space, where** `n` **is the size of the input array.** | |
| ### [Container with most water](https://neetcode.io/problems/max-water-container) MEDIUM | |
| You are given an integer array `heights` where `heights[i]` represents the height of the ith _ith_ bar. | |
| You may choose any two bars to form a container. Return the _maximum_ amount of water a container can store. | |
| ![[container-with-most-water.png.png]] | |
| ``` | |
| Example 1: | |
| Input: height = [1,7,2,5,4,7,3,6] | |
| Output: 36 | |
| ``` | |
| #### **Solution** | |
| To find the maximum area of water that can be held between two vertical lines, we can use a two-pointer approach. We initialize two pointers, one at the beginning of the input array (left) and the other at the end of the array (right). The area between the two vertical lines is calculated as the minimum of the heights at the two pointers multiplied by the distance between them. We then update the maximum area found so far and move the pointer with the smaller height towards the other pointer. We continue this process until the two pointers meet or cross each other. | |
| ```python | |
| class Solution: | |
| def maxArea(self, heights: List[int]) -> int: | |
| size = len(heights) | |
| l, r = 0, size - 1 | |
| max_vol = 0 | |
| while l < r: | |
| height = min(heights[l], heights[r]) | |
| max_vol = max(max_vol, height * (r - l)) | |
| if heights[l] <= heights[r]: | |
| l += 1 | |
| else: | |
| r -= 1 | |
| return max_vol | |
| ``` | |
| > [!info] Time and Space complexity | |
| > You should aim for a solution with`O(n)` time and `O(1)` space, where `n` is the size of the input array. | |
| ### [Trapping Rain Water](https://neetcode.io/problems/trapping-rain-water) HARD | |
| You are given an array non-negative integers `height` which represent an elevation map. Each value `height[i]` represents the height of a bar, which has a width of `1`. | |
| Return the maximum area of water that can be trapped between the bars. | |
| Example 1: | |
| ![[trapping-rain-water.png.png]] | |
| ``` | |
| Input: height = [0,2,0,3,1,0,1,3,2,1] | |
| Output: 9 | |
| ``` | |
| #### **Solution** | |
| To find the amount of trapped rainwater in the given elevation histogram represented by the input array 'height', we can use a two-pointer approach. We initialize two pointers, one at the beginning of the array (left) and the other at the end of the array (right). We also initialize two variables to keep track of the maximum left height and maximum right height seen so far. While the left pointer is less than the right pointer, we compare the height at the left and right pointers. If the height at the left pointer is less than or equal to the height at the right pointer, it means we can trap water between the left pointer and the maximum left height. Otherwise, we can trap water between the right pointer and the maximum right height. At each step, we update the trapped water amount and move the pointers and update the maximum heights accordingly. | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution as good or better than `O(n)` time and `O(n)` space, where `n` is the size of the input array. | |
| ```python | |
| class Solution: | |
| def trap(self, height: List[int]) -> int: | |
| left, right = 0, len(height) - 1 | |
| max_left, max_right = 0, 0 | |
| trapped_water = 0 | |
| while left < right: | |
| if height[left] <= height[right]: | |
| if height[left] >= max_left: | |
| max_left = height[left] | |
| else: | |
| trapped_water += max_left - height[left] | |
| left += 1 | |
| else: | |
| if height[right] >= max_right: | |
| max_right = height[right] | |
| else: | |
| trapped_water += max_right - height[right] | |
| right -= 1 | |
| return trapped_water | |
| ``` | |
| PREVIOUS: [[Arrays and Hashing]] | NEXT: [[Sliding Window]] |
Xet Storage Details
- Size:
- 9.23 kB
- Xet hash:
- 191ae1d7370d7958afc815880b7a2b1d8d6f4bfcee307e37a6b1a0ab63df5425
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.