Q: Trapping Rain Water (total water held between bars of an elevation map) with two pointers and running left_max and right_max. When height[l] < height[r], what is added at l?

left_max - height[l] after updating left_max When height[l] < height[r], the right side has a wall at least as tall as left_max, so left_max bounds the water at l. Using right_max overcounts when right_max is larger than left_max. Using a precomputed full right_max is the prefix array approach, not this one, and mixing them is inconsistent. height[r] minus height[l] ignores walls between.

Q: Squares of a sorted array that contains negatives, return sorted squares in O(n). How?

Two pointers at both ends. The largest square is at one end, so compare abs values, write the bigger square to the back of the output, and move that pointer. Pitfall: squaring then sorting is O(n log n).

Question 1

Two Sum on an unsorted array, return indices. A candidate proposes left and right pointers moving inward. What is wrong?

Accepted Answer

Pointer moves are only valid on sorted input, and sorting loses the original indices Moving left up when the sum is too small relies on sorted order. Without sorting the moves skip valid pairs, and sorting needs index tracking. It is not O(n^2), it is wrong. A visited set of pointers fixes nothing.

Question 2

3Sum on sorted nums must return unique triplets. After finding a triplet at (i, l, r), what avoids duplicates without a set?

Accepted Answer

Advance l while nums[l] equals the previous value, and skip i when nums[i] equals nums[i - 1] Skipping equal neighbours for both the anchor and the inner pointer removes repeats while keeping valid triplets. Skipping i against i + 1 drops the first copy and loses triplets like [-1, -1, 2]. Breaking after one triplet misses others with the same anchor. Deduplicating the input loses triplets that need repeated values such as [0, 0, 0].

Question 3

Container With Most Water (pick two vertical lines that hold the most water) uses two pointers. Which pointer moves each step?

Accepted Answer

The one with the shorter line Area is limited by the shorter line, and any container keeping that short line with a narrower width cannot be larger, so discarding it is safe. Moving the taller line can only keep or reduce height while width shrinks. Moving both can skip the optimum. Always moving left ignores heights entirely.

Question 4

Valid Palindrome ignoring non alphanumeric characters and case. Which is O(1) extra space?

Accepted Answer

Two pointers from both ends, skipping non alphanumerics and comparing lowercased chars Inward pointers use constant space. Building a filtered copy is O(n) space. A stack is O(n). Recursive stripping creates new strings and uses O(n) stack.

Question 5

Remove duplicates in place from a sorted array and return the new length k. Which loop is right?k = 1
for i in range(1, len(nums)):
 if nums[i] != nums[k - 1]:
 nums[k] = nums[i]
 k += 1

Accepted Answer

Correct as written for non empty input The write pointer k compares against the last kept value, which is right for any non empty sorted array (empty input needs a guard). Comparing i with i + 1 reads past the end. Starting k at 0 makes nums[k - 1] read the last element. A hash set is unnecessary when input is sorted.

Question 6

Move Zeroes moves every 0 to the end, keeps non zero order and runs in place. What is the time complexity of the swap based write pointer method?

Accepted Answer

O(n) Each element is read once and swapped at most once. O(n log n) would need sorting, which also breaks order. O(n^2) is shifting elements left for every zero. O(k n) is the same naive shift counted per zero.

Question 7

Trapping Rain Water (total water held between bars of an elevation map) with two pointers and running left_max and right_max. When height[l] < height[r], what is added at l?

Accepted Answer

left_max - height[l] after updating left_max When height[l] < height[r], the right side has a wall at least as tall as left_max, so left_max bounds the water at l. Using right_max overcounts when right_max is larger than left_max. Using a precomputed full right_max is the prefix array approach, not this one, and mixing them is inconsistent. height[r] minus height[l] ignores walls between.

Question 8

Squares of a sorted array that contains negatives, return sorted squares in O(n). How?

Accepted Answer

Two pointers at both ends. The largest square is at one end, so compare abs values, write the bigger square to the back of the output, and move that pointer. Pitfall: squaring then sorting is O(n log n).

Two pointers coding interview questions

More coding topics

Practise these on your commute