3Sum Smaller

LeetCode 259: 3Sum Smaller Solution & Explanation

Problem Overview

TL;DR: Sort the input array, iterate through the first element, and use the converging two-pointer technique to count all valid pairs for the remaining two elements in $O(N^2)$ time.

The problem asks us to calculate the number of index triplets $(i, j, k)$ such that $0 \le i < j < k < n$ and the sum of the elements at these indices is strictly less than a given target value. Unlike the classic 3Sum problem which asks for unique triplets of values, LeetCode 259 requires us to count index triplets, meaning duplicate values in the array are treated as distinct elements. This is a popular interview question that tests your ability to optimize combinatorial search problems using sorting and pointers.

Brute Force Approach for 3Sum Smaller

The most straightforward method to solve the 3Sum Smaller problem is to iterate through every possible triplet of indices $(i, j, k)$ and check if their sum satisfies the condition.

We can use three nested loops to generate all combinations where $i < j < k$.

1# Pseudo-code for Brute Force
2count = 0
3for i from 0 to n - 3:
4    for j from i + 1 to n - 2:
5        for k from j + 1 to n - 1:
6            if nums[i] + nums[j] + nums[k] < target:
7                count = count + 1
8return count

Complexity Analysis: The time complexity of this approach is $O(N^3)$ because of the three nested loops. If $N$ is 2000, $N^3$ is $8 \times 10^9$, which will result in a Time Limit Exceeded (TLE) error on most coding platforms. This approach fails because it performs redundant checks and does not utilize the properties of the data to prune the search space.

Algorithm Strategy: Two Pointer Patterns

1. Sort: First, sort the array nums in ascending order. This is a prerequisite for the two-pointer logic.
2. Iterate: Loop through the array with index i from 0 to n-2. This i represents the first element of the triplet.
3. Initialize Pointers: For each i, initialize two pointers:
   • left = i + 1
   • right = n - 1
4. Converge: While left < right:
   • Calculate current_sum = nums[i] + nums[left] + nums[right].
   • Case 1 (current_sum < target): We found a valid window. All elements from left + 1 to right can pair with left to satisfy the condition.
     • Add right - left to the total count.
     • Increment left to explore larger values.
   • Case 2 (current_sum >= target): The sum is too large. We need a smaller sum.
     • Decrement right to reduce the sum.
5. Return: After the outer loop finishes, return the total count.

Execution Flow

Let's trace nums = [-2, 0, 1, 3], target = 2.

1. Sort: [-2, 0, 1, 3] (Already sorted).
2. Outer Loop i = 0 (nums[i] = -2):
   • Set left = 1 (nums[1] = 0), right = 3 (nums[3] = 3).
   • Sum: -2 + 0 + 3 = 1.
   • Check: 1 < 2 is True.
   • Action: Since the sum is small enough, the pair (0, 3) works. Additionally, any element between left and right combined with left would be even smaller.
   • Count: Add right - left = 3 - 1 = 2. (Triplets are indices: (0,1,3) and (0,1,2)).
   • Move: left becomes 2.
   • New State: left = 2, right = 3.
   • Sum: -2 + 1 + 3 = 2.
   • Check: 2 < 2 is False.
   • Action: Sum is too high (or equal).
   • Move: right becomes 2.
   • Loop condition left < right (2 < 2) is False. Break inner loop.
3. Outer Loop i = 1 (nums[i] = 0):
   • Set left = 2, right = 3.
   • Sum: 0 + 1 + 3 = 4.
   • Check: 4 < 2 is False.
   • Move: right becomes 2.
   • Loop condition 2 < 2 is False. Break.
4. End: Return total count 2.

Proof of Correctness

The correctness relies on the sorted property of the array.

• Completeness: By fixing i and scanning the remaining array with left and right, we consider all valid positions for the second and third elements.
• Counting Logic: When nums[i] + nums[left] + nums[right] < target, the inequality holds for all k where left < k <= right because nums[k] <= nums[right]. Therefore, nums[i] + nums[left] + nums[k] <= nums[i] + nums[left] + nums[right] < target. Adding right - left correctly counts exactly these k values without individual checks.
• Pointer Movement:
  • If sum < target, increasing left allows us to test if a larger second number can still form a valid sum.
  • If sum >= target, decreasing right is the only way to reduce the sum, as decreasing left is impossible (we move forward) and increasing left would only increase the sum.

Pattern Reuse Notes

The Two Pointers - Converging pattern used in LeetCode 259 is fundamental for several array problems:

• LeetCode 11: Container With Most Water: Uses converging pointers to maximize area, moving the pointer pointing to the shorter line.
• LeetCode 15: 3Sum: Finds triplets summing to zero. Uses the same sorting + two-pointer logic but requires skipping duplicates.
• LeetCode 16: 3Sum Closest: Finds a triplet sum closest to a target. Uses the exact same traversal but tracks the minimum difference instead of counting.
• LeetCode 18: 4Sum: Extends the 3Sum logic by adding one more nested loop, reducing $O(N^4)$ to $O(N^3)$.

Understanding the invariant in 3Sum Smaller—that satisfying the condition at the boundaries implies satisfaction for the whole range—is key to mastering this subpattern.

Reference Implementation

C++ Solution for LeetCode 259

1class Solution {
2public:
3    int threeSumSmaller(vector<int>& nums, int target) {
4        sort(nums.begin(), nums.end());
5        int count = 0;
6        int n = nums.size();
7        
8        for (int i = 0; i < n - 2; ++i) {
9            int left = i + 1;
10            int right = n - 1;
11            
12            while (left < right) {
13                // Check sum of current triplet
14                if (nums[i] + nums[left] + nums[right] < target) {
15                    // If (i, left, right) is valid, then all pairs
16                    // (i, left, left+1) ... (i, left, right) are valid.
17                    count += (right - left);
18                    left++;
19                } else {
20                    // Sum is too large, decrease the largest element
21                    right--;
22                }
23            }
24        }
25        
26        return count;
27    }
28};

Java Solution for LeetCode 259

1class Solution {
2    public int threeSumSmaller(int[] nums, int target) {
3        Arrays.sort(nums);
4        int count = 0;
5        int n = nums.length;
6        
7        for (int i = 0; i < n - 2; i++) {
8            int left = i + 1;
9            int right = n - 1;
10            
11            while (left < right) {
12                int sum = nums[i] + nums[left] + nums[right];
13                
14                if (sum < target) {
15                    // All indices between left and right satisfy the condition
16                    // when paired with nums[i] and nums[left]
17                    count += (right - left);
18                    left++;
19                } else {
20                    // Sum is too large, try smaller number
21                    right--;
22                }
23            }
24        }
25        
26        return count;
27    }
28}

Python Solution for LeetCode 259

1class Solution:
2    def threeSumSmaller(self, nums: List[int], target: int) -> int:
3        nums.sort()
4        count = 0
5        n = len(nums)
6        
7        for i in range(n - 2):
8            left = i + 1
9            right = n - 1
10            
11            while left < right:
12                current_sum = nums[i] + nums[left] + nums[right]
13                
14                if current_sum < target:
15                    # If the sum is smaller than target, then nums[i] + nums[left]
16                    # plus ANY element from index left+1 to right is also smaller.
17                    count += (right - left)
18                    left += 1
19                else:
20                    # Sum is too large, move right pointer to reduce sum
21                    right -= 1
22                    
23        return count