#2824

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Count Pairs Whose Sum is Less than Target

This problem asks you to count all index pairs in an array whose sum is strictly less than a given target value efficiently.

array two pointers binary search sorting

Problem Statement

Given an integer array nums and an integer target, count the number of index pairs (i, j) where 0 <= i < j < nums.length and nums[i] + nums[j] is strictly less than target. Return the total count of such pairs.

Constraints ensure nums has length between 1 and 50 and each element along with target is between -50 and 50. Example cases show counting valid pairs by checking sums without exceeding the target.

Examples

Example 1

Input: nums = [-1,1,2,3,1], target = 2

Output: 3

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

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

Solution Approach

Sort and Two-Pointer Traversal

Sort nums and initialize two pointers: one at the start and one at the end. Move pointers to count all pairs whose sum is less than target, advancing the left pointer when the sum is valid and decrementing the right pointer otherwise.

Binary Search for Upper Bound

After sorting, for each index i, use binary search to find the largest index j where nums[i] + nums[j] < target. This directly counts valid pairs for i without scanning all j manually.

Brute-Force Validation

Iterate over all pairs (i, j) with nested loops and check if nums[i] + nums[j] < target. Useful for small input sizes to verify correctness and for testing optimized solutions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n^2) for brute-force to O(n log n) for sorting plus binary search per element. Space complexity is O(1) extra for pointers or O(n) if storing sorted array separately.

What Interviewers Usually Probe

Look for solutions that avoid counting pairs multiple times.
Consider if sorting can simplify pair comparisons.
Check if binary search reduces the number of sum calculations per index.

Common Pitfalls or Variants

Common pitfalls

Forgetting to only count pairs where i < j, leading to overcounting.
Neglecting negative numbers and assuming all sums increase with indices.
Using inefficient brute-force for large arrays without noticing sorting opportunities.

Follow-up variants

Count pairs whose sum is less than or equal to target.
Count triplets with sum less than target using similar binary search logic.
Return the actual list of valid pairs instead of just the count.

FAQ

What is the recommended approach for counting pairs less than target?

Sorting the array and applying a two-pointer or binary search approach efficiently counts valid pairs while avoiding double-counting.

Can a brute-force solution pass this problem?

Yes, because the array length is at most 50, brute-force nested loops can compute the count correctly within acceptable time limits.

How do negative numbers affect pair counting?

Negative numbers can decrease sums, so sorting is important and binary search ensures you correctly capture all pairs less than the target.

Does the order of the array matter?

The original order does not affect the count as long as you check all i < j pairs; sorting simplifies the logic for efficient methods.

Which pattern does this problem exemplify?

This problem is a binary search over the valid answer space pattern, where each element's valid pairing range is found efficiently.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

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 ans

Continue Practicing

#2576 find the maximum number of marked indices #2563 count the number of fair pairs #3186 maximum total damage with spell casting