# 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:

```java
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:

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

You can use a diagram to visualize this:

**Image 1: Array before and after sorting**

```plaintext
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:**

```plaintext
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**

```plaintext
codeSum = -3
Closest = -3
```

---

### **Step 4: Move Pointers**

Since `sum < target`, we increment `left`:

* `left = 2` → `nums[left] = 1`
    

**New pointers:**

```plaintext
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**

```plaintext
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:**

```plaintext
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**

```plaintext
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:

| Iteration | `start` | `left` | `right` | Sum | Closest |
| --- | --- | --- | --- | --- | --- |
| 1 | \-4 | \-1 | 2 | \-3 | \-3 |
| 2 | \-4 | 1 | 2 | \-1 | \-1 |
| 3 | \-1 | 1 | 2 | 2 | 2 |

### Final Output:

```plaintext
Closest Sum = 2
```