3Sum Smaller

Find Index Triplets

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.

Constraints:
n == nums.length
0 ≤ n ≤ 3500
-100 ≤ nums[i] ≤ 100
-100 ≤ target ≤ 100

Approach: Binary Search

Before we solve the threeSum problem, solve this simpler twoSum version:

Given a nums array, find the number of index pairs i, j with 0 ≤ i < j < n that satisfy the condition nums[i] + nums[j] < target.

If we sort the array first, we can apply binary search to find the largest index j such that nums[i] + nums[j] < target for each i. Once we find the largest index j, we know there must be j - i pairs that satisfy the condition with i's value fixed. Finally, we can apply the twoSum solution to threeSum directly by wrapping an outer for-loop around it.

class Solution {
      public int threeSumSmaller(int[] nums, int target) {
         Arrays.sort(nums);
         int sum = 0;

         for (int i = 0; i < nums.length - 2; i++) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i]);
         }
         return sum;
      }

      private int twoSumSmaller(int[] nums, int startIndex, int target) {
         int sum = 0;
         for (int i = startIndex; i < nums.length - 1; i++) {
            int j = binarySearch(nums, i, target - nums[i]);
            sum += j - i;
         }
         return sum;   
      }

      private int binarySearch(int[] nums, int startIndex, int target) {
         int left = startIndex;
         int right = nums.length - 1;
         while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] < target) {
                  left = mid;
            } else {
                  right = mid - 1;
            }
         }
         return left;
      }
}    
              

Complexity Analysis

Time Complexity: O(n² log n). The binarySearch function takes O(log n) time, so the twoSumSmaller function takes O(n log n) time. The threeSumSmaller function wraps with another for-loop, resulting in O(n² log n) time complexity.

Space Complexity: O(1). No additional data structures are used.