LeetCode 2824 - Count Pairs Whose Sum is Less than Target

LeetCode Problem 2824

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

This problem asks us to count the number of unique pairs of indices (i, j) in a given integer array nums such that the sum of the two numbers at those indices is strictly less than a given target. The array is 0-indexed, so valid pairs satisfy 0 <= i < j < n, where n is the length of the array.

The input nums can have negative numbers, zeros, or positive numbers, and the array size is small, up to 50 elements. The target can also be negative. The output is a single integer, representing the total number of pairs whose sum is less than the target.

Key observations from the constraints include that the small array length (n <= 50) allows approaches with time complexity up to O(n^2) to be feasible, but we can optimize further. Edge cases that could be tricky include arrays where all elements are negative or positive, and targets that are very small (e.g., negative) or very large. We also must ensure that the solution only counts pairs (i, j) where i < j and not duplicate or reversed pairs.

Approaches

The simplest approach is a brute-force method, where we iterate over all possible pairs (i, j) using nested loops and check if their sum is less than target. This approach guarantees correctness because it explicitly checks all possible pairs, but it has a quadratic time complexity of O(n^2). Given that n is at most 50, this is acceptable, but we can improve efficiency.

A more optimal approach leverages sorting and the two-pointer technique. By sorting the array in non-decreasing order, we can efficiently count the number of valid pairs. For each element nums[i], we can use a second pointer j starting from the end of the array and move it left until nums[i] + nums[j] < target. Because the array is sorted, all elements to the left of j with the same i will also form valid pairs. This reduces redundant comparisons and improves the efficiency of counting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Simple nested loops to check all pairs
Two Pointers (Optimal)	O(n log n)	O(1)	Sort array and use two-pointer method to count pairs efficiently

Algorithm Walkthrough

1. Sort the array nums in non-decreasing order. Sorting allows us to efficiently count pairs with a sum less than target using the two-pointer technique.
2. Initialize two pointers: left at the start of the array (0) and right at the end of the array (n-1).
3. Initialize a counter count to 0 to store the number of valid pairs.
4. While left < right, calculate the sum current_sum = nums[left] + nums[right].
5. If current_sum is less than target, then all pairs from left to right-1 are valid with the current left because the array is sorted. Increment count by right - left and move left one step to the right.
6. If current_sum is greater than or equal to target, move right one step to the left to decrease the sum.
7. Repeat steps 4-6 until left is no longer less than right.
8. Return the counter count.

Why it works: Sorting ensures that as we move right leftwards, sums decrease, and as we move left rightwards, sums increase. By counting all elements between left and right when the sum is valid, we efficiently include all valid pairs without checking them individually. This maintains correctness while reducing unnecessary checks.

Python Solution

from typing import List

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        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

This Python implementation first sorts the input array to facilitate the two-pointer counting. The while loop efficiently moves the left and right pointers according to the sum relative to target. When the sum is less than target, all elements between left and right are valid pairs, so we add right - left to the count and increment left. Otherwise, we decrement right to reduce the sum.

Go Solution

import "sort"

func countPairs(nums []int, target int) int {
    sort.Ints(nums)
    count := 0
    left, right := 0, len(nums)-1
    
    for left < right {
        if nums[left]+nums[right] < target {
            count += right - left
            left++
        } else {
            right--
        }
    }
    
    return count
}

The Go version is nearly identical to Python, with attention to Go-specific details like using sort.Ints for sorting and initializing variables in a Go-friendly way. The logic of the two-pointer approach remains the same.

Worked Examples

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

After sorting: nums = [-1,1,1,2,3]

left	right	nums[left]	nums[right]	sum	count
0	4	-1	3	2	0
0	3	-1	2	1	3
1	3	1	2	3	3
1	2	1	1	2	3

Final count: 3

Example 2: nums = [-6,2,5,-2,-7,-1,3], target = -2

After sorting: nums = [-7,-6,-2,-1,2,3,5]

left	right	nums[left]	nums[right]	sum	count
0	6	-7	5	-2	0
0	5	-7	3	-4	5
1	5	-6	3	-3	9
2	5	-2	3	1	9
2	4	-2	2	0	9
2	3	-2	-1	-3	10

Final count: 10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting takes O(n log n), and the two-pointer loop runs in O(n)
Space	O(1)	Only a few integer variables used, sorting can be in-place

The algorithm is efficient for the constraints, as n is at most 50. Sorting dominates the time complexity, while counting is linear.

Test Cases

# Provided examples
assert Solution().countPairs([-1,1,2,3,1], 2) == 3  # Example 1
assert Solution().countPairs([-6,2,5,-2,-7,-1,3], -2) == 10  # Example 2

# Edge cases
assert Solution().countPairs([1], 5) == 0  # Single element
assert Solution().countPairs([1,2,3,4,5], 10) == 10  # All pairs valid
assert Solution().countPairs([-5,-4,-3,-2,-1], -1) == 10  # All pairs negative sum
assert Solution().countPairs([0,0,0], 1) == 3  # All zeros
assert Solution().countPairs([50,50,50], 50) == 0  # All above target

Test	Why
Single element	No pairs exist, ensures function handles small arrays
All pairs valid	Tests counting all possible pairs
All negative numbers	Checks algorithm works with negative sums
All zeros	Edge case with zeros and small target
All above target	Ensures function returns 0 when no valid pairs

Edge Cases

First, arrays of length 1 or 0 are trivial, as there are no pairs. The algorithm correctly handles this because left < right condition fails immediately.

Second, arrays with all elements identical may produce multiple valid pairs if the sum is below the target. The algorithm counts these pairs correctly using the right - left logic.

Third, targets smaller than any possible pair sum, including negative targets with positive numbers, ensure that the algorithm correctly skips all pairs and returns 0