Solving the Classic "3Sum" Array Coding Interview Question

The "3Sum" problem is a classic interview question that asks you to find all unique triplets in an array that add up to 0.

It's a popular problem that companies like Amazon, Facebook, Microsoft, Oracle, etc often ask in their interviews to test your problem-solving skills and ability to work with arrays.

Problem Statement:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

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

Output: [[-1,-1,2],[-1,0,1]]

Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• 105 <= nums[i] <= 105

Solution:

To solve this problem, you can use a two-pointer technique after sorting the array. Here's the approach:

1. Sort the array.
2. Iterate through the array with a loop, using the current element as the first element of the triplet.
3. For each element, set two pointers: one at the next element and the other at the end of the array.
4. Move the pointers towards each other until they meet, looking for pairs that sum up to the negative of the current element.
5. Skip over duplicate elements to avoid duplicate triplets.
6. Add valid triplets to the result list.

Here's a Python code snippet implementing this approach:

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
    return result

# Example usage:
print(threeSum([-1, 0, 1, 2, -1, -4]))  # Output: [[-1, -1, 2], [-1, 0, 1]]

Time Complexity: O(n^2), where n is the number of elements in the array.

The array is sorted once (O(n log n)), and then we have a loop and a two-pointer scan (O(n^2)).

Space Complexity: O(1) or O(n), depending on the sorting algorithm used. If the sorting does not use extra space, the space complexity is O(1).

Otherwise, it's O(n) for the space used to sort.

****

If you found this "3Sum" solution insightful and want to take your preparation to the next level, feel free to reach out to me.

I'd be happy to discuss more coding challenges like this and share my experience tackling various interview problems.

More technical interview questions and their solutions:

SQL Interview Question: Retrieving Top Customers by Total Spend

Walmart DS Interview: Acing Expected Value & Probability Problem