3sum Smaller - Leetcode Solution

Problem Statement:

Given an array of n integers nums and a 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.

Example:

Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2, 0, 1] [-2, 0, 3]

Solution:

First, we sort the input array 'nums'. Then, we iterate through the sorted array from left to right, consider each item 'x' as a potential candidate for the first element of a triplet, and find the number of pairs (i, j) in the remaining subarray nums[i+1,n-1] that satisfy the condition nums[i] + nums[j] < target - x, using a two-pointers technique.

The idea is simple: We have two pointers, left and right, initially pointing to the beginning and the end of the remaining subarray nums[i+1,n-1], respectively. As long as nums[i] + nums[left] + nums[right] >= target, we move the right pointer one step to the left. Otherwise, if nums[i] + nums[left] + nums[right] < target, we can safely count all pairs (left, right), (left + 1, right), ..., (right - 1, right) as valid triplets, and move the left pointer one step to the right.

The reason why we can count all these pairs is that the subarray nums[left+1,right-1] contains only items that are greater than or equal to nums[left], and less than or equal to nums[right], since the array is sorted. Therefore, if nums[i] + nums[left] + nums[right] < target, we can include all triplets that have nums[i], nums[left], and any item in the subarray nums[left+1,right-1], which are exactly (right - left) triplets.

Additional conditions for handling duplicates are added (similar to 3Sum problem):

• If the current item nums[i] is identical to the previous one, we skip it to avoid duplicates.
• If the sum nums[i] + nums[left] + nums[right] is still larger than or equal to the target after moving the right pointer, we should decrement the right pointer and continue to the next iteration, rather than break the loop. This is because the decrement can still reduce the sum below the target (if nums[i] + nums[left] + nums[right-1] < target), and breaking the loop would count incorrect triplets.

Here is the Python code for the solution:

class Solution: def threeSumSmaller(self, nums: List[int], target: int) -> int: N = len(nums) count = 0 nums.sort() for i in range(N - 2): if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, N - 1 while left < right: s = nums[i] + nums[left] + nums[right] if s >= target: right -= 1 else: count += right - left # all pairs are valid left += 1 return count

Time Complexity: O(n^2), where n is the length of the input array 'nums'. The outer loop runs O(n) times, and the inner while loop runs O(n) times in total (O(n) times for each iteration of the outer loop).

Space Complexity: O(1). We use only constant extra space for the pointers and the result variable.

1