Skip to main content
Talentd

3Sum Smaller - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersBinary SearchSorting12 min readAsked at: Microsoft, Meta, Oracle +4
Practice this problem

Problem Statement

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.length
  • 0 <= n <= 3500
  • -100 <= nums[i] <= 100
  • -100 <= target <= 100
  • The input is generated such that the answer is less than or equal to 109.

Approach Overview

Problem 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.

Solution

Since the order of elements does not affect the result, we can sort the array first and then use the two-pointer method to solve this problem.

First, we sort the array and then enumerate the first element nums[i]. Within the range nums[i+1:n-1], we use two pointers pointing to nums[j] and nums[k], where j is the next element of nums[i] and k is the last element of the array.

  • If nums[i] + nums[j] + nums[k] < target, then for any element j \lt k' leq k, we have nums[i] + nums[j] + nums[k'] < target. There are k - j such k', and we add k - j to the answer. Next, move j one position to the right and continue to find the next k that meets the condition until j geq k.
  • If nums[i] + nums[j] + nums[k] geq target, then for any element j leq j' \lt k, it is impossible to make nums[i] + nums[j'] + nums[k] < target. Therefore, we move k one position to the left and continue to find the next k that meets the condition until j geq k.

After enumerating all i, we get the number of triplets that meet the condition.

The time complexity is O(n^2), and the space complexity is O(log n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triple LoopO(n^3)O(1)Small arrays or when demonstrating the straightforward interpretation of the problem
Sorting + Two Pointers + EnumerationO(n^2)O(1)Optimal interview solution; works well after sorting when counting multiple valid pairs efficiently
Sorting + Enumeration + Binary SearchO(n^2 log n)O(1)When binary search is preferred for locating the maximum valid third element

Video Solution

LeetCode 259 | 3Sum Smaller | Solution Explained (Java + Whiteboard) • Xavier Elon • 4,148 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is 3Sum Smaller easy or hard?
3Sum Smaller is generally considered a medium difficulty problem. The brute force idea is simple, but recognizing that sorting allows counting multiple valid pairs with two pointers is the key insight that reduces the complexity to O(n^2).
3Sum Smaller Python/Java solution
The typical implementation sorts the array and then iterates with an index i while using left and right pointers for the remaining elements. When the sum is less than the target, add right - left to the count and move the left pointer. The same logic works across Python, Java, C++, Go, TypeScript, and JavaScript.
How to solve 3Sum Smaller in O(n)?
Solving 3Sum Smaller in strict O(n) time is not possible for the general case because the algorithm must consider combinations of three elements. The best known practical solution is O(n^2) using sorting and the two pointers technique. This approach efficiently counts multiple valid triplets in a single step.
What is the best approach for 3Sum Smaller?
The most efficient approach sorts the array and then uses a two pointers technique. Fix the first element and move two pointers across the remaining subarray to count valid pairs. Because the array is sorted, when a sum is smaller than the target you can add multiple pairs at once. This reduces the complexity to O(n^2) time with O(1) extra space.
Is 3Sum Smaller asked at Google/Amazon/Meta?
3Sum-style problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test sorting, two pointers, and combination counting. Variants include 3Sum, 3Sum Closest, and 3Sum Smaller. Interviewers expect candidates to move from brute force to an O(n^2) optimized solution.
What data structure is used in 3Sum Smaller?
The problem mainly relies on arrays combined with sorting and the two pointers technique. No complex data structures are required. The algorithm uses pointer movement over a sorted array to efficiently count valid triplets.
What is the time complexity of 3Sum Smaller?
The optimal solution runs in O(n^2) time after sorting the array. Sorting takes O(n log n), but the dominant cost is the quadratic two-pointer traversal for each first element. Space complexity is O(1) if sorting is done in place.

Ready to solve this problem?

Practice 3Sum Smaller with our built-in code editor and test cases.

Practice on FleetCode
Previous

3Sum

Next

3Sum Closest