Count Pairs Whose Sum is Less than Target

Difficulty: Easy | Acceptance: 87.70% | Paid: No Topics: Array, Two Pointers, Binary Search, Sorting

Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

• Examples
• Constraints
• Brute Force
• Sorting + Two Pointers
• Sorting + Binary Search

Examples

Example 1:

Input: nums = [-1,1,2,3,0], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions below:
- (0, 1) -> 0 < 2
- (0, 2) -> 1 < 2
- (0, 4) -> -1 < 2
Note that indices 2 and 4 are not valid because their sum is 3 which is not less than 2.

Example 2:

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions below:
- (0, 1) -> -4 < -2
- (0, 3) -> -8 < -2
- (0, 4) -> -13 < -2
- (0, 5) -> -7 < -2
- (0, 6) -> -3 < -2
- (1, 3) -> 0 < -2
- (1, 4) -> -5 < -2
- (1, 5) -> 1 < -2
- (3, 4) -> -9 < -2
- (3, 5) -> -3 < -2

Constraints

2 <= nums.length == n <= 50
-50 <= nums[i], target <= 50

Brute Force

Intuition Iterate through every possible pair of indices in the array and check if their sum meets the condition.

Steps

• Initialize a counter to 0.
• Use a nested loop where the outer loop runs from index i to n-1 and the inner loop runs from i+1 to n-1.
• For each pair (i, j), check if nums[i] + nums[j] < target.
• If true, increment the counter.
• Return the counter.

from typing import List

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        count = 0
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] < target:
                    count += 1
        return count

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple to implement but inefficient for large arrays.

Sorting + Two Pointers

Intuition Sorting the array allows us to use the two-pointer technique. If the sum of the smallest and largest elements is less than the target, then all pairs involving the smallest element and any element up to the largest will also satisfy the condition.

Steps

• Sort the array in non-decreasing order.
• Initialize two pointers, left at the start (0) and right at the end (n-1).
• While left < right:
  • Calculate the sum of nums[left] and nums[right].
  • If the sum is less than target, it means all elements from left+1 to right will also form a valid pair with nums[left] (since the array is sorted). Add right - left to the count and increment left.
  • If the sum is greater than or equal to target, decrement right to try a smaller sum.
• Return the total count.

from typing import List

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        count = 0
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] + nums[right] < target:
                count += right - left
                left += 1
            else:
                right -= 1
        return count

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting algorithm.
• Notes: More efficient than brute force for larger inputs.

Sorting + Binary Search

Intuition After sorting, for each element nums[i], we can find the largest element nums[j] (where j > i) such that nums[i] + nums[j] < target. Since the array is sorted, we can use binary search to find the boundary of valid values for j.

Steps

• Sort the array.
• Initialize count to 0.
• Iterate through the array with index i from 0 to n-1.
• For each i, perform a binary search on the subarray nums[i+1 ... n-1] to find the first index j where nums[i] + nums[j] >= target.
• All indices from i+1 to j-1 satisfy the condition. Add j - (i + 1) to the count.
• Return the count.

from typing import List
import bisect

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        count = 0
        n = len(nums)
        for i in range(n):
            val = target - nums[i]
            j = bisect.bisect_left(nums, val, i + 1)
            count += j - (i + 1)
        return count

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting algorithm.
• Notes: Useful when you need to find specific boundaries or counts relative to a sorted array.