LeetCode 15 3Sum - Example and Complexity Analysis

Trace nums = [-1, 0, 1, 2, -1, -4].

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

Fix -4 (index 0). Two pointers find pairs summing to 4. No valid pairs exist.

Fix -1 (index 1). Find pairs summing to 1:

• Left at -1, right at 2: sum = 1. Found [-1, -1, 2].
• Skip duplicate left. Left at 0, right at 2: sum = 2 > 1. Move right.
• Left at 0, right at 1: sum = 1. Found [-1, 0, 1].

Skip index 2 (same as index 1). Fix 0 (index 3). No valid pairs.

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

Outer loop: $n$ iterations. Inner two-pointer search: $O(n)$. Total: $O(n^2)$ time.

Sorting is $O(n \log n)$, dominated by $O(n^2)$. Space is $O(1)$ excluding output.