Count Pairs Whose Sum is Less than Target

Count Pairs Whose Sum is Less than Target

What is this problem about?

The "Count Pairs Whose Sum is Less than Target interview question" is a fundamental array optimization task. You are given an array of integers and a target. You need to find the number of pairs $(i, j)$ such that $0 \leq i < j < n$ and nums[i] + nums[j] < target. This problem tests your ability to move beyond brute-force counting and utilize sorting to improve performance.

Why is this asked in interviews?

Companies like Meta and Amazon use the "Count Pairs Whose Sum is Less than Target coding problem" to assess a candidate's understanding of the "Two Pointers interview pattern." It evaluates the ability to recognize that sorting the array doesn't change the set of possible pairs but allows for a much more efficient search strategy ($O(N \log N)$ vs $O(N^2)$).

Algorithmic pattern used

This problem is solved using the Sorting and Two Pointers pattern.

1. Sort: Arrange the array in ascending order.
2. Pointers: Initialize left = 0 and right = n - 1.
3. Logic:
   • If nums[left] + nums[right] < target, then because the array is sorted, every element between left and right will also satisfy the condition when paired with nums[left]. There are right - left such pairs. Add this to your count and increment left.
   • If nums[left] + nums[right] >= target, then nums[right] is too large to pair with any element. Decrement right.

Example explanation

Array: [-1, 1, 2, 3, 1], Target: 2

1. Sorted: [-1, 1, 1, 2, 3].
2. left=0 (-1), right=4 (3): Sum = 2. Not < 2. right--.
3. left=0 (-1), right=3 (2): Sum = 1. < 2. Pairs: (-1, 1), (-1, 1), (-1, 2). Total += 3. left++.
4. left=1 (1), right=3 (2): Sum = 3. Not < 2. right--. ... Result: 3.

Common mistakes candidates make

• Not Sorting: Attempting to use two pointers on an unsorted array, which doesn't work because there is no monotonic relationship between indices and sums.
• Counting Individual Pairs: Incrementing the counter by 1 inside the while loop instead of adding right - left. This loses the $O(N)$ efficiency of the two-pointer pass.
• Strict Inequality: Forgetting that the condition is strictly less than target, not less than or equal to.

Interview preparation tip

Master the "Two Pointers" technique for inequalities. Whenever you need to count pairs based on a sum, sorting the array usually unlocks a linear or $O(N \log N)$ solution.