Count Pairs Whose Sum is Less than Target

Count pairs (i, j) with i < j and nums[i] + nums[j] < target — sort then converging two pointers.

Easy

Time O(n log n) Space O(1)

LeetCode

May 16, 2026 3 min read

Problem#

Count pairs (i, j) with i < j and nums[i] + nums[j] < target.

Examples#

nums = [-1,1,2,3,1], target = 2 → 3

Constraints#

1 <= n <= 50.

Approach#

Sort. For each i, binary-search the largest j > i with nums[i] + nums[j] < target; add j - i to the count. Two-pointer converging version is equivalent and slightly cleaner.

Solution#

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;
    }
};

import "sort"

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

from typing import List

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

function countPairs(nums, target) {
    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;
}

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int l = 0, r = nums.size() - 1, ans = 0;
        while (l < r) {
            if (nums.get(l) + nums.get(r) < target) {
                ans += r - l;
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

function 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;
}

Editorial#

After sorting, the two-pointer trick gives O(n): for each l, the largest valid r is non-increasing as l grows. The count r - l adds every pair (l, m) with l < m <= r.

Complexity#

Time: O(n log n).
Space: O(1).

Concept revision#

3Sum
Two Sum

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#