How to Solve: Three Sum (Complete Guide for FAANG Interviews)

How to Solve: Three Sum (Complete Guide for FAANG Interviews)

? Introduction

"This single problem tests sorting, two-pointer technique, and edge-case handling—master it, and you prove you can optimize brute-force solutions into linear time, a skill that separates L4 from L5 engineers at FAANG."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Three Sum, ensure you understand: 1. Sorting & Two-Pointer Technique – How to traverse a sorted array from both ends to find pairs efficiently. 2. Hash Sets for Lookup – How to use sets to track seen values (though not always optimal for Three Sum). 3. Time Complexity Analysis – Why brute-force is O(n³) and how to reduce it to O(n²).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps every time you see a Three Sum problem:

1. Sort the Array
2. Sorting enables two-pointer traversal and duplicate skipping.

3. Time: O(n log n), Space: O(1) (or O(n) if sorting is not in-place).

4. Iterate with a Fixed Pointer (i)

5. Loop from i = 0 to n-3 (since we need at least 3 elements).

6. For each i, treat nums[i] as the first element of the triplet.

7. Skip Duplicates for i

8. If nums[i] == nums[i-1], skip to avoid duplicate triplets.

9. Example: [-1, -1, 0, 1] → Skip the second -1.

10. Two-Pointer Search (left, right)

11. Initialize left = i + 1, right = n - 1.

12. While left < right:

    • Calculate current_sum = nums[i] + nums[left] + nums[right].
    • If current_sum == 0, add triplet to result.
    • If current_sum < 0, move left++ (need a larger sum).
    • If current_sum > 0, move right-- (need a smaller sum).

13. Skip Duplicates for left/right

14. After finding a valid triplet, skip duplicates for left and right.

15. Example: [-2, 0, 0, 2, 2] → Skip the second 0 and 2.

16. Early Termination (Optional)

17. If nums[i] > 0, break (since array is sorted, no possible triplet).

18. Return Result

19. Return the list of unique triplets.

? WORKED EXAMPLES

Example 1 – Basic: Three Sum (LeetCode 15)

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

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

Step-by-Step Solution

1. Sort the array:
   [-4, -1, -1, 0, 1, 2]

2. Iterate with fixed i:

3. i = 0 (nums[i] = -4):
   • left = 1, right = 5
   • current_sum = -4 + (-1) + 2 = -3 → Too small → left++
   • current_sum = -4 + 0 + 2 = -2 → Too small → left++
   • current_sum = -4 + 1 + 2 = -1 → Too small → left++ (now left == right → break)
4. i = 1 (nums[i] = -1):
   • left = 2, right = 5
   • current_sum = -1 + (-1) + 2 = 0 → Valid triplet → Add [-1, -1, 2]
   • Skip duplicates: nums[left] == nums[left+1] → left = 3
   • current_sum = -1 + 0 + 1 = 0 → Valid triplet → Add [-1, 0, 1]
   • Skip duplicates: nums[right] == nums[right-1] → right = 3 → break
5. i = 2 (nums[i] = -1):
   • Skip duplicate (same as i=1).

6. i = 3 (nums[i] = 0):

   • nums[i] > 0 → Early termination.

7. Result: [[-1, -1, 2], [-1, 0, 1]]

Python Code

def threeSum(nums):

    nums.sort()

    res = []

    n = len(nums)


    for i in range(n - 2):

        if i > 0 and nums[i] == nums[i - 1]:

            continue  # Skip duplicates


        left, right = i + 1, n - 1

        while left < right:

            total = nums[i] + nums[left] + nums[right]

            if total < 0:

                left += 1

            elif total > 0:

                right -= 1

            else:

                res.append([nums[i], nums[left], nums[right]])

                # Skip duplicates

                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 res

Time & Space Complexity

• Time: O(n²) (sorting is O(n log n), two-pointer traversal is O(n²)).
• Space: O(1) (ignoring output storage, which is O(n) in worst case).

Why This Works

• Sorting allows us to use two pointers efficiently.
• Skipping duplicates ensures unique triplets.
• Early termination optimizes for sorted arrays.

Example 2 – Medium: Three Sum with Duplicates (Follow-up)

Problem: Same as above, but the input may have more than 3 duplicates (e.g., [-1, -1, -1, 0, 1, 1]).

Input: nums = [-1, -1, -1, 0, 1, 1] Output: [[-1, 0, 1]]

Key Adjustment

• After finding a valid triplet, skip all duplicates for left and right: python while left < right and nums[left] == nums[left + 1]:
left += 1 while left < right and nums[right] == nums[right - 1]:
right -= 1

Python Code (Same as above, but with stricter duplicate handling)

def threeSum(nums):

    nums.sort()

    res = []

    n = len(nums)


    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:

            total = nums[i] + nums[left] + nums[right]

            if total < 0:

                left += 1

            elif total > 0:

                right -= 1

            else:

                res.append([nums[i], nums[left], nums[right]])

                # Skip ALL duplicates

                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 res

Why This Works

• The stricter duplicate skipping ensures no repeated triplets, even with multiple duplicates.

Example 3 – Hard: Three Sum Closest (LeetCode 16)

Problem: Given an array nums and a target target, find three integers such that their sum is closest to target. Return the sum.

Input: nums = [-1, 2, 1, -4], target = 1 Output: 2 (because -1 + 2 + 1 = 2 is closest to 1)

Step-by-Step Solution

1. Sort the array: [-4, -1, 1, 2]
2. Initialize closest_sum = infinity
3. Iterate with fixed i:
4. i = 0 (nums[i] = -4):
   • left = 1, right = 3
   • current_sum = -4 + (-1) + 2 = -3 → Update closest_sum if |-3 - 1| < |closest_sum - 1|
   • current_sum < target → left++
   • current_sum = -4 + 1 + 2 = -1 → Update closest_sum
   • current_sum < target → left++ → break
5. i = 1 (nums[i] = -1):
   • left = 2, right = 3
   • current_sum = -1 + 1 + 2 = 2 → Closest to target → Update closest_sum
   • current_sum > target → right-- → break
6. Return closest_sum

Python Code

def threeSumClosest(nums, target):

    nums.sort()

    closest_sum = float('inf')

    n = len(nums)


    for i in range(n - 2):

        left, right = i + 1, n - 1

        while left < right:

            current_sum = nums[i] + nums[left] + nums[right]

            if abs(current_sum - target) < abs(closest_sum - target):

                closest_sum = current_sum

            if current_sum < target:

                left += 1

            elif current_sum > target:

                right -= 1

            else:

                return current_sum  # Early exit if exact match

    return closest_sum

Time & Space Complexity

• Time: O(n²) (same as Three Sum).
• Space: O(1).

Why This Works

• The two-pointer approach efficiently narrows down the closest sum.
• Early exit if an exact match is found.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. Three Sum is all about sorting, two pointers, and skipping duplicates. Here’s the playbook: 1. Sort the array—this lets you use two pointers. 2. Loop with a fixed i, treating nums[i] as the first number. 3. Skip duplicates for i to avoid repeats. 4. Use two pointers (left, right) to find pairs that sum to -nums[i]. 5. Skip duplicates for left and right after finding a valid triplet. 6. Early termination if nums[i] > 0 (since the array is sorted). Time complexity? O(n²). Space? O(1) if you ignore sorting. Now go crush it—you’ve got this!

? Final Notes

• Practice Variations:
• LeetCode 15 (Three Sum)
• LeetCode 16 (Three Sum Closest)
• LeetCode 18 (Four Sum) (same pattern, but with an extra loop).
• Whiteboard Tip: Always write the sorted array first and mark i, left, right with arrows.

This framework is directly usable in interviews—memorize the steps, and you’ll solve Three Sum problems with confidence. ?