Two Pointers

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. **Note:** Alphanumeric characters consist of letters `(A-Z, a-z)` and numbers `(0-9)`. **Example 1:** ```java 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. **Example 2:** ```java Input: s = "tab a cat" Output: false ``` Explanation: "tabacat" is not a palindrome. **Constraints:** * `1 <= s.length <= 1000` * `s` is made up of only printable ASCII characters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the length of the input string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to create a copy of the string, reverse it, and then check for equality. This would be an <code>O(n)</code> solution with extra space. Can you think of a way to do this without <code>O(n)</code> space? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Can you find the logic by observing the definition of pallindrome or from the brute force solution? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> A palindrome string is a string that is read the same from the start as well as from the end. This means the character at the start should match the character at the end at the same index. We can use the two pointer algorithm to do this efficiently. </p> </details>

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)$ additional space. **Example 1:** ```java 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]`. **Constraints:** * `2 <= numbers.length <= 1000` * `-1000 <= numbers[i] <= 1000` * `-1000 <= target <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to check every pair of numbers in the array. This would be an <code>O(n^2)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Can you think of an algorithm by taking the advantage of array being sorted? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use the two-pointer algorithm. If <code>nums[0] + nums[n-1] > target</code>, then we know <code>nums[n - 1]</code> can not possibly be included in any pairs. Why? Because <code>nums[n - 1]</code> is the largest element in the array. Even by adding it with <code>nums[0]</code>, which is the smallest element, we still exceed the target. You can think of the case when <code>nums[0] + nums[n - 1] < target</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We keep two pointers, one at the start and the other at the end of the array. If the sum of the numbers at the two pointers is greater than the <code>target</code>, decrement the right pointer, else increment the left pointer. Repeat this process until you find a valid pair. </p> </details>

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:** ```java 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 2:** ```java Input: nums = [0,1,1] Output: [] ``` Explanation: The only possible triplet does not sum up to 0. **Example 3:** ```java Input: nums = [0,0,0] Output: [[0,0,0]] ``` Explanation: The only possible triplet sums up to 0. **Constraints:** * `3 <= nums.length <= 1000` * `-10^5 <= nums[i] <= 10^5` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n^2)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to check for every triplet in the array. This would be an <code>O(n^3)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Can you think of an algorithm after sorting the input array? What can we observe by rearranging the given equation in the problem? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can iterate through nums with index <code>i</code> and get <code>nums[i] = -(nums[j] + nums[k])</code> after rearranging the equation, making <code>-nums[i] = nums[j] + nums[k]</code>. For each index <code>i</code>, we should efficiently calculate the <code>j</code> and <code>k</code> pairs without duplicates. Which algorithm is suitable to find <code>j</code> and <code>k</code> pairs? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> To efficiently find the <code>j</code> and <code>k</code> pairs, we run the two pointer approach on the elements to the right of index <code>i</code> as the array is sorted. When we run two pointer algorithm, consider <code>j</code> and <code>k</code> as pointers (<code>j</code> is at left, <code>k</code> is at right) and <code>target = -nums[i]</code>, if the current sum <code>num[j] + nums[k] < target</code> then we need to increase the value of current sum by incrementing <code>j</code> pointer. Else if the current sum <code>num[j] + nums[k] > target</code> then we should decrease the value of current sum by decrementing <code>k</code> pointer. How do you deal with duplicates? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 5</summary> <p> When the current sum <code>nums[j] + nums[k] == target</code> add this pair to the result. We can move <code>j</code> or <code>k</code> pointer until <code>j < k</code> and the pairs are repeated. This ensures that no duplicate pairs are added to the result. </p> </details>

You are given an integer array `heights` where `heights[i]` represents the height of the $i^{th}$ bar. You may choose any two bars to form a container. Return the *maximum* amount of water a container can store. **Example 1:**  ```java Input: height = [1,7,2,5,4,7,3,6] Output: 36 ``` **Example 2:** ```java Input: height = [2,2,2] Output: 4 ``` **Constraints:** * `2 <= height.length <= 1000` * `0 <= height[i] <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to try all pairs of bars in the array, compute the water for each pair, and return the maximum water among all pairs. This would be an <code>O(n^2)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Can you think of an algorithm that runs in linear time and is commonly used in problems that deal with pairs of numbers? Find a formula to calculate the amount of water when we fix two heights. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use the two pointer algorithm. One pointer is at the start and the other at the end. At each step, we calculate the amount of water using the formula <code>(j - i) * min(heights[i], heights[j])</code>. Then, we move the pointer that has the smaller height value. Can you think why we only move the pointer at smaller height? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> In the formula, the amount of water depends only on the minimum height. Therefore, it is appropriate to replace the smaller height value. </p> </details>

You are given an array of 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:**  ```java Input: height = [0,2,0,3,1,0,1,3,2,1] Output: 9 ``` **Constraints:** * `1 <= height.length <= 1000` * `0 <= height[i] <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> How can we determine the amount of water that can be trapped at a specific position in the array? Perhaps looking at the image might help clarify. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> From the image, we can see that to calculate the amount of water trapped at a position, the greater element to the left <code>l</code> and the greater element to the right <code>r</code> of the current position are crucial. The formula for the trapped water at index <code>i</code> is given by: <code>min(height[l], height[r]) - height[i]</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> A brute force solution would involve iterating through the array with index <code>i</code>, finding the greater elements to the left (<code>l</code>) and right (<code>r</code>) for each index, and then calculating the trapped water for that position. The total amount of trapped water would be the sum of the water trapped at each index. Finding <code>l</code> and <code>r</code> for each index involves repeated work, resulting in an <code>O(n^2)</code> solution. Can you think of a more efficient approach? Maybe there is something that we can precompute and store in arrays. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can store the prefix maximum in an array by iterating from left to right and the suffix maximum in another array by iterating from right to left. For example, in <code>[1, 5, 2, 3, 4]</code>, for the element <code>3</code>, the prefix maximum is <code>5</code>, and the suffix maximum is <code>4</code>. Once these arrays are built, we can iterate through the array with index <code>i</code> and calculate the total water trapped at each position using the formula: <code>min(prefix[i], suffix[i]) - height[i]</code>. </p> </details>