LeetCode 16: 3Sum Closest Solution in Python – A Step-by-Step Guide

What Is LeetCode 16: 3Sum Closest?

In LeetCode 16: 3Sum Closest, you’re handed an integer array nums and a target integer target. Your task is to find three distinct elements—nums[i], nums[j], nums[k]—where i != j != k, and their sum is closest to target. Unlike 3Sum, which seeks an exact sum of zero, here you’re aiming for proximity, returning the sum itself (not the triplet). For example, with nums = [-1, 2, 1, -4] and target = 1, the closest sum is 2 (from -1 + 2 + 1), since it’s only 1 unit away from the target.

Problem Statement

• Input: An integer array nums and an integer target.
• Output: An integer—the sum of three elements closest to target.
• Rules:
• Use exactly three distinct indices (i != j != k).
• Return the sum, not the triplet.
• If multiple triplets tie for closeness, any of their sums is fine.

Constraints

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -10⁴ <= target <= 10⁴

Examples

• Input: nums = [-1, 2, 1, -4], target = 1
• Output: 2
• Why: -1 + 2 + 1 = 2, closest to 1 (difference of 1).
• Input: nums = [0, 0, 0], target = 1
• Output: 0
• Why: 0 + 0 + 0 = 0, difference of 1 from 1.
• Input: nums = [1, 1, 1, 0], target = -100
• Output: 3
• Why: 1 + 1 + 1 = 3, closest to -100 among all triplets.

Understanding the Problem: Getting Close to the Goal

To solve LeetCode 16: 3Sum Closest in Python, we need to find a triplet whose sum minimizes the absolute difference from target. A brute force approach—checking all possible triplets with three loops—would take O(n³) time, which is sluggish for up to 500 elements. Instead, we’ll use smarter strategies:

• Best Solution (Two-Pointer): O(n²) time, O(1) extra space—efficient and precise.
• Alternative Solution (Brute Force with Optimization): O(n³) time, O(1) space—simpler but slower, with a tweak to make it bearable.

Let’s dive into the Best Solution—the two-pointer approach—with a clear, step-by-step breakdown.

Best Solution: Two-Pointer Approach

Why This Is the Best Solution

The two-pointer technique is the star here because it cuts the time complexity to O(n²) and uses almost no extra space (O(1) beyond the input). By sorting the array, it turns a messy search into a streamlined process, comparing sums and tracking the closest one. It’s like having two helpers scan a sorted list, adjusting their positions to zero in on the target—fast, smart, and effective!

How It Works

Here’s the playbook:

• Step 1: Sort the Array:
• Sort nums to enable two-pointer movement and simplify comparisons.
• Step 2: Fix One Number:
• Loop through each element as the first number (nums[i]).
• Remaining target is target - nums[i].
• Step 3: Use Two Pointers:
• Set left (after i) and right (end of array).
• Compute the sum: nums[i] + nums[left] + nums[right].
• Update the closest sum if this one’s nearer to target.
• Adjust pointers:
• Sum > target? Move right left.
• Sum < target? Move left right.
• Step 4: Track the Closest:
• Keep a running closest_sum, updating it when a better match is found.

Step-by-Step Example

Example: nums = [-1, 2, 1, -4], target = 1

• Sort: [-4, -1, 1, 2].
• Initialize: closest_sum = -4 + -1 + 1 = -4 (first triplet), diff = 5.
• i = 0, nums[i] = -4:
• left = 1 (-1), right = 3 (2) → -4 + -1 + 2 = -3, diff = 4 < 5 → closest_sum = -3.
• left = 2 (1), right = 3 (2) → -4 + 1 + 2 = -1, diff = 2 < 4 → closest_sum = -1.
• i = 1, nums[i] = -1:
• left = 2 (1), right = 3 (2) → -1 + 1 + 2 = 2, diff = 1 < 2 → closest_sum = 2.
• i = 2: Only 1 element left, stop.
• Result: closest_sum = 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down for clarity:

Copy codeclass Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # Step 1: Sort the array
        nums.sort()
        n = len(nums)
        # Initialize with first triplet
        closest_sum = nums[0] + nums[1] + nums[2]

        # Step 2: Loop through each element as first number
        for i in range(n - 2):
            # Step 3: Set two pointers
            left = i + 1
            right = n - 1

            # Step 4: Find closest sum
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                # Update closest_sum if current_sum is closer
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum

                # Adjust pointers
                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return current_sum  # Exact match, return immediately

        return closest_sum

• Line 4: Sort nums—O(n log n)—to enable two-pointer logic.
• Line 6: Initialize closest_sum with the first three numbers.
• Line 9: Loop up to n-2 (need two more numbers).
• Line 11-12: Set left after i, right at end.
• Line 15-23: Two-pointer loop:
• Line 16: Compute current sum.
• Line 18-19: Update closest_sum if closer to target.
• Line 22: Sum < target, move left up.
• Line 24: Sum > target, move right down.
• Line 26: Exact match, return it (can’t get closer).
• Time Complexity: O(n²)—sorting O(n log n) + O(n²) for two-pointer.
• Space Complexity: O(1) extra space.

This solution zeroes in on the target like a pro!

Alternative Solution: Brute Force with Optimization

Why an Alternative Approach?

The brute force approach with optimization is a straightforward fallback—O(n³) time, O(1) space. It checks every triplet but adds a trick: it stops early if it finds an exact match and tracks the closest sum. It’s like exhaustively trying every combination with a notepad to record the best fit—simple but slower.

How It Works

Here’s the plan:

• Step 1: Use three nested loops to pick i, j, k.
• Step 2: Compute the sum for each triplet.
• Step 3: Update closest_sum if the current sum is nearer to target.
• Step 4: Return early if an exact match is found.

Step-by-Step Example

Example: nums = [-1, 2, 1, -4], target = 1

• Initialize: closest_sum = -1 + 2 + 1 = 2, diff = 1.
• i=0, j=1, k=2: -1 + 2 + 1 = 2, diff = 1 (already set).
• i=0, j=1, k=3: -1 + 2 + -4 = -3, diff = 4 > 1, skip.
• i=0, j=2, k=3: -1 + 1 + -4 = -4, diff = 5 > 1, skip.
• i=1, j=2, k=3: 2 + 1 + -4 = -1, diff = 2 > 1, skip.
• Result: closest_sum = 2.

Code for Brute Force Approach

Copy codeclass Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        closest_sum = nums[0] + nums[1] + nums[2]

        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    current_sum = nums[i] + nums[j] + nums[k]
                    if current_sum == target:
                        return current_sum
                    if abs(current_sum - target) < abs(closest_sum - target):
                        closest_sum = current_sum

        return closest_sum

• Line 5: Start with first triplet.
• Line 7-12: Triple loop over all triplets:
• Line 10: Check if exact match (early exit).
• Line 12: Update if closer.
• Time Complexity: O(n³)—three nested loops.
• Space Complexity: O(1).

It’s a thorough but slow search!

Comparing the Two Solutions

• Two-Pointer (Best):
• Pros: O(n²) time, O(1) space, fast and elegant.
• Cons: Requires sorting.
• Brute Force (Alternative):
• Pros: O(n³) time, O(1) space, simple logic.
• Cons: Much slower.

Two-pointer wins hands down.

Additional Examples and Edge Cases

• [1, 2, 3], target = 0: 6 (only triplet).
• [-2, 0, 1, 2], target = 2: 1 (-2 + 0 + 3).
• [0, 0, 0], target = 0: 0 (exact match).

Both handle these smoothly.

Complexity Breakdown

• Two-Pointer: Time O(n²), Space O(1).
• Brute Force: Time O(n³), Space O(1).

Two-pointer’s the practical choice.

Key Takeaways

• Two-Pointer: Sort and slide to the closest!
• Brute Force: Check everything, optimize lightly!
• Precision: Absolute differences guide us.
• Python Tip: Sorting simplifies—see [Python Basics](/python/basics).

Final Thoughts: Close the Gap

LeetCode 16: 3Sum Closest in Python is a precision challenge that rewards efficiency. The two-pointer approach nails it with speed, while brute force offers a fallback with grit. Want more array fun? Check out LeetCode 15: 3Sum or LeetCode 1: Two Sum. Ready to get close? Head to Solve LeetCode 16 on LeetCode and hit that target today!