Skip to main content
Talentd

Count Pairs Whose Sum is Less than Target - Solution & Explanation

EasyArrayTwo PointersBinary SearchSorting15 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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

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.

This C code uses two nested loops to find all pairs (i, j) where nums[i] + nums[j] < target. The outer loop runs from 0 to n-1, and the inner loop runs from i+1 to n, where n is the length of the array. A counter keeps track of valid pairs.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) because we have two nested loops.
Space Complexity: O(1) because we only use a fixed amount of extra space.

Try this approach in the editor →

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.

This C solution uses qsort to sort the array first. Then, it maintains two pointers, starting from the leftmost and rightmost ends. If the sum of elements at the pointers is less than the target, all pairs between i and j satisfy the condition, and we move the left pointer up. Else, we move the right pointer down.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, followed by an O(n) two-pointer scan.
Space Complexity: O(1) since sorting is in-place.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2) because we have two nested loops.
Space Complexity: O(1) because we only use a fixed amount of extra space.

Two-Pointer Technique on Sorted Array

Time Complexity: O(n log n) due to sorting, followed by an O(n) two-pointer scan.
Space Complexity: O(1) since sorting is in-place.

Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n²)O(1)Small input sizes or when demonstrating baseline logic in interviews
Two-Pointer on Sorted ArrayO(n log n)O(1)Best general solution for unsorted arrays where pair counting is required

Video Solution

LeetCode 2824: Count Pairs Whose Sum is Less than Target • Engineering Digest • 7,271 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Pairs Whose Sum is Less than Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Fair Pairs

Next

Two Sum