We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

3Sum Smaller

Number: 259

Difficulty: Medium

Paid? Yes

Companies: PayPal, TikTok, Google

Problem Description

Given an array of integers and a target value, count the number of triplets (i, j, k) with 0 <= i < j < k < n such that the sum of the three numbers is less than the target.

Key Insights

  • Sort the array to leverage the inherent order.
  • Use a two pointers approach for each fixed element to efficiently count valid pairs.
  • When a valid pair is found, all elements between the left and right pointers yield valid triplets.
  • Avoid redundant calculations by adjusting pointers based on the sum comparison with the target.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1) (or O(log n) if considering the sorting stack space)

Solution

Sort the array first. Then, iterate through the array using an index i, and for each i, use two pointers (left and right) to check pairs (j, k) such that the sum of nums[i] + nums[left] + nums[right] is less than the target. When the condition is met, all elements between left and right will also form valid triplets with the current i, so add (right - left) to the count and move the left pointer. If the sum is equal to or exceeds the target, move the right pointer leftwards to reduce the sum. This approach leverages the sorted order to count multiple valid pairs at once, resulting in an O(n^2) time complexity.

Code Solutions

def threeSumSmaller(nums, target):
    # Sort the array in ascending order
    nums.sort()
    count = 0
    n = len(nums)
    # Loop through each element up to the third-last element
    for i in range(n - 2):
        left, right = i + 1, n - 1
        # Use two pointers to find pairs such that the sum is less than target
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum < target:
                # All elements between left and right create valid triplets with nums[i]
                count += (right - left)
                left += 1
            else:
                right -= 1
    return count

# Example usage:
print(threeSumSmaller([-2, 0, 1, 3], 2))  # Output: 2
← Back to All Questions