2824. Count Pairs Whose Sum is Less than Target
Problem Description
The task at hand is to find the number of unique pairs (i, j)
within an array nums
, where nums
has n
elements, such that when we add the elements at positions i
and j
, the sum is less than a given target
value. It's important to note that the array is 0-indexed (meaning indexing starts from 0), and the pairs must satisfy 0 <= i < j < n
, which ensures that i
is strictly less than j
, and j
is within the bounds of the array.
To simplify, given an array and a numeric target, we're looking for pairs of numbers in the array that add up to a number less than the target. The problem asks for a count of such pairs.
Intuition
When tackling this problem, the intuition is that if we have an array sorted in increasing order, we can efficiently find the threshold beyond which a pair of numbers would exceed the target value. Sorting helps constrain the search space when looking for the second number of the pair.
Here's the step-by-step approach to arrive at the solution:
-
Sort the Array: Start by sorting
nums
in non-decreasing order. This allows us to use the property that ifnums[k]
is too large for somei
when paired withnums[j]
, thennums[k+1], nums[k+2], ..., nums[n-1]
will also be too large. -
Two-Pointer Strategy: We could use a two-pointer strategy to find the count of valid pairs, but the issue is that it runs in O(n^2) time in its naĆÆve form because we'd check pairs
(i, j)
exhaustively. -
Binary Search Optimization: To optimize, we turn to binary search (
bisect_left
in Python). For each numberx
in our sortednums
at indexj
, we want to find the largest indexi
such thati < j
andnums[i] + x < target
, which gives us the number of valid pairs with the second number beingx
. -
Counting Pairs: The function
bisect_left
returns the index wheretarget - x
would be inserted to maintain the sorted order, which is conveniently the indexi
we are looking for. The value ofi
represents how many numbers in the sorted array are less thantarget - x
whenx
is the second element of the pair. Sincej
is the current index, and we're interested in indices less thanj
, by passinghi=j
tobisect_left
, we ensure that.
By looping through all elements x
of the sorted nums
and applying binary search, we get the count of valid pairs for each element. Summing these counts gives us the total number of pairs that satisfy the problem's criteria.
The elegance of this solution lies in effectively reducing the complexity from O(n^2) to O(n log n) due to sorting and the binary search, which takes O(log n) time per element.
Learn more about Two Pointers and Sorting patterns.
Solution Approach
The given solution implements the optimized approach using sorting and binary search as follows:
-
Sorting: First, the list
nums
is sorted in non-decreasing order. This allows us to leverage the fact that once we find a pair that satisfies our condition (nums[i] + nums[j] < target
), any smalleri
for the samej
will also satisfy the condition, since the array is sorted.1nums.sort()
-
Binary Search: The binary search is done using Python's
bisect_left
method from thebisect
module.1i = bisect_left(nums, target - x, hi=j)
Here, the
bisect_left
method is used to find the indexi
at which we could inserttarget - x
while maintaining the sorted order of the array. It searches in the slice ofnums
up to the indexj
, which ensures that we are only considering elements at indices less thanj
. The elementx
corresponds to the second number in our pair, and the indexj
is its position in the sorted array. -
Loop and Count: For every number
x
in our sortednums
, represented by the loop indexj
, we find how many numbers are to the left ofj
that could form a valid pair withx
. This is done by adding the result of the binary search to our answerans
.1ans = 0 2for j, x in enumerate(nums): 3 i = bisect_left(nums, target - x, hi=j) 4 ans += i
-
Return Result: After iterating through all the elements of the sorted array and accumulating the valid pairs count in
ans
, the final step is to returnans
, which holds the total number of valid pairs found.1return ans
In summary, the solution harnesses the binary search algorithm to efficiently find for each element x
in nums
the number of elements to the left that can be paired with x
to form a sum less than target
. The sorting step beforehand ensures that the binary search operation is possible. The time complexity of this algorithm is O(n log n), with O(n log n) for the sorting step and O(n log n) for the binary searches (O(log n) for each of the n elements).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have an array nums = [7, 3, 5, 1]
and the target = 8
. We want to find the number of unique pairs (i, j)
such that nums[i] + nums[j] < target
and 0 <= i < j < n
.
Here's how we apply the solution approach to our example:
-
Sort the Array: We start by sorting
nums
to get[1, 3, 5, 7]
. -
Binary Search and Loop:
- Let's begin the loop with
j = 1
(x = 3
), sincei < j
. Forx = 3
, we want to find how many numbers to the left are less thantarget - x
(8 - 3 = 5
). We usebisect_left
and obtaini = bisect_left([1, 3, 5, 7], 5, hi=1) = 1
. This means starting from the index 0, there is 1 number that can be paired with 3 to have a sum less than 8. - Next,
j = 2
(x = 5
). We're looking for numbers less than8 - 5 = 3
. Indexi
is found bybisect_left([1, 3, 5, 7], 3, hi=2) = 1
. Again, 1 number left of index 2 can pair with 5. - Then, for
j = 3
(x = 7
),target - x
is8 - 7 = 1
. Callingbisect_left([1, 3, 5, 7], 1, hi=3) = 0
givesi = 0
, but there are no numbers less than 1 in the array, so we cannot form any new pairs with 7.
- Let's begin the loop with
-
Counting Pairs:
- For each
j
, we addi
to our total countans
. - From our steps:
ans = 1 + 1 + 0 = 2
.
- For each
-
Return Result: With the loop completed, we've determined there are 2 unique pairs that meet the criteria:
(1, 3)
and(1, 5)
. Thus, we returnans = 2
.
This example illustrates how sorting the array, using a two-pointer approach, and optimizing with binary search allows us to efficiently solve this problem.
Solution Implementation
1from bisect import bisect_left
2from typing import List
3
4class Solution:
5 def countPairs(self, nums: List[int], target: int) -> int:
6 # Sort the list of numbers first to use binary search
7 nums.sort()
8 count = 0 # Initialize count of pairs
9
10 # Iterate through the sorted list
11 for index, value in enumerate(nums):
12 # Determine the index in the list where the pair's complement would be inserted
13 # to maintain sorted order. Only consider elements before the current one.
14 insertion_point = bisect_left(nums, target - value, hi=index)
15
16 # Add the number of eligible pair counts.
17 # Since we're searching in a sorted list up to the current index, all indices
18 # before the insertion point are valid pairs with the current value.
19 count += insertion_point
20
21 return count # Return the total count of pairs
22
1class Solution {
2 // Method to count the number of pairs that, when added, equals the target value
3 public int countPairs(List<Integer> nums, int target) {
4 // Sort the list first to apply binary search
5 Collections.sort(nums);
6 int pairCount = 0;
7
8 // Iterate through each element in the list to find valid pairs
9 for (int j = 0; j < nums.size(); ++j) {
10 int currentVal = nums.get(j);
11 // Search for index of the first number that is greater than or equal to (target - currentVal)
12 int index = binarySearch(nums, target - currentVal, j);
13 // Increment the pair count by the number of valid pairs found
14 pairCount += index;
15 }
16 return pairCount;
17 }
18
19 // Helper method to perform a binary search and find the first element greater than or equal to x before index r
20 private int binarySearch(List<Integer> nums, int x, int rightBound) {
21 int left = 0;
22 while (left < rightBound) {
23 // Find the middle index between left and rightBound
24 int mid = (left + rightBound) >> 1; // equivalent to (left + rightBound) / 2
25 // If the value at mid is greater than or equal to x, move the rightBound to mid
26 if (nums.get(mid) >= x) {
27 rightBound = mid;
28 } else {
29 // Otherwise, move the left bound just beyond mid
30 left = mid + 1;
31 }
32 }
33 // Return the left bound as the first index greater than or equal to x
34 return left;
35 }
36}
37
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to count pairs with a sum equal to a given target.
7 int countPairs(vector<int>& nums, int target) {
8 // First, we sort the input vector which enables us to use binary search.
9 sort(nums.begin(), nums.end());
10
11 // This variable will hold the count of valid pairs.
12 int pairCount = 0;
13
14 // Iterate through the sorted vector to find valid pairs.
15 for (int rightIndex = 0; rightIndex < nums.size(); ++rightIndex) {
16 // For each element at rightIndex, find the first number in the range [0, rightIndex)
17 // that, when added to nums[rightIndex], would equal at least the target.
18 // lower_bound returns an iterator pointing to the first element not less than target - nums[rightIndex].
19 int leftIndex = lower_bound(nums.begin(), nums.begin() + rightIndex, target - nums[rightIndex]) - nums.begin();
20
21 // The number of valid pairs for this iteration is the index found by lower_bound (leftIndex),
22 // because all previous elements (0 to leftIndex-1) paired with nums[rightIndex] will have a sum less than target.
23 pairCount += leftIndex;
24 }
25
26 // Return the total count of valid pairs.
27 return pairCount;
28 }
29};
30
1// Counts the number of pairs in the 'nums' array that add up to the given 'target'.
2function countPairs(nums: number[], target: number): number {
3 // Sort the array in ascending order to facilitate binary search.
4 nums.sort((a, b) => a - b);
5 let pairCount = 0; // Initialize the count of pairs.
6
7 // A binary search function to find the index of the smallest number in 'nums'
8 // that is greater than or equal to 'x', up to but not including index 'rightLimit'.
9 function binarySearch(x: number, rightLimit: number): number {
10 let left = 0;
11 let right = rightLimit;
12 while (left < right) {
13 // Calculate the middle index.
14 const mid = Math.floor((left + right) / 2);
15 if (nums[mid] >= x) {
16 // If the element at 'mid' is greater than or equal to 'x',
17 // narrow down the search to the left half including 'mid'.
18 right = mid;
19 } else {
20 // Otherwise, narrow down the search to the right half excluding 'mid'.
21 left = mid + 1;
22 }
23 }
24 // Return the index of the smallest number greater than or equal to 'x'.
25 return left;
26 }
27
28 // Iterate through the sorted array to find all pairs that meet the condition.
29 for (let j = 0; j < nums.length; ++j) {
30 // Use the binary search function to find the number of elements
31 // that can be paired with 'nums[j]' to be less than the 'target'.
32 const index = binarySearch(target - nums[j], j);
33 // Add the number of valid pairs to 'pairCount'.
34 pairCount += index;
35 }
36
37 // Return the total count of valid pairs.
38 return pairCount;
39}
40
Time and Space Complexity
The code provided is using a sorted array to count pairs that add up to a specific target value.
Time Complexity:
The time complexity of the sorting operation at the beginning is O(n log n)
where n
is the total number of elements in the nums
list.
The for loop runs in O(n)
time since it iterates over each element in the list once.
Inside the loop, the bisect_left
function is called, which performs a binary search and runs in O(log j)
time where j
is the current index of the loop.
Since bisect_left
is called inside the loop, we need to consider its time complexity for each iteration. The average time complexity of bisect_left
across all iterations is O(log n)
, making the for loop's total time complexity O(n log n)
.
Hence, the overall time complexity, considering both the sort and the for loop operations, is O(n log n)
because they are not nested but sequential.
Space Complexity:
The space complexity is O(1)
assuming the sort is done in-place (Python's Timsort, which is typically used in .sort()
, can be O(n)
in the worst case for space, but this does not count the input space). If we consider the input space as well, then the space complexity is O(n)
. There are no additional data structures that grow with input size n
used in the algorithm outside of the sorting algorithm's temporary space. The variables ans
, j
, and x
use constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we