3Sum Smaller

medium array two pointers sorting

Problem

Given an array of n integers nums and a target, find the number of index triplets i<j<k with nums[i] + nums[j] + nums[k] < target.

Inputnums = [-2,0,1,3], target = 2

Output2

Triplets (-2,0,1) and (-2,0,3) both sum to less than 2.

nums (comma-separated)

target

def three_sum_smaller(nums, target):
    nums.sort()
    n = len(nums)
    count = 0
    for i in range(n - 2):
        j, k = i + 1, n - 1
        while j < k:
            if nums[i] + nums[j] + nums[k] < target:
                count += k - j
                j += 1
            else:
                k -= 1
    return count

function threeSumSmaller(nums, target) {
  nums.sort((a, b) => a - b);
  let count = 0;
  for (let i = 0; i < nums.length - 2; i++) {
    let j = i + 1, k = nums.length - 1;
    while (j < k) {
      if (nums[i] + nums[j] + nums[k] < target) {
        count += k - j;
        j++;
      } else {
        k--;
      }
    }
  }
  return count;
}

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] < target) {
                    count += k - j; j++;
                } else k--;
            }
        }
        return count;
    }
}

int threeSumSmaller(vector& nums, int target) {
    sort(nums.begin(), nums.end());
    int count = 0;
    for (int i = 0; i + 2 < (int)nums.size(); i++) {
        int j = i + 1, k = (int)nums.size() - 1;
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] < target) { count += k - j; j++; }
            else k--;
        }
    }
    return count;
}

Explanation

We count triplets whose sum is strictly less than the target. The big speed-up comes from sorting first and then counting many triplets at once instead of one at a time.

Fix the smallest index i, then sweep with a left pointer j and a right pointer k. Look at nums[i] + nums[j] + nums[k].

Here is the trick: if that sum is already below the target, then every k' between j+1 and k also works, because the array is sorted and those values are even smaller. So we add k - j in one shot and move j right. If the sum is too big, we shrink by moving k left.

Example: sorted [-2, 0, 1, 3], target 2. With i on -2, j on 0, k on 3: sum is 1 < 2, so all pointers from j+1 up to k count — that is k - j = 2 triplets at once.

Counting a whole range per step is what turns a cubic brute force into an n-squared solution.

Time: O(n^2) Space: O(1)