Many array problems that seem complex at first can be solved elegantly using a two-pass approach. This technique involves traversing the array twice, each time collecting different information that you later combine to produce the final result.
The key insight is to break down a complex calculation into simpler parts. Instead of trying to compute everything in one pass, you can:
This approach is particularly powerful when you need information about "everything except the current element" or when you need to consider both preceding and following elements for each position.
Consider a simpler example: finding the maximum element to the left and right of each position in an array. A two-pass solution would first traverse left-to-right to find the maximum element to the left of each position, then traverse right-to-left to find the maximum to the right.
The beauty of two-pass algorithms is that they often achieve O(n) time complexity while remaining easy to understand and implement. They're also space-efficient because you can often reuse the same result array to store intermediate values from the first pass.
1def max_left_and_right(nums):
2 """For each position, find max element to left and right"""
3 n = len(nums)
4 result = [[0, 0] for _ in range(n)]
5
6 # First pass: find max to the left
7 max_left = float('-inf')
8 for i in range(n):
9 result[i][0] = max_left
10 max_left = max(max_left, nums[i])
11
12 # Second pass: find max to the right
13 max_right = float('-inf')
14 for i in range(n - 1, -1, -1):
15 result[i][1] = max_right
16 max_right = max(max_right, nums[i])
17
18 return result