Array Traversal in O(n) Time, O(1) Space

Problem Starting from a working brute-force array solution that uses nested loops or an auxiliary hashmap/array, redesign it so the answer is produced in a single left-to-right pass using only a constant number of extra variables — O(n) time, O(1) auxiliary space. The prompt is the optimization itself: drive both time and space down and justify the invariant.

Input / Output

• Input: an integer array arr of length n, read-only unless the problem explicitly permits in-place mutation.
• Output: the problem's answer — a value, an index, or the array mutated in place — computed without allocating O(n) scratch space.

Constraints

• 1 <= n <= 10^5-10^6, so an O(n^2) double loop will time out.
• O(1) extra memory: a fixed set of counters/pointers only. No auxiliary array, no hashmap. The input array itself may sometimes be reused as storage if mutation is allowed.

Example

• Maximum subarray sum: arr = [-2,1,-3,4,-1,2,1,-5,4] -> 6, carrying only best and current rather than an O(n) DP table. The all-negative case arr = [-3,-1,-2] -> -1 is the tricky one: initialising best to 0 instead of arr[0] silently returns the wrong answer.