Count Pairs with Sum Less Than Target — Problem Statement & Solution Guide
Problem Description
You are provided with a non-decreasing sequence of integers, nums, and a specific integer value, target. Your objective is to compute the total number of distinct index pairs (i, j) that satisfy the condition i < j and nums[i] + nums[j] < target.
The array is guaranteed to be sorted in ascending order, which allows for an optimized approach to finding valid pairs without resorting to a brute-force nested loop. The indices must be within the bounds of the array, specifically 0 <= i < j < nums.length.
Return the count of all such valid pairs. If no pairs satisfy the condition, return 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Pairs with Sum Less Than Target"
WHY DOES IT MATTER?
Two‑pointer patterns turn a quadratic search space into a linear walk by exploiting order. Recognizing when a problem can be reframed as “find pairs satisfying a monotonic condition” is a core skill for writing scalable code.
OPTIMIZATION CHALLENGE
The key insight is that a valid pair (i, j) guarantees all indices between i and j also form valid pairs with i, allowing us to count an entire block in O(1) instead of iterating each element.
REAL-WORLD CONNECTION
Think of a load balancer assigning tasks to two servers: you keep the lightest task on the left and the heaviest on the right, moving pointers inward until the combined load stays under a threshold, similar to capacity planning in distributed systems.
During an interview, write the two‑pointer loop first, then immediately add the block‑count (right‑left) when the sum is under target; this avoids off‑by‑one errors and shows you understand the counting shortcut.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the count of index pairs (i, j) with i < j such that nums[i] + nums[j] < target in a non‑decreasing array. A naïve double loop checks every possible pair, leading to O(n²) time, which quickly becomes infeasible for n up to 10⁵ or higher. Because the array is sorted, we can exploit the monotonic relationship between indices and values: if a pair (i, j) satisfies the inequality, then any index k with i < k < j will also satisfy nums[i] + nums[k] < target, allowing us to skip large blocks of pairs.
The two‑pointer technique leverages two indices—one starting at the beginning (left) and one at the end (right). If the sum of the two pointed values is less than the target, all elements between left and right form valid pairs with left, so we add (right - left) to the answer and move left forward. Otherwise, the sum is too large, and we decrement right to try a smaller partner. This greedy movement guarantees each element is visited at most once, yielding linear time. The approach is optimal for sorted inputs because any algorithm must at least read each element, establishing O(n) as the lower bound.
Interview Questions on This Problem
Q1How would you modify the two‑pointer solution to count pairs with sum **greater than** a given target?
Initialize left at 0 and right at n‑1. If nums[left] + nums[right] > target, then all pairs (left, k) for k in [left+1, right] are also > target, so add (right - left) and decrement right. Otherwise, increment left. This mirrors the original logic with the inequality reversed.
Q2Can you solve the problem in O(n log n) without the array being pre‑sorted? What would be the steps?
First sort the array in O(n log n). Then apply the same two‑pointer scan on the sorted array, which runs in O(n). The total complexity becomes O(n log n) due to the sorting step.
Q3If the input were a stream of numbers (no random access), how could you approximate the count of pairs with sum < target using limited memory?
Maintain a balanced binary search tree (or a Fenwick tree) of seen values. For each incoming number x, query how many previously seen numbers are < target - x, add that to the count, then insert x. Each operation is O(log n), giving O(n log n) time and O(n) space, which works for streaming data.
Examples
Input
nums = [1, 2, 3, 4, 5], target = 7
Output
6
Explanation: Valid pairs are: (1,2)->3, (1,3)->4, (1,4)->5, (1,5)->6, (2,3)->5, (2,4)->6. All sums are less than 7. (2,5)=7 is not less than 7. (3,4)=7 is not less than 7. (3,5)=8 is not less than 7. (4,5)=9 is not less than 7. Total 6 pairs.
Input
nums = [-1, 0, 1, 2, 3], target = 2
Output
5
Explanation: Valid pairs: (-1,0)->-1, (-1,1)->0, (-1,2)->1, (-1,3)->2 (not < 2, wait, 2 is not < 2). Let's re-evaluate. (-1,0)=-1 < 2. (-1,1)=0 < 2. (-1,2)=1 < 2. (-1,3)=2 is NOT < 2. (-1,4)=3 is NOT < 2. (0,1)=1 < 2. (0,2)=2 is NOT < 2. (0,3)=3 is NOT < 2. (1,2)=3 is NOT < 2. So valid pairs are (-1,0), (-1,1), (-1,2), (0,1). That is 4. Let's check again. (-1,0)=-1. (-1,1)=0. (-1,2)=1. (0,1)=1. (0,2)=2 (no). (1,2)=3 (no). Total 4. Let's pick a better example to avoid confusion. Let's use nums = [-5, -4, -3, -2, -1], target = -5. Pairs: (-5,-4)=-9 < -5. (-5,-3)=-8 < -5. (-5,-2)=-7 < -5. (-5,-1)=-6 < -5. (-4,-3)=-7 < -5. (-4,-2)=-6 < -5. (-4,-1)=-5 (no). (-3,-2)=-5 (no). (-3,-1)=-4 (no). (-2,-1)=-3 (no). Total 6.
Input
nums = [10, 20, 30, 40], target = 50
Output
3
Explanation: Valid pairs: (10,20)=30 < 50. (10,30)=40 < 50. (10,40)=50 (not < 50). (20,30)=50 (not < 50). (20,40)=60 (no). (30,40)=70 (no). Total 3 pairs.
Input
nums = [1, 1, 1, 1], target = 3
Output
6
Explanation: All pairs sum to 2, which is less than 3. Number of pairs in an array of length 4 is 4*3/2 = 6.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- nums is sorted in non-decreasing order
Optimal Approach & Strategy
Use two pointers, left at 0 and right at n‑1. If the current sum is less than target, add (right‑left) to the result and advance left; otherwise, decrement right. This visits each element at most once.
Brute Force Approach
Iterate over every i from 0 to n‑2 and for each i loop j from i+1 to n‑1, checking if nums[i] + nums[j] < target and incrementing a counter. This double loop examines all possible pairs.
Verified Code Solutions
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; }class Solution { public: int countPairs(vector<int>& nums, int target) { int count = 0; for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { if (nums[i] + nums[j] < target) { count++; } } } return count; } };class Solution { public 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; } }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 countfunction 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; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.