Problem Description

Given an array of integers nums and an integer target, return the number of index triplets (i, j, k) such that i < j < k and nums[i] + nums[j] + nums[k] < target.

• You must count all unique triplets where the indices are strictly increasing.
• Each element in nums can be used at most once per triplet (no reusing elements in a triplet).
• The array may contain negative, zero, or positive numbers.

Constraints:

• 3 <= nums.length <= 1000
• -100 <= nums[i] <= 100
• -100 <= target <= 100

Thought Process

The most direct way to solve this problem is to check every possible triplet in nums and count those whose sum is less than target. This is a brute-force approach and involves three nested loops, which is inefficient for large arrays.

To optimize, we can think about how to avoid unnecessary checks. Since the order of indices matters (i < j < k), but the order of values does not, sorting the array might help us quickly skip impossible combinations. If we fix the first two elements, we can use a two-pointer technique to efficiently count all valid third elements. This leverages the sorted order to avoid redundant work, similar to the classic "3Sum" problem, but instead of finding sums equal to a target, we count those less than a target.

Solution Approach

We use a two-pointer approach after sorting the array:

1. Sort the array nums in ascending order.
   • This allows us to make assumptions about the relative sizes of potential triplet sums.
2. Iterate through the array with index i (the first element of the triplet).
   • For each i, use two pointers: left (starting at i + 1) and right (starting at the end of the array) to find valid triplets.
3. While left < right:
   • Compute current_sum = nums[i] + nums[left] + nums[right].
   • If current_sum < target, then all triplets between left and right (inclusive) with the current i and left will also be valid, because increasing left will only increase the sum (since the array is sorted).
   • Add right - left to the count, and move left one step right to look for more possibilities.
   • If current_sum >= target, decrement right to try a smaller sum.
4. Continue until all possible i have been checked.

This approach avoids redundant checks and leverages the sorted property of the array for efficient counting.

Example Walkthrough

Suppose nums = [-2, 0, 1, 3] and target = 2.

1. Sort nums: [-2, 0, 1, 3] (already sorted).
2. For i = 0 (nums[0] = -2):
   • left = 1 (nums[1] = 0), right = 3 (nums[3] = 3)
   • sum = -2 + 0 + 3 = 1 which is less than 2.
     • All triplets with left = 1 and right = 3 will be valid, which is right - left = 2 triplets: (-2, 0, 1) and (-2, 0, 3).
     • Increment left to 2.
   • Now left = 2 (nums[2] = 1), right = 3.
     • sum = -2 + 1 + 3 = 2 which is NOT less than 2, so decrement right to 2.
   • Now left == right, so move to next i.
3. For i = 1 (nums[1] = 0):
   • left = 2 (nums[2] = 1), right = 3 (nums[3] = 3)
   • sum = 0 + 1 + 3 = 4 which is NOT less than 2, so decrement right to 2.
   • Now left == right, so done.
4. For i = 2, not enough elements after to form a triplet, so stop.
5. Total valid triplets: 2

Time and Space Complexity

• Brute-force approach:
  • Three nested loops over n elements: O(n³).
  • Space complexity: O(1) (ignoring input storage).
• Optimized two-pointer approach:
  • Sorting: O(n log n).
  • Outer loop over i: O(n).
  • Inner two-pointer scan: O(n) per i (in total, O(n²)).
  • Overall time complexity: O(n²).
  • Space complexity: O(1) extra (if sorting in-place), O(n) if not.

The optimized approach is much faster and suitable for the given constraints.

Summary

The "3Sum Smaller" problem asks us to count the number of triplets whose sum is less than a given target, with strictly increasing indices. While the brute-force solution is simple but slow, sorting the array and using a two-pointer technique allows us to efficiently find and count all valid triplets. This approach leverages the properties of sorted arrays to avoid redundant checks, making the solution both elegant and performant.

Code Implementation

class Solution:
    def threeSumSmaller(self, nums, target):
        nums.sort()
        count = 0
        n = len(nums)
        for i in range(n-2):
            left, right = i+1, n-1
            while left < right:
                curr_sum = nums[i] + nums[left] + nums[right]
                if curr_sum < target:
                    count += right - left
                    left += 1
                else:
                    right -= 1
        return count
      

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int count = 0, n = nums.size();
        for (int i = 0; i < n - 2; ++i) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int curr_sum = nums[i] + nums[left] + nums[right];
                if (curr_sum < target) {
                    count += right - left;
                    ++left;
                } else {
                    --right;
                }
            }
        }
        return count;
    }
};
      

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

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