3Sum Closest - Step-by-Step with Java

Problem Statement

The problem asks us to find three numbers in an array whose sum is closest to a given target value.

Example Input: nums = [-1, 2, 1, -4], **target = 1 **Expected Output**:2`

---

Approach

We can solve the problem using the Two Pointer Technique with a sorted array. Here's a high-level summary of the solution:

1. Sort the array to prepare for the two-pointer method.

2. Iterate through each number in the array. For each number:

   • Fix the number as the first number (nums[start]).

   • Use two pointers, left and right, to explore the remaining numbers.

3. Calculate the sum of the three numbers.

4. Update the closest sum whenever the new sum is closer to the target than the previous closest value.

5. Adjust the pointers (left++ or right--) based on the comparison between sum and target.

---

Code

Here is the final Java solution:

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);  // Step 1: Sort the array
        int closest = Integer.MAX_VALUE;  // Closest sum initialized to max value

        for (int i = 0; i < nums.length; i++) {
            int start = i;  // Fix the current number
            int left = i + 1;  // Left pointer
            int right = nums.length - 1;  // Right pointer

            while (left < right) {  // Step 2: Two-pointer approach
                int sum = nums[start] + nums[left] + nums[right];

                // Step 3: Update closest sum
                if (Math.abs(sum - target) < Math.abs(closest - target)) {
                    closest = sum;
                }

                if (sum == target) return sum;  // Perfect match

                // Move pointers
                if (sum < target) {
                    left++;  // Increase the sum
                } else {
                    right--;  // Decrease the sum
                }
            }
        }
        return closest;  // Return the closest sum
    }
}

---

Step-by-Step Execution

We will use the input nums = [-1, 2, 1, -4] and target = 1.

Step 1: Sort the Array

The input array becomes:

cssCopy codeSorted nums = [-4, -1, 1, 2]

You can use a diagram to visualize this:

Image 1: Array before and after sorting

Original: [-1, 2, 1, -4]
Sorted:   [-4, -1, 1, 2]

---

Step 2: Initialize Pointers

We loop through the array, starting with i = 0:

• start = i = 0 → nums[start] = -4

• left = 1 → nums[left] = -1

• right = 3 → nums[right] = 2

Initial pointers:

codenums = [-4, -1, 1, 2]
            ↑    ↑    ↑
          start left right

---

Step 3: Calculate the First Sum

• First sum = nums[start] + nums[left] + nums[right] = -4 + (-1) + 2 = -3

• Compare |target - sum|:

  • target = 1

  • difference = |1 - (-3)| = 4

• Update closest to -3 because it's the first valid sum.

Image 2: State after the first calculation

codeSum = -3
Closest = -3

---

Step 4: Move Pointers

Since sum < target, we increment left:

• left = 2 → nums[left] = 1

New pointers:

codenums = [-4, -1, 1, 2]
             ↑       ↑  ↑
           start   left right

---

Step 5: Calculate the New Sum

• New sum = -4 + 1 + 2 = -1

• Compare |target - sum|:

  • difference = |1 - (-1)| = 2

• Update closest to -1 because it's closer to the target than -3.

Image 3: State after the second calculation

Sum = -1
Closest = -1

---

Step 6: Move Pointers Again

Since sum < target, increment left:

• left = 3 → Now left equals right, so the while loop ends.

---

Step 7: Move to the Next Start

Now, i = 1:

• start = 1 → nums[start] = -1

• left = 2 → nums[left] = 1

• right = 3 → nums[right] = 2

New pointers:

nums = [-4, -1, 1, 2]
            ↑   ↑  ↑
          start left right

---

Step 8: Calculate the Sum

• Sum = -1 + 1 + 2 = 2

• Compare |target - sum|:

  • difference = |1 - 2| = 1

• Update closest to 2 because it's closer than -1.

Image 4: State after final calculation

codeSum = 2
Closest = 2

---

Step 9: End of Iteration

The loop ends, and the closest sum is returned as 2.

---

Conclusion

With clear visuals and diagrams at each step, you can demonstrate how the pointers move and how the closest sum is updated. Here’s a summary of the pointer movements and sums:

Final Output:

Closest Sum = 2