Two Pass Method

The Two Pass Method is a technique generally used in image processing or graph algorithms to label connected components. In the first pass, you iterate through each element and assign provisional labels. In the second pass, you finalize these labels based on some criteria, ensuring that all connected elements share the same label.

Algorithm

  1. First Pass: Iterate through the data structure and assign temporary labels to connected components based on some condition.
  2. Second Pass: Iterate again to update the labels so that all connected elements have the same label.

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class TwoPassMethod {
  public static int[] twoPass(int[] arr) {
    int n = arr.length;
    
    // First pass
    for (int i = 1; i < n; i++) {
      if (arr[i] == arr[i-1]) {
        arr[i] = i;
      }
    }

    // Second pass
    for (int i = n-1; i > 0; i--) {
      if (arr[i] == arr[i-1]) {
        arr[i-1] = arr[i];
      }
    }

    return arr;
  }
}

C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <vector>

std::vector<int> twoPass(std::vector<int> arr) {
  int n = arr.size();
  
  // First pass
  for (int i = 1; i < n; ++i) {
    if (arr[i] == arr[i-1]) {
      arr[i] = i;
    }
  }
  
  // Second pass
  for (int i = n-1; i > 0; --i) {
    if (arr[i] == arr[i-1]) {
      arr[i-1] = arr[i];
    }
  }
  
  return arr;
}

Python Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def two_pass(arr):
    n = len(arr)

    # First pass
    for i in range(1, n):
        if arr[i] == arr[i-1]:
            arr[i] = i

    # Second pass
    for i in range(n-1, 0, -1):
        if arr[i] == arr[i-1]:
            arr[i-1] = arr[i]

    return arr

The Two Pass Method often results in an (O(N)) time complexity, where (N) is the number of elements. It is efficient and effective for labelling problems.