Count Pairs Whose Sum is Less than Target - Solution & Explanation

Problem Overview: Given an integer array nums and an integer target, count how many index pairs (i, j) exist such that i < j and nums[i] + nums[j] < target. The task is to efficiently count all valid pairs without double counting.

Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)

The simplest method checks every possible pair in the array. Use two nested loops: the outer loop fixes index i, and the inner loop iterates from i + 1 to the end. For each pair, compute nums[i] + nums[j] and increment a counter if the sum is smaller than the target. This approach is straightforward and guarantees correctness because every pair is evaluated exactly once.

The downside is scalability. The nested iteration performs roughly n(n-1)/2 comparisons, resulting in O(n²) time complexity. Space usage stays O(1) since only a counter is stored. This method works fine for small inputs and is often the first solution developers write during interviews to establish correctness before optimizing.

Approach 2: Two-Pointer Technique on Sorted Array (O(n log n) time, O(1) space)

A more efficient solution sorts the array first and then applies the two pointers technique. After sorting using sorting, place one pointer at the start (left) and another at the end (right). Evaluate the sum nums[left] + nums[right].

If the sum is less than the target, every element between left and right paired with nums[left] will also produce a valid sum because the array is sorted. That means you can add (right - left) pairs to the count at once, then move left forward. If the sum is greater than or equal to the target, decrease right to reduce the sum.

This insight avoids checking every pair individually. Sorting takes O(n log n) time, and the two-pointer scan runs in O(n). Total time complexity becomes O(n log n) with constant O(1) extra space if sorting is done in place. This approach scales much better for large arrays.

Recommended for interviews: Start with the brute force explanation to show you understand the pair constraint and index ordering. Then transition to the sorted two-pointer solution. Interviewers typically expect the two-pointer optimization because it reduces comparisons and demonstrates familiarity with common patterns used in array and two-pointer problems.