Which pairs can disappear?

Sorted [1,3,5,8,10], target 9.

The endpoints total 11. Name every pair that can be removed by that one comparison.

1 / 10

Derive the movement

Start with all index pairs.

A map stores earlier witnesses. Sorted order instead lets one comparison retire an endpoint.

Would that proof survive unsorted [3,2,4], target 6?

2 / 10

Trace: sorted two-sum

[1,2,4,8], target 6

1+8>6: remove endpoint 8.

1+4<6: remove endpoint 1.

2+4=6: return indices [2,3].

3 / 10

Trace: water is not sorted sum

Heights [1,8,6,2,5,4,8,3,7]

First area: 8. Discard height 1.

Next area: 49. Discard the right height 7.

A safe move need not improve the next area.

4 / 10

Subsequence: take the earliest match

s="aba", t="aabba"

Match positions 0,2,4 in t.

Does skipping the first usable a ever leave more room?

5 / 10

Palindrome: what is a character?

"0P" is not a palindrome.

" , " is a palindrome after filtering.

The contract retains ASCII digits and letters; comparisons fold ASCII case.

6 / 10

Partition: do not advance mid yet

[1,2,0], low=0, mid=1, high=2

Swap 2 with 0 → [1,0,2].

Which value is still unclassified?

7 / 10

3Sum: indices versus values

[0,0,0,0]

Four index triples. One value triple.

Explain the two independent sources of duplicate output.

8 / 10

Reversal: stronger than an involution

Reverse twice → original.

But doing nothing also has that property.

Check output[i]=original[n-1-i] after one reversal.

9 / 10

Transfer checkpoint

Which proof survives unsorted input?

Which algorithm sorts its caller’s slice?

Which returns one-based indices?

10 / 10