Array

An array label is a topic rather than a solvable specification. Clarify the desired result, whether the input is sorted, whether values repeat, whether the array may be mutated, and whether an O(n) solution is required. Then select a technique based on the actual relation: two pointers for a sorted pair or partition problem, a hash map for membership or prefix-sum lookup, sorting when reordering is acceptable, and a monotonic structure for next-greater style queries. Explain one invariant, such as: every element before write satisfies the filter, or the map stores earliest prefix indices. Exercise empty input, one element, all equal values, negative values, integer overflow, and answers at index zero or the last index. Avoid guessing a famous array question from a vague label. Big-O notation must match the selected method: a scan is O(n) time and O(1) extra space; a hash map is O(n) expected time and O(n) space.