Watch 10 video solutions for 3Sum Smaller, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by Xavier Elon has 4,082 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
Example 1:
Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3]
Example 2:
Input: nums = [], target = 0 Output: 0
Example 3:
Input: nums = [0], target = 0 Output: 0
Constraints:
n == nums.length0 <= n <= 3500-100 <= nums[i] <= 100-100 <= target <= 100Problem Overview: Given an integer array nums and a target value, count how many index triplets (i, j, k) satisfy i < j < k and nums[i] + nums[j] + nums[k] < target. The goal is not to return the triplets, only the total count.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Check every possible triplet using three nested loops. For each combination (i, j, k), compute the sum and increment the counter if the sum is smaller than the target. This approach directly follows the problem definition and guarantees correctness. However, it performs O(n^3) comparisons, which becomes slow for larger arrays. It is useful as a baseline solution and helps verify correctness before optimizing.
Approach 2: Sorting + Two Pointers + Enumeration (O(n^2) time, O(1) space)
First sort the array using a standard algorithm from sorting. Then enumerate the first element of the triplet with index i. For the remaining part of the array, apply the classic two pointers technique: place left at i + 1 and right at the end of the array. If nums[i] + nums[left] + nums[right] < target, every index between left and right forms a valid triplet with i, because the array is sorted. That means you can add right - left to the count in one step, then move left forward. If the sum is too large, move right backward to reduce it.
The key insight is that sorting creates a monotonic structure. When the current sum is smaller than the target, all elements between the pointers also satisfy the constraint. This eliminates the need to check each pair individually and reduces the complexity from cubic to quadratic.
This technique combines ideas from array traversal and pointer-based window shrinking. Some variations also use binary search to locate the largest valid third element, but the two-pointer sweep is typically faster in practice due to linear scanning.
Recommended for interviews: Interviewers expect the sorting + two pointers solution with O(n^2) time. Showing the brute force method first demonstrates understanding of the problem, but recognizing that sorting enables counting multiple pairs at once shows strong algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triple Loop | O(n^3) | O(1) | Small arrays or when demonstrating the straightforward interpretation of the problem |
| Sorting + Two Pointers + Enumeration | O(n^2) | O(1) | Optimal interview solution; works well after sorting when counting multiple valid pairs efficiently |
| Sorting + Enumeration + Binary Search | O(n^2 log n) | O(1) | When binary search is preferred for locating the maximum valid third element |