Problem

An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.

Given the grid grid represented as a string array, return the number of regions.

Note that backslash characters are escaped, so a '\' is represented as '\\'.

Examples

Example 1:

1
2
3

Input: grid = [" /","/ "]
Output: 2
Explanation: This is 2x2 grid:

Example 2:

1
2

Input: grid = [" /","  "]
Output: 1

Example 3:

1
2
3

Input: grid = ["/\\","\\/"]
Output: 5
Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.

Solution

Method 1 - Using Union Find

Each 1x1 square is divided into 4 smaller triangles. We can label these triangles as follows:

  • Top-left triangle: 0
  • Top-right triangle: 1
  • Bottom-left triangle: 2
  • Bottom-right triangle: 3

So, we can use union find data structure to simulate that.

  • Use the Union-Find structure to keep track of connected regions.
  • Initialize the Union-Find structure to have ( n \times n \times 4 ) elements (each small triangle in the grid).

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

public class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        int totalCells = n * n * 4;
        UnionFind uf = new UnionFind(totalCells);

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                int base = 4 * (r * n + c);
                char val = grid[r].charAt(c);

                // Connect triangles within the cell
                if (val == '/') {
                    uf.union(base, base + 3);
                    uf.union(base + 1, base + 2);
                } else if (val == '\\') {
                    uf.union(base, base + 1);
                    uf.union(base + 2, base + 3);
                } else {
                    uf.union(base, base + 1);
                    uf.union(base + 1, base + 2);
                    uf.union(base + 2, base + 3);
                }

                // Connect triangles with neighboring cells
                // Connect with the right cell
                if (c + 1 < n) {
                    uf.union(base + 1, 4 * (r * n + (c + 1)) + 3);
                }
                // Connect with the bottom cell
                if (r + 1 < n) {
                    uf.union(base + 2, 4 * ((r + 1) * n + c));
                }
            }
        }

        return uf.getNumComponents();
    }
	static class UnionFind {  
		private int[] parent;  
		private int[] rank;  
		
		private int numComponents;  
		
		public UnionFind(int size) {  
			this.numComponents = size;  
			makeSet();  
		}  
		
		
		public void makeSet() {  
			rank = new int[numComponents];  
			parent = new int[numComponents];  
			for (int i = 0; i < parent.length; i++) {  
				parent[i] = i;  
				rank[i] = 0;  
			}  
		}  
		   
		public boolean union(int i, int j) {  
			int rootI = find(i);  
			int rootJ = find(j);  
			if (rootI == rootJ) {  
				return false;  
			}  
			// make parent with higher rank  
			if (rank[rootI] < rank[rootJ]) {  
				parent[rootI] = rootJ;  
			} else if (rank[rootI] > rank[rootJ]) {  
				parent[rootJ] = rootI;  
			} else {  
				// equal case  
				parent[rootJ] = rootI;  
				rank[rootI]++;  
			}  
			numComponents--;  
			return true;    
		}  
		
		public int find(int i) {  
			while (parent[i] != i) {  
				i = parent[i];  
			}  
			return i;  
		}  
		
		public int getNumComponents() {  
			return numComponents;  
		}  
		
		public boolean isConnected(int i, int j) {  
			return find(i) == find(j);  
		}  
		
		public int count() {  
			return numComponents;  
		}  
	
	}    
}

Complexity

  • ⏰ Time complexity: O(n^2)
    • The outer loops iterate through every cell in an ( n \times n ) grid. Thus, the number of iterations is ( O(n^2) ).
    • Within each cell, for each of the 4 triangles, we perform union operations.
    • Each union operation and find operation in the Union-Find structure are amortized ( O(\alpha(N)) ), where ( \alpha ) is the inverse Ackermann function, which grows very slowly and is practically constant for typical input sizes.
    • Given that we perform a constant number (up to 12) of union/find operations per cell, this step is ( O(1) ) per cell.
  • 🧺 Space complexity: O(n^2)
    • We use a Union-Find structure to manage ( 4 \times n \times n ) elements.
    • The space required for the parent and rank arrays is ( O(4 \times n^2) = O(n^2) ).

Dry Run

Lets take eg. 1, then, we have:

1

Input: grid = [" /","/ "]

So, we have grid like:

Initially n = 4, For each 1x1 cell, we’ll divide it into four smaller triangles, numbered 0 to 3, this is how our grid looks with 16 triangles in it, labeled 0 to 15:

Processing each cell

Cell (0, 0) = " " ⇨ union(0, 1), union(1, 2), union(2, 3)

Cell (0,1) = “/” ⇨ union(4, 7), union(5, 6)

Cell (1, 0) = “/” ⇨ union(8, 11), union(9, 10)

Cell (1, 0) = " " ⇨ union(12, 13), union(13, 14), union(14, 15)

Connecting neighbouring cells
  1. Between (0, 0) and (0, 1): Union(1, 7)
  2. Between (0, 1) and (1, 1): Union(7, 15)
  3. Between (0, 0) and (1, 0): Union(2, 8)
  4. Between (1, 0) and (1, 1): Union(10, 12)
Final answer

This is how number of components in 2.