Count Pairs Whose Sum is Less than Target solution and explanation
Google
9 more videos on this problem
LeetCode 2824: Count Pairs Whose Sum is Less than TargetEngineering Digest · 5:46 · 7K views
2824. Count Pairs Whose Sum is Less than Target (Leetcode Easy)Programming Live with Larry · 2:12 · 1K views
LeetCode 2824 : Count Pairs Whose Sum is Less than Target || EASY || C++ ||JAVA || Detailed SolutionCodeGPT · 9:22 · 1K views
Unlocking LeetCode 2824. Count Pairs Whose Sum is Less than Target Two-Pointer TechniquevanAmsen · 4:30 · 1K views
2824 Count Pairs Whose Sum is Less than Target || Leetcode || Biweekly || Solution ExplainCodeLuv · 2:41 · 1K views
LeetCode 2824 | Count Pairs Whose Sum is Less than Target | easy | Python code | Binary searchTechtonic Knights · 5:07 · 602 views
Leetcode Problem 2824. Count Pairs Whose Sum is Less than Target. Leetcode Solution 2824 EASY.CodingForBeginners · 3:18 · 589 views
leetcode 2824 Count Pairs Whose Sum is Less Than Target - two-pointer trickCode-Yao · 6:42 · 477 views
Count Pairs Whose Sum is Less than Target | Leetcode 2824 | Approach + Code with explanation.Pirai's Academy · 12:30 · 454 views
Leetcode 6954 || Count Pairs Whose Sum is Less than Target || Leetcode Weekly Easy || cppKomal Pal · 5:05 · 177 views
The problem
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
Approach overview
Problem Overview: Given an integer array nums and an integer target, count how many index pairs (i, j) exist such that i < j and nums[i] + nums[j] < target. The task is to efficiently count all valid pairs without double counting.
Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)
The simplest method checks every possible pair in the array. Use two nested loops: the outer loop fixes index i, and the inner loop iterates from i + 1 to the end. For each pair, compute nums[i] + nums[j] and increment a counter if the sum is smaller than the target. This approach is straightforward and guarantees correctness because every pair is evaluated exactly once.
The downside is scalability. The nested iteration performs roughly n(n-1)/2 comparisons, resulting in O(n²) time complexity. Space usage stays O(1) since only a counter is stored. This method works fine for small inputs and is often the first solution developers write during interviews to establish correctness before optimizing.
Approach 2: Two-Pointer Technique on Sorted Array (O(n log n) time, O(1) space)
A more efficient solution sorts the array first and then applies the two pointers technique. After sorting using sorting, place one pointer at the start (left) and another at the end (right). Evaluate the sum nums[left] + nums[right].
If the sum is less than the target, every element between left and right paired with nums[left] will also produce a valid sum because the array is sorted. That means you can add (right - left) pairs to the count at once, then move left forward. If the sum is greater than or equal to the target, decrease right to reduce the sum.
This insight avoids checking every pair individually. Sorting takes O(n log n) time, and the two-pointer scan runs in O(n). Total time complexity becomes O(n log n) with constant O(1) extra space if sorting is done in place. This approach scales much better for large arrays.
Recommended for interviews: Start with the brute force explanation to show you understand the pair constraint and index ordering. Then transition to the sorted two-pointer solution. Interviewers typically expect the two-pointer optimization because it reduces comparisons and demonstrates familiarity with common patterns used in array and two-pointer problems.
Approach 1: Brute Force Approach
This approach involves iterating over all possible pairs (i, j) where 0 <= i < j < n, and checking if their sum is less than the target. If so, count that pair.
This is a straightforward method but could become inefficient with larger arrays due to its O(n^2) time complexity.
def count_pairs(nums, target):
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] < target:
count += 1
return count
nums = [-1, 1, 2, 3, 1]
target = 2
print(count_pairs(nums, target))import java.util.*;
public class Counter {
public static int countPairs(int[] nums, int target) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] < target) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {-1, 1, 2, 3, 1};
int target = 2;
System.out.println(countPairs(nums, target));
}
}#include <iostream>
#include <vector>
using namespace std;
int countPairs(vector<int>& nums, int target) {
int count = 0;
for(size_t i = 0; i < nums.size(); ++i) {
for(size_t j = i + 1; j < nums.size(); ++j) {
if(nums[i] + nums[j] < target) {
count++;
}
}
}
return count;
}
int main() {
vector<int> nums = {-1, 1, 2, 3, 1};
int target = 2;
cout << countPairs(nums, target) << endl;
return 0;
}function countPairs(nums, target) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] < target) {
count++;
}
}
}
return count;
}
const nums = [-1, 1, 2, 3, 1];
const target = 2;
console.log(countPairs(nums, target));#include <stdio.h>
int countPairs(int* nums, int numsSize, int target) {
int count = 0;
for(int i = 0; i < numsSize - 1; i++) {
for(int j = i + 1; j < numsSize; j++) {
if(nums[i] + nums[j] < target) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {-1, 1, 2, 3, 1};
int target = 2;
printf("%d\n", countPairs(nums, 5, target));
return 0;
}using System;
public class Solution {
public static int CountPairs(int[] nums, int target) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (nums[i] + nums[j] < target) {
count++;
}
}
}
return count;
}
public static void Main() {
int[] nums = {-1, 1, 2, 3, 1};
int target = 2;
Console.WriteLine(CountPairs(nums, target));
}
}This Python code counts valid pairs using nested loops. The outer loop selects the first element of the pair and the inner loop selects the second, checking if their sum is less than the target.
Time Complexity: O(n^2) due to the use of a nested loop structure.
Space Complexity: O(1) since only a simple counter is used.
Approach 2: Two-Pointer Technique on Sorted Array
This approach leverages sorting the array to use the two-pointer technique efficiently. By sorting, we can move pointers from both ends of the list towards the center to find valid pairs, reducing unnecessary calculations.
def count_pairs(nums, target):
nums.sort()
count = 0
left, right = 0, len(nums) - 1
while left < right:
if nums[left] + nums[right] < target:
count += (right - left)
left += 1
else:
right -= 1
return count
nums = [-1, 1, 2, 3, 1]
target = 2
print(count_pairs(nums, target))import java.util.Arrays;
public class Counter {
public static int countPairs(int[] nums, int target) {
Arrays.sort(nums);
int count = 0, left = 0, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] < target) {
count += (right - left);
left++;
} else {
right--;
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {-1, 1, 2, 3, 1};
int target = 2;
System.out.println(countPairs(nums, target));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int countPairs(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int count = 0, i = 0, j = nums.size() - 1;
while (i < j) {
if (nums[i] + nums[j] < target) {
count += (j - i);
i++;
} else {
j--;
}
}
return count;
}
int main() {
vector<int> nums = {-1, 1, 2, 3, 1};
int target = 2;
cout << countPairs(nums, target) << endl;
return 0;
}function countPairs(nums, target) {
nums.sort((a, b) => a - b);
let count = 0;
let left = 0, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] < target) {
count += (right - left);
left++;
} else {
right--;
}
}
return count;
}
const nums = [-1, 1, 2, 3, 1];
const target = 2;
console.log(countPairs(nums, target));#include <stdio.h>
#include <stdlib.h>
int cmpfunc (const void * a, const void * b) {
return (*(int*)a - *(int*)b);
}
int countPairs(int* nums, int numsSize, int target) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
int count = 0, i = 0, j = numsSize - 1;
while (i < j) {
if (nums[i] + nums[j] < target) {
count += (j - i);
i++;
} else {
j--;
}
}
return count;
}
int main() {
int nums[] = {-1, 1, 2, 3, 1};
int target = 2;
printf("%d\n", countPairs(nums, 5, target));
return 0;
}using System;
public class Solution {
public static int CountPairs(int[] nums, int target) {
Array.Sort(nums);
int count = 0, left = 0, right = nums.Length - 1;
while (left < right) {
if (nums[left] + nums[right] < target) {
count += (right - left);
left++;
} else {
right--;
}
}
return count;
}
public static void Main() {
int[] nums = {-1, 1, 2, 3, 1};
int target = 2;
Console.WriteLine(CountPairs(nums, target));
}
}This Python code sorts the array and uses two pointers to tally pairs. When a valid pair sums to less than the target, all objectives between the pointers embody valid formations, thus minimizing unnecessary checks.
Time Complexity: O(n log n), derived from the sort operation, bolstered by an O(n) run separable via pair assessment.
Space Complexity: O(1). Sorting is performed in-place.
Approach 3: Sorting + Binary Search
First, we sort the array nums. Then, for each j, we use binary search in the range [0, j) to find the first index i that is greater than or equal to target - nums[j]. All indices k in the range [0, i) meet the condition, so the answer increases by i.
After the traversal, we return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
function countPairs(nums: number[], target: number): number {
nums.sort((a, b) => a - b);
let ans = 0;
const search = (x: number, r: number): number => {
let l = 0;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let j = 0; j < nums.length; ++j) {
const i = search(target - nums[j], j);
ans += i;
}
return ans;
}func countPairs(nums []int, target int) (ans int) {
sort.Ints(nums)
for j, x := range nums {
i := sort.SearchInts(nums[:j], target-x)
ans += i
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) due to the use of a nested loop structure. |
| Two-Pointer Technique on Sorted Array | Time Complexity: O(n log n), derived from the sort operation, bolstered by an O(n) run separable via pair assessment. |
| Sorting + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Small input sizes or when demonstrating baseline logic in interviews |
| Two-Pointer on Sorted Array | O(n log n) | O(1) | Best general solution for unsorted arrays where pair counting is required |
Frequently asked questions
Is Count Pairs Whose Sum is Less than Target easy or hard?
Count Pairs Whose Sum is Less than Target is categorized as an Easy problem. The brute force approach is simple to implement, and the optimized solution introduces the common two-pointer pattern after sorting. It is often used to practice array traversal and pair-counting strategies.
Count Pairs Whose Sum is Less than Target Python/Java solution
Python and Java implementations usually follow the same structure: sort the array, initialize two pointers, and count valid pairs while adjusting the pointers. The logic remains identical across languages, and the overall complexity stays O(n log n) due to sorting.
How to solve Count Pairs Whose Sum is Less than Target in O(n)?
A pure O(n) solution is possible only if the array is already sorted. With a sorted array, use two pointers: one at the start and one at the end. If the sum is less than the target, add (right - left) to the count and move the left pointer forward; otherwise move the right pointer backward. This processes the array in a single pass.
What is the best approach for Count Pairs Whose Sum is Less than Target?
The optimal approach sorts the array and uses the two-pointer technique. After sorting, place one pointer at the start and one at the end. If the sum is less than the target, all elements between the pointers form valid pairs with the left value, allowing you to count multiple pairs at once. This reduces the complexity to O(n log n) due to sorting and O(n) for the scan.
Is Count Pairs Whose Sum is Less than Target asked at Google/Amazon/Meta?
Pair counting and two-pointer problems frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying patterns—sorting plus two pointers or pair sum analysis—are common interview topics used to evaluate array manipulation and algorithmic reasoning.
What data structure is used in Count Pairs Whose Sum is Less than Target?
The problem primarily uses arrays combined with algorithmic techniques such as sorting and the two-pointer pattern. No additional complex data structures are required. The optimized approach relies on the sorted order of the array to efficiently count valid pairs.
What is the time complexity of Count Pairs Whose Sum is Less than Target?
The brute force approach runs in O(n²) time because it checks every pair of indices. The optimized solution sorts the array in O(n log n) time and then performs a linear two-pointer traversal in O(n). The overall optimal complexity is O(n log n) with O(1) additional space.