Leetcode: Sum Series — Three Sum

Image Credits

The Three sum problem series is an extension of Two Sum problem as constructed in this a previous article. Intuition to solving these problems will heavily borrow on the lessons learnt under patterns and conclusions of the mentioned article.

Three Sum

Problem Statement: Given an array and a value, return a triplet whose sum is equal to the given target otherwise return []

Example
Input: nums = [12, 3, 4, 1, 6, 9], target = 24
Output: [12, 3, 9]
Explanation: 12 + 3 + 9 = 24

Intuition

• Brute force — loop the array three times to check for possible candidates equal to the target.
• In every iteration — employ two sum solution of finding a number with it’s complement that add to the remainder off the iterated number.
• Sort it — remove the need to have a hashset to record previous seen compliments

Solution 1: Brute force — loop the array three times

def find_triplets(nums: list[int], target: int) -> List[int]:
    n = len(nums)

    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + array[k] == target:
                    return [nums[i], nums[j], nums[k]]

    return []

Review *

• The time complexity — O(N³), space complexity — O(1). For each element, it loops the array three times to find a triplet that add upto the target😡.

Solution 2: Employ two sum solution of finding a number with it’s complement that add to the remainder off the iterated number.

def find_triplets(nums: list[int], target: int) -> List[int]:
    n = len(nums)
    for i in range(n):
        seen = set()
        rem_target = target - nums[i]
        
        # Two sum problem 
        for j in range(i + 1, n):
            complement = rem_target - nums[j]
            if complement in seen:
                return [nums[i], nums[j], complement] 
            else:
                seen.add(nums[j])

      return []

Review *

• The time complexity — O(N²), space complexity — O(N). For each element iteration, it searches for two numbers in the rest of the elements that adds upto the remainder target 🤔(much better!)
• However, it uses a hashset to keep a memory of potential complements for later comparisons leading to a space complexity of O(N)😵‍💫.

Solution 2: Sort the input— remove the need to have a hashset to record previous seen compliments

def find_triplets(nums: list[int], target: int) -> List[int]:
    n = len(nums)
    array.sort()

    for i in range(n):
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum == target:
                return [nums[i], nums[left], nums[right]]
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return []

Review *

• The time complexity — O(N²), space complexity — O(1). While sorting the input is nlogn , it doesn’t hurt the overall time complexity of O(N²) 👌.

Three Sum Zero

Problem Statement: Are there elements a, b, c in nums such that a + b + c = 0?. Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Intuition

• Brute force — loop the array three times to check for possible candidates equal to zero.
• In every iteration — employ two sum solution of finding a number with it’s complement that add to the remainder off the iterated number.
• Sort it — remove the need to have a hashset to record previous seen compliments

Since we know how to implement the above intuitions as illustrated in the solution of Three Sum, we will only show the optimized solution.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = set()

        for i, num in enumerate(nums):
            remaining_target = 0 - num
            left, right = i + 1, len(nums) - 1

            while left < right:
                current_sum = nums[left] + nums[right]
                if current_sum == remaining_target:
                    # a hashset can only have immutable keys 
                    # hence adding tuple not list
                    result.add((num, nums[left], nums[right]))
                    left, right = left + 1, right - 1
                elif current_sum < remaining_target:
                    left += 1
                else:
                    right -= 1

         return [list(triplet) for triplet in result]

Review *

• The time complexity — O(N²), space complexity — O(N). The result set can contain upto N//3 combinations hence leading to the overall space complexity to be linear.
• Takeaway — a hashset can only have immutable keys hence adding tuple, since list is mutable(unhashable).

Three Sum Smaller

Problem Statement: 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.

Example
Input: nums = [-2, 0, 1, 3], target = 2
Output: 2
Explanation: There're two triplets with sums < 2: [-2, 0, 1], [-2, 0, 3]

Intuition

• Customise the previous used patterns to calculate all possible combinations when the inside remainder sum is less than the target as shown in the image below;

def threeSumSmaller(nums: list[int], target: int) -> int:
    nums.sort()
    ans, N = 0, len(nums)

    for i in range(N):
        left, right = i + 1, N - 1
        rem_target = target - nums[i] 

        while left < right:
            curr_sum = nums[left] + nums[right]
            if curr_sum < rem_target:
                ans += right - left
                left += 1
            else:
                right -= 1
    return ans

Review *

• The time complexity — O(N²), space complexity — O(1). The explanation says it all 🤓.

Three Sum Closest

Problem Statement: Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example
Input: nums = [-1, 2, 1, -4], target =1
Output: 2
Explanation: The sum closest to the target is 2. (-1 + 2 + 1 = 2)

Intuition

• Customise the previous used patterns keep track of the closest sum, bearing in mind that the closest can be to the left(<-) or right(->) of the number line.

def threeSumClosest(nums: list[int], target: int) -> int:
    nums.sort()
    N, closest = len(nums), float('inf')

    for i in range(N):
        left, right = i + 1, N - 1

        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]

            if abs(curr_sum - target) < abs(closest - target):
                closest = curr_sum
            elif curr_sum < target:
                left += 1
            else:
                right -= 1

    return closest

Review *

• The time complexity — O(N²), space complexity — O(1).
• Takeaway — closest can be of negative or positive diff hence using abs to compare which is closer to the target.

Conclusion

1. All the three sum problems have commonalities with a few fine-tuning to solve particular use cases. It is only prudent to dissect the Two Sum Problems to clearly see the patterns extending to these solutions.

Note: The article cover image has not correlation to the problem and solutions provided.

References

1. Three Sum Zero: Leetcode Link
2. Three Sum Closet: Leetcode Link
3. Three Sum Smaller: Leetcode Link
4. Two Sum Less Than K: Leetcode Link

Series

1. Prev << Leetcode: Sum Series — Two Sum
2. Next >> Leetcode: Sum Series — Four Sum