Week 1 Reference Sheets

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).