Shortest Unsorted Continuous Subarray (Array/Pointers)

To solve this efficiently, I would avoid full sorting since it takes O(n log n). Instead, I aim for an O(n) approach using two passes. First, I'll traverse from left to right, tracking the maximum value encountered. If I find an element smaller than this current maximum, it means this element is out of place and marks a potential end of our unsorted subarray. I update my 'end' pointer whenever this happens. Next, I'll do a reverse pass from right to left, tracking the minimum value. If an element is larger than this running minimum, it indicates an out-of-order position on the left side, updating my 'start' pointer. Finally, if no such elements are found, the array is already sorted. Otherwise, the length is simply end minus start plus one. For example, in [2, 6, 4, 8, 10, 9, 15], the max scan identifies 4 as out of place after 6, setting end to index 2. The min scan finds 6 out of place after 10, setting start to index 1. Sorting indices 1 through 5 fixes the whole array. This method ensures we only touch necessary elements, aligning with Google's focus on performance optimization.