Count Pairs Whose Sum is Less than Target

Easy
268.

Count Pairs Whose Sum is Less than Target

Count Pairs Whose Sum is Less than Target is an easy coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

Given an integer array nums and an integer target, return the number of index pairs (i, j) with 0 <= i < j < nums.length and nums[i] + nums[j] < target.

Example 1

Input
nums = [-1,1,2,3,1], target = 2
Output
3
Explanation
The pairs are (0,1), (0,2) and (0,4).

Example 2

Input
nums = [-6,2,5,-2,-7,-1,3], target = -2
Output
10

Example 3

Input
nums = [1,1], target = 3
Output
1

Constraints

  • 1 <= nums.length <= 40
  • -50 <= nums[i], target <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var countPairs = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Pairs Whose Sum is Less than Target — Solution

Count Pairs Whose Sum is Less than Target solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Pairs Whose Sum is Less than Target is an easy coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

Problem statement

Given an integer array nums and an integer target, return the number of index pairs (i, j) with 0 <= i < j < nums.length and nums[i] + nums[j] < target.

Example 1

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: The pairs are (0,1), (0,2) and (0,4).

Example 2

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10

Example 3

Input: nums = [1,1], target = 3
Output: 1

Constraints

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

Hints for Count Pairs Whose Sum is Less than Target

  1. Hint 1

    The pair condition only involves values, not positions, so sorting is free.

  2. Hint 2

    Two pointers: if the smallest plus the largest already clears the bar, every element between them pairs with the small one too.

  3. Hint 3

    That gives right - left pairs at once — then advance the left pointer.

How to solve Count Pairs Whose Sum is Less than Target

Sort, then two pointers: if the smallest plus the largest is below the target, every element between also pairs with the smallest, contributing right - left pairs at once.

Approach

  1. Sort; set left = 0, right = n - 1.
  2. If a[left] + a[right] < target, add right - left and advance left; otherwise retreat right.
  3. Stop when the pointers meet.

Why it works

When the pair with the largest partner succeeds, all smaller partners succeed too, so the batch count is exact; when it fails, the largest value cannot pair with anything remaining and is retired.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • The condition involves values only, so sorting does not change the count of index pairs.

Reference solution

Python

def countPairs(nums, target: int) -> int:
    a = sorted(nums)
    left, right, count = 0, len(a) - 1, 0
    while left < right:
        if a[left] + a[right] < target:
            count += right - left
            left += 1
        else:
            right -= 1
    return count

Java

public static int countPairs(int[] nums, int target) {
    int[] a = Arrays.copyOf(nums, nums.length);
    Arrays.sort(a);
    int left = 0, right = a.length - 1, count = 0;
    while (left < right) {
        if (a[left] + a[right] < target) {
            count += right - left;
            left++;
        } else {
            right--;
        }
    }
    return count;
}

C++

int countPairs(vector<int>& nums, int target) {
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int left = 0, right = (int) a.size() - 1, count = 0;
    while (left < right) {
        if (a[left] + a[right] < target) {
            count += right - left;
            left++;
        } else {
            right--;
        }
    }
    return count;
}

JavaScript

var countPairs = function(nums, target) {
    const a = nums.slice().sort(function(x, y) { return x - y; });
    let left = 0, right = a.length - 1, count = 0;
    while (left < right) {
        if (a[left] + a[right] < target) {
            count += right - left;
            left++;
        } else {
            right--;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms