Scale Engineer

Count Pairs Whose Sum is Less than Target

Easy
#2524Time: 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.2 companies
Patterns
Two Pointers
Algorithms
Binary SearchSorting
Data structures
Array
Companies
Accenturejosh technology

Prompt

Given a 0-indexed integer array 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 count to 0.
  • Use a nested loop. The outer loop iterates i from 0 to n-2.
  • The inner loop iterates j from i+1 to n-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:

  1. Initialize a counter variable count to zero.
  2. Iterate with an index i from 0 to n-1 (where n is the size of nums).
  3. Inside this loop, iterate with an index j from i+1 to n-1.
  4. For each pair (i, j), check if nums.get(i) + nums.get(j) < target.
  5. If the condition is true, increment count.
  6. After the loops complete, count will 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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem