Arrays & Hashing
Arrays and hashing are the foundational tools for a vast category of interview problems. Mastery lies not in knowing their basic operations, but in recognizing and applying patterns that optimize solutions from brute-force to linear time.
A category of problems solved by scanning through the array once (or a constant number of times) to gather required information. This includes finding specific values (like the maximum or second maximum), or identifying elements based on neighbors (like array leaders). The key is to maintain trackers (such as a running max) as you iterate. Often, you might traverse from the right end when right-side context is needed (as in the leaders problem).
Example Problems:
Linear SearchLargest Element in ArraySecond Largest ElementLeaders in an Array
Solution Spotlight: Leaders in an Array
By scanning the array from the right, this solution finds all leaders efficiently. The trick is to keep track of the maximum element seen so far from the right. Any element greater than this
maxFromRight is a leader since nothing to its right is larger. Similarly, one-pass traversals can compute simple statistics (like max or min) in O(n) by updating trackers, eliminating the need for multiple passes or sorting.LeadersinanArray.java
Loading code syntax...