Operation costs
Let n be input length, d the number of distinct values, and q the number of copied entries. Integer arithmetic and integer hashing are treated as constant cost.
| Operation | Time | Storage / condition |
|---|---|---|
| List indexing | O(1) | Direct position access |
| List membership | O(n) | Sequential value comparisons |
| dict/set lookup and update | Expected O(1), worst O(n) | Hashable keys; long-key hashing has its own cost |
| Copy q entries | O(q) | O(q) shallow reference copy |
| Sort n entries | Worst O(n log n) | O(n) Python workspace |
| Store latest position per value | Expected O(n) for a scan | O(d) retained state |
| Two pointers in sorted values | O(n) | O(1) auxiliary space |
State and assumptions
For Two Sum, record earlier values only after lookup. For nearby duplicates, retain the latest occurrence and update after a failed distance check. Two-pointer elimination requires sorted values and distinct positions. For 3Sum, distinguish distinct positions from distinct output value triplets, and count copying, sorting, and output storage separately.
Core sources
Erik Demaine and Srini Devadas, Introduction to Algorithms, MIT 6.006 (Fall 2011).