Two Pointers

Question 1

Valid 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

Answer 1

1. Initialization: left pointer starts at the beginning of the string.
   right pointer starts at the end of the string.
2. Skip Non-Alphanumeric Characters: Use the alphaNum helper method to identify alphanumeric characters. Increment left or decrement right pointers until they point to alphanumeric characters.
3. Compare Characters: Convert both characters to lowercase using .lower() and compare them. If they are not equal, return False.
   Continue Moving Pointers:
4. Move left one step forward and right one step backward.
5. Return Result: If the pointers meet without mismatches, return True.

Time Complexity: O(1)
Space Complexity: O(1)

Question 2

Two Integer Sum II (med)

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.

Answer 2

1. Initialization: Left pointer starts at the beginning of the array.
   right pointer starts at the end of the array.
2. Calculate the Sum: Add the values at the left and right pointers (numbers[left] + numbers[right]).
   If the sum equals the target, return the 1-based indices [left + 1, right + 1].
3. Adjust Pointers: If the sum is greater than the target, move the right pointer one step left to reduce the sum.
   If the sum is less than the target, move the left pointer one step right to increase the sum.
4. Continue: Repeat until the pointers meet or the solution is found.

Time Complexity: O(n)
Space Complexity: O(1)

Question 3

3 Sum (med)

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.

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Answer 3

1. Sort the Array: Sorting simplifies duplicate handling and enables the two-pointer approach.
2. Iterate: Use each number a as the first element of the triplet. Skip duplicates of a.
3. Two-Pointer Search: Use pointers l (left) and r (right) to find numbers such that a+nums[l]+nums[r]=0. If the sum is zero, save the triplet and skip duplicates.
4. Adjust pointers: Sum < 0 → move l right. Sum > 0 → move r left.
5. Output: Return all unique triplets.
   Time Complexity: O(n^2)
   Space Complexity: O(1)

Question 4

Container with most water (med)

You are given an integer array heights where heights[i] represents the height of the ith bar.You may choose any two bars to form a container. Return the maximum amount of water a container can store.

Answer 4

1. Two Pointers: Use a left pointer at the start and a right pointer at the end of the array.
2. Calculate Area: Compute the area as min(heights[left],heights[right])×(right−left).
3. Update maxHeight if the current area is larger.
4. Move Pointers: If heights[left] <= heights[right], move left pointer right.Otherwise, move right pointer left.
5. Stop When Left Meets Right: Return the maximum area found.

Time Complexity: O(n)
Space Complexity: O(1)

Question 5

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.

Input: height = [0,2,0,3,1,0,1,3,2,1]
Output: 9

Answer 5

1. Precompute Maximums: maxLeft[i]: Maximum height to the left of index i. maxRight[i]: Maximum height to the right of index i.
2. Calculate Minimum Boundaries: For each index i, compute minLeftRight[i] = min(maxLeft[i], maxRight[i]).
3. Compute Trapped Water: For each index i, the trapped water is minLeftRight[i] - height[i] if it’s positive.