Array manipulation

What it is

"Array" as a label doesn't name one technique — it names the family of questions where the input is a flat, unordered (or arbitrarily ordered) list of numbers and the challenge is entirely about how you look at it: once, twice, forward, backward, with or without an auxiliary hash set. Under this label you'll find hashing for O(1) membership checks, running-sum tricks (Kadane's algorithm, prefix/suffix products), and index-as-hash-slot tricks that get you O(1) space when values are bounded. What ties them together is the absence of any other structure (no order, no tree, no graph) to lean on, so the array itself, and how many times you're willing to walk it, is the whole design space.

When it applies

• The input is a single flat array with no guaranteed order, and the question is about counting, finding, or transforming values by their content rather than their position.
• A first instinct produces an O(n²) nested loop (compare every pair, or rescan for each element); the question is whether a hash set, a running total, or the value range itself lets you cut that to O(n).
• Space is explicitly constrained to O(1), which usually signals you're meant to reuse the input array itself as scratch space (via sign-flipping or index remapping) rather than allocate a second structure.
• If the array is sorted and the technique hinges on that order, you're more likely in two-pointers or binary search territory; if the real ask is about sums over ranges rather than transforming the whole array, prefix sums is the more precise fit.

Tells in the problem

• "Return in O(n) time" paired with "O(1) extra space" — a strong signal the values themselves (their range, or their sign) are meant to double as storage.
• Values are guaranteed to lie in [1, n] where n is the array length — a hint to use each value's own index as a marker instead of a hash set.
• "Without using division" attached to a per-element product or aggregate — forces two one-directional sweeps instead of one.
• A guarantee like "exactly one pair" or "a majority element always exists" — the guarantee is there so you don't have to handle the no-answer case, and often unlocks a single-pass solution.
• The answer is a contiguous run or best single value derived by extending or resetting a running quantity as you scan left to right.

The classic mistake

The recurring failure is reaching immediately for the nested-loop, compare-everything-against-everything solution because it's the first thing that comes to mind for "find a pair" or "find a duplicate," and then not stepping back to ask what a single well-chosen pass with a hash set or a running value could replace it with. This happens because the brute force is easy to state correctly, so it feels safe to start typing it — but on the array sizes these questions specify (often in the hundreds of thousands), it's the wrong complexity from the start. Notice the trap by asking, before writing any loop, "am I about to re-scan the array from inside a scan of the array" — if yes, look for what a set, a counter, or a running total from the first pass would tell you instead.

Questions to start with

• Two Sum — the canonical hash-map-instead-of-nested-loop exercise; every other question here is a variation on this trade.
• Contains Duplicate — the simplest possible "have I seen this before" check with a hash set.
• Maximum Subarray — introduces the running-value idea (Kadane's algorithm): decide to extend or restart at each position.
• Product of Array Except Self — forces two directional passes instead of one, since division is off the table.
• First Missing Positive — the hardest of the set: reuses the array itself as a hash table to hit O(1) space.