Solution: Count Pairs Whose Sum is Less than Target

Statement

You are given a 0-indexed integer array, nums, of length $n$, and an integer target. Your task is to determine the number of distinct pairs of indices $(i, j)$ such that:

• $0 \leq i < j < n$ (i.e., $i$ comes before $j$ in the array)

• The sum of the elements of the indices $(i, j)$, (i.e., $nums[i]+nums[j]$), is strictly less than target.

Constraints:

$1 \leq$ nums.length $==$ $n\leq 50$

$-50 \leq$ nums[i], target $\leq 50$

Solution

The algorithm counts the number of valid pairs in an array using sorting and binary search. We can use binary search to find valid pairs by sorting the array first. The algorithm uses a binary search for each element to determine the range of subsequent elements that can form valid pairs with it. These valid pairs are then added to a running total count of pairs.

The steps of the algorithm are as follows:

1. Sort the input array nums in ascending order for binary search.

2. A variable count is initialized to $0$ to keep track of the total number of valid pairs.

3. The algorithm iterates through each element of the array (except the last one) using an index $i$, as pairs require $j>i$. For each element nums[i]:

   1. Set the binary search range with low = i + 1 and high = len(nums).

   2. Perform binary search while low < high:

      1. Compute mid = (low + high) / 2.

      2. If nums[i] + nums[mid] < target:

         1. All elements in the range $[low, mid]$ satisfy the condition and are valid pairs.

         2. Move low = mid + 1 to explore additional valid pairs.

      3. Otherwise, reduce the range by setting high = mid to focus on smaller sum pairs.

   3. All elements in the range $[i + 1,low - 1]$ form valid pairs with nums[i]. The number of valid pairs is calculated as: count = low − (i + 1).

4. Once all elements have been processed, return the count as the total number of valid pairs.

Let’s look at the following illustration to get a better understanding of the solution: