Skip to main content

Two Pass

Premium

The two pass technique involves traversing the data structure twice (or making two passes) to solve a problem. This approach helps when the first pass is used to gather or calculate important information that simplifies the problem, while the second pass applies that information to reach the solution.

When to use it

You can identify problems that can be solved using the two pass technique if they meet one or more of these conditions:

  1. The problem is better solved by preprocessing the data first, which can often reduce the complexity of the second pass.
  2. The problem involves constraints that are more easily handled by analyzing the data in one direction first, then solving or refining the solution in another direction.

Why use it

Two passes allows you to avoid intricate logic in a single pass and can improve clarity, though it may come at the cost of processing time or space efficiency (since you're traversing twice). Typically, this is still efficient with O(n)O(n) time complexity when each pass is linear.

How it works

In the first pass, you gather data or set up constraints that inform the second pass. The second pass processes the data based on the gathered information, yielding the final result.

Let's say you need to find the distance from each character in a string s to a given target character (target). For example, given the string 'EXPONENT', we want to find how far each letter is from a letter 'E'.

  1. First pass: Scan from left to right through the string. For each character, calculate the shortest distance to the nearest 'E' that appears before it.
  2. Second pass: Scan from right to left through the string. For each character, update the distance by considering the nearest 'E' that appears after it.
Python
s = "EXPONENT"
target = 'E'
n = len(s)
distances = [float('inf')] * n

# 1st pass: Left to right
prev = float('inf')
for i in range(n):
    if s[i] == target:
        prev = i
    if prev != float('inf'):
        distances[i] = i - prev

# 2nd pass: Right to left
prev = float('inf')
for i in range(n - 1, -1, -1):
    if s[i] == target:
        prev = i
    if prev != float('inf'):
        distances[i] = min(distances[i], prev - i)

Two pass

Examples

  1. Array product except self
    • Problem: Find the product of all elements except the current element in an array.
    • Approach: Use two passes: one to calculate the left-side products and another to incorporate right-side products.
  2. Maximum water container
    • Problem: Find the maximum water trapped between the bars of a histogram.
    • Approach: Use one pass to calculate the maximum heights from the left, and a second pass to incorporate maximum heights from the right.
  3. Candy distribution problem
    • Problem: Distribute candy to children based on ratings, ensuring higher-rated children get more candy than their neighbors.
    • Approach: Use two passes: one to assign candies based on left neighbors, and another to correct based on right neighbors.
Next Lesson