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.
- Difficulty: Easy
- Topics: Arrays, Sorting, Binary Search, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
Hint 1
The pair condition only involves values, not positions, so sorting is free.
Hint 2
Two pointers: if the smallest plus the largest already clears the bar, every element between them pairs with the small one too.
Hint 3
That gives
right - leftpairs 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
- Sort; set
left = 0,right = n - 1. - If
a[left] + a[right] < target, addright - leftand advanceleft; otherwise retreatright. - 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 countJava
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