Arrays

Arrays cover many incompatible problems, so a strong answer begins with questions instead of an algorithm. Ask for the desired output, input size, sortedness, duplicates, numeric range, and whether reordering or extra memory is permitted. Pick a technique only after that: prefix sums for range or subarray totals, a hash map for prior-state lookup, two pointers for monotonic sorted relations, or a monotonic stack for nearest-greater relations. Describe a single invariant in plain language and use a three- or four-element dry run to show updates. Verify empty and singleton arrays, all-equal values, negative values, answers touching either boundary, and overflow in totals. If the interviewer asks for in-place work, distinguish output storage from auxiliary storage. A linear scan is O(n) time and often O(1) space; a map-based scan is generally O(n) expected time and O(n) space. Avoid guessing a problem from a category-only report.