Count Pairs Whose Sum is Less than Target

Problem

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

Example 1

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target 
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.

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 in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
- (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
- (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
- (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
- (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
- (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
- (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
- (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
- (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target

Constraints

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

Solution

Method 1 – Two Pointers After Sorting

Intuition

If we sort the array, for each left pointer, we can use a right pointer to find the farthest index such that the sum is less than the target. This avoids checking all pairs and is efficient for small arrays.

Approach

1. Sort the array nums.
2. Initialize two pointers: l = 0, r = n - 1.
3. While l < r:
   1. If nums[l] + nums[r] < target, all pairs (l, l+1), ..., (l, r) are valid. Add (r - l) to ans and increment l.
   2. Otherwise, decrement r.
4. Return ans.

Code

C++

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.size() - 1, ans = 0;
        while (l < r) {
            if (nums[l] + nums[r] < target) {
                ans += r - l;
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
};

Go

func countPairs(nums []int, target int) int {
    sort.Ints(nums)
    l, r := 0, len(nums)-1
    ans := 0
    for l < r {
        if nums[l]+nums[r] < target {
            ans += r - l
            l++
        } else {
            r--
        }
    }
    return ans
}

Java

class Solution {
    public int countPairs(int[] nums, int target) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1, ans = 0;
        while (l < r) {
            if (nums[l] + nums[r] < target) {
                ans += r - l;
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun countPairs(nums: IntArray, target: Int): Int {
        nums.sort()
        var l = 0
        var r = nums.size - 1
        var ans = 0
        while (l < r) {
            if (nums[l] + nums[r] < target) {
                ans += r - l
                l++
            } else {
                r--
            }
        }
        return ans
    }
}

Python

class Solution:
    def countPairs(self, nums: list[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        ans = 0
        while l < r:
            if nums[l] + nums[r] < target:
                ans += r - l
                l += 1
            else:
                r -= 1
        return ans

Rust

impl Solution {
    pub fn count_pairs(nums: Vec<i32>, target: i32) -> i32 {
        let mut nums = nums;
        nums.sort();
        let (mut l, mut r, mut ans) = (0, nums.len() - 1, 0);
        while l < r {
            if nums[l] + nums[r] < target {
                ans += (r - l) as i32;
                l += 1;
            } else {
                r -= 1;
            }
        }
        ans
    }
}

TypeScript

class Solution {
    countPairs(nums: number[], target: number): number {
        nums.sort((a, b) => a - b);
        let l = 0, r = nums.length - 1, ans = 0;
        while (l < r) {
            if (nums[l] + nums[r] < target) {
                ans += r - l;
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log n), due to sorting, then O(n) for the two pointers.
• 🧺 Space complexity: O(1), if sorting in place, otherwise O(n) for the sorted array copy.