3Sum Smaller

3Sum Smaller

What is this problem about?

The 3Sum Smaller coding problem asks you to count the number of index triplets $(i, j, k)$ such that $i < j < k$ and $nums[i] + nums[j] + nums[k] < target$. Unlike other 3Sum variations, you don't need the actual triplets—just the total count of combinations that satisfy the inequality.

Why is this asked in interviews?

Asked by Microsoft and Oracle, this problem tests a candidate's ability to use the properties of a sorted array to count multiple solutions at once. It’s an exercise in efficiency; if you find one valid boundary, you can mathematically infer many other valid solutions without iterating through them.

Algorithmic pattern used

This problem utilizes the Two Pointers interview pattern on a sorted array. The key insight is: if $nums[i] + nums[left] + nums[right] < target$, then all elements between left and right will also satisfy the condition when paired with nums[i] and nums[left]. This allows you to add (right - left) to your count in $O(1)$ time.

Example explanation

Array: [-2, 0, 1, 3], target = 2.

1. Sort the array (already sorted).
2. **Fix -2**: left = 0, right = 3.

• Sum = -2 + 0 + 3 = 1.
• Since $1 < 2$, all pairs between left (0) and right (3) work. This includes $(0, 3)$ and $(0, 1)$.
• Count += $(3 - 1) = 2$.

1. Repeat for other fixed indices.

Common mistakes candidates make

• Iterating for Count: After finding that the sum is smaller than the target, some candidates use another loop to count the elements instead of using the $right - left$ math, which reverts the complexity to $O(N^3)$.
• Index Confusion: Mixing up the original indices with the sorted indices. Since the problem asks for the count of index triplets, sorting is allowed as long as you are just counting the combinations of values.

Interview preparation tip

Look for "counting" problems where you can avoid an inner loop by using the distance between two pointers. This "sliding window count" logic is a very common optimization in competitive programming.