Nested two-pointer is still quadratic
Updated
Outer i, inner L/R on the suffix is O(n) inner scans times n outer indices: O(n²). 3-sum is this. Calling it two pointers does not make it linear.
What to focus on
The inner pointers reset for each i. Resetting is the nest. A single inward pass without an outer i is the linear one.
Worked examples
3-sum shape
a = [1, 4, 9], t=14, fix i=0- inner L=1 R=2 on [4, 9]
- 4+9=13, one inner scan
- then i=1 inner on [9]
Result: n inner scans, O(n²)
count inner steps
a = [1, 4, 9, 1] sorted [1, 1, 4, 9], each i two-pointer suffix- i=0 suffix len 3
- i=1 suffix len 2
- i=2 suffix len 1
Result: 3+2+1=6 inner moves, Θ(n²)
contrast linear
a = [1, 4, 9], t=13, no outer i- L=0 R=2, 1+9=10, L++
- L=1 R=2, 4+9=13 hit
- two moves total
Result: O(n), not nested
Try it
Write countInner(a). a is a sorted array of integers. Outer i resets inner L and R on the suffix. Print inner L/R moves of 3-sum (fix i), then moves of plain two-sum. Label O(n²) vs O(n). For a = [1, 1, 4, 9] count 3-sum inner moves. Then two-sum t=13 on [1, 4, 9].
a is sorted non-decreasing, length ≥ 3 for the nested scan. Length ≥ 2 for the linear contrast.