Count Pairs Whose Sum is Less than Target
EasyPrompt
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.
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
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible pair of indices (i, j) in the array such that i < j. For each pair, we calculate the sum of the corresponding elements and check if it's less than the target. If it is, we increment a counter.
Algorithm
- Initialize a counter
countto 0. - Use a nested loop. The outer loop iterates
ifrom0ton-2. - The inner loop iterates
jfromi+1ton-1. - Inside the inner loop, check if
nums[i] + nums[j] < target. - If the condition is true, increment
count. - After the loops complete, return
count.
Walkthrough
This method involves using nested loops to generate all unique pairs of elements. The outer loop runs from the first element to the second-to-last element, and the inner loop runs from the element after the current outer loop element to the last element. This ensures that each pair (i, j) is considered only once with i < j.
Here's the breakdown:
- Initialize a counter variable
countto zero. - Iterate with an index
ifrom0ton-1(wherenis the size ofnums). - Inside this loop, iterate with an index
jfromi+1ton-1. - For each pair
(i, j), check ifnums.get(i) + nums.get(j) < target. - If the condition is true, increment
count. - After the loops complete,
countwill hold the total number of pairs satisfying the condition.
import java.util.List; class Solution { public int countPairs(List<Integer> nums, int target) { int n = nums.size(); int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums.get(i) + nums.get(j) < target) { count++; } } } return count; }}Complexity
Time
O(n^2), where `n` is the number of elements in `nums`. We iterate through all possible pairs `(i, j)` with `i < j`, which amounts to n * (n-1) / 2 comparisons.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Simple to understand and implement.
It does not require any modification of the input array.
Works correctly and is acceptable for the given constraints (
n <= 50).
Cons
Inefficient for large input sizes due to its quadratic time complexity.
It performs many redundant calculations.
A more efficient approach involves sorting the array first. After sorting, we can use two pointers, one starting from the beginning (left) and one from the end (right) of the array. By comparing the sum of the elements at these pointers with the target, we can efficiently count the valid pairs in linear time after the initial sort.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize a counter
count = 0. - Initialize two pointers:
left = 0andright = n - 1. - Loop while
left < right:- If
nums[left] + nums[right] < target:- This implies that
nums[left]paired with any element fromnums[left + 1]tonums[right]will also have a sum less thantarget. - Add
right - lefttocount. - Increment
leftto consider the next element.
- This implies that
- Else (
nums[left] + nums[right] >= target):- The sum is too large. To decrease it, move the
rightpointer one step to the left (right--).
- The sum is too large. To decrease it, move the
- If
- Return
count.
Walkthrough
The key insight is that after sorting the array, if nums[left] + nums[right] < target, then nums[left] paired with any element between left+1 and right (inclusive) will also form a sum less than the target. This is because all elements nums[k] where left < k <= right are less than or equal to nums[right]. This allows us to count multiple pairs at once.
Algorithm steps:
- Sort the input array
nums. - Initialize a counter
countto 0. - Initialize two pointers:
left = 0andright = n - 1. - Loop while
left < right: a. Ifnums.get(left) + nums.get(right) < target, it means all pairs(left, left+1), (left, left+2), ..., (left, right)are valid. There areright - leftsuch pairs. Add this number tocountand moveleftone step to the right (left++) to consider the next element. b. Ifnums.get(left) + nums.get(right) >= target, the sum is too large. To reduce the sum, we must use a smaller number, so we move therightpointer one step to the left (right--). - Return the final
count.
import java.util.Collections;import java.util.List; class Solution { public int countPairs(List<Integer> nums, int target) { Collections.sort(nums); int n = nums.size(); int count = 0; int left = 0; int right = n - 1; while (left < right) { if (nums.get(left) + nums.get(right) < target) { count += (right - left); left++; } else { right--; } } return count; }}Complexity
Time
O(n log n), where `n` is the number of elements in `nums`. This is dominated by the sorting step. The two-pointer traversal itself takes O(n) time.
Space
O(log n) or O(n), depending on the space complexity of the sorting algorithm used. For instance, Timsort used in Java's `Collections.sort` can take up to O(n) space in the worst case. If we ignore the space used by sorting, it's O(1).
Trade-offs
Pros
Significantly more efficient than the brute-force approach, with a time complexity of O(n log n).
Elegant solution that cleverly uses the sorted property of the array to avoid redundant checks.
Cons
Requires modifying the input array by sorting it. If the original order must be preserved, a copy of the array is needed, which adds O(n) space complexity.
The sorting step has a time complexity of O(n log n), which might be slightly slower than brute force for very small arrays, though its overall scalability is far superior.
Solutions
Solution
class Solution {public int countPairs(List<Integer> nums, int target) { Collections.sort(nums); int ans = 0; for (int j = 0; j < nums.size(); ++j) { int x = nums.get(j); int i = search(nums, target - x, j); ans += i; } return ans; }private int search(List<Integer> nums, int x, int r) { int l = 0; while (l < r) { int mid = (l + r) >> 1; if (nums.get(mid) >= x) { r = mid; } else { l = mid + 1; } } return l; }}class Solution {public: int countPairs(vector<int> &nums, int target) { sort(nums.begin(), nums.end()); int ans = 0; for (int j = 0; j < nums.size(); ++j) { int i = lower_bound(nums.begin(), nums.begin() + j, target - nums[j]) - nums.begin(); ans += i; } return ans; }};class Solution: def countPairs(self, nums: List[int], target: int) -> int: nums . sort() ans = 0 for j, x in enumerate(nums): i = bisect_left(nums, target - x, hi=j) ans += i return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.