LeetCode 16 3Sum Closest - Example and Complexity Analysis

Trace nums = [-1, 2, 1, -4] with target = 1.

Sort: [-4, -1, 1, 2]. Initialize closest = -4 + (-1) + 1 = -4.

Fix -4 (index 0). Left at -1, right at 2:

• Sum = -4 + (-1) + 2 = -3. Difference from 1 is 4. Update closest = -3.
• Sum < target, move left. Left at 1, right at 2:
• Sum = -4 + 1 + 2 = -1. Difference is 2. Update closest = -1.

Fix -1 (index 1). Left at 1, right at 2:

• Sum = -1 + 1 + 2 = 2. Difference is 1. Update closest = 2.

Fix 1 (index 2). Only one element right of it. Skip.

Return 2.

Outer loop: $O(n)$. Inner two-pointer: $O(n)$. Total: $O(n^2)$ time, $O(1)$ space.