Triplets with Smaller Sum
Medium · Two Pointers · Array · Two Pointers · Binary Search · Sorting
Problem
Given an array nums of integers and an integer target, count the index triplets i < j < k for which nums[i] + nums[j] + nums[k] < target.
Triplets are counted by position, so equal values at different indices form different triplets. Aim for O(n²) time.
Examples
Input: nums = [-2,0,1,3], target = 2 Output: 2
The triplets (-2, 0, 1) and (-2, 0, 3) sum to -1 and 1, both below 2. The others sum to 2 and 4.
Input: nums = [1,1,1,1], target = 4 Output: 4
Every one of the 4 index triplets sums to 3.
Input: nums = [5,6,7], target = 0 Output: 0
The only triplet sums to 18.
Constraints
- 0 <= len(nums) <= 3500
- -100 <= nums[i] <= 100
- -100 <= target <= 100
Approaches
- Baseline: check every triplet — time O(n³), space O(1)
Follow-up
The count can reach C(3500, 3), about 7 · 10^9, which does not fit in a 32-bit integer: use a 64-bit counter. Why is it safe to sort when the question is about indices i < j < k?
Related problems
Start free on Cariara · Coding problems · System design studio
