# Count Cells in Overlapping Horizontal and Vertical Substrings **Difficulty:** MEDIUM [External](https://leetcode.com/problems/count-cells-in-overlapping-horizontal-and-vertical-substrings) Canonical: https://scaleengineer.com/dsa/problems/count-cells-in-overlapping-horizontal-and-vertical-substrings **Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function) **Data structures:** Array, String, Matrix --- ## Problem You are given an `m x n` matrix `grid` consisting of characters and a string `pattern`. A **horizontal substring** is a contiguous sequence of characters read from left to right. If the end of a row is reached before the substring is complete, it wraps to the first column of the next row and continues as needed. You do **not** wrap from the bottom row back to the top. A **vertical substring** is a contiguous sequence of characters read from top to bottom. If the bottom of a column is reached before the substring is complete, it wraps to the first row of the next column and continues as needed. You do **not** wrap from the last column back to the first. Count the number of cells in the matrix that satisfy the following condition: * The cell must be part of **at least** one horizontal substring and **at least** one vertical substring, where **both** substrings are equal to the given `pattern`. Return the count of these cells. **Example 1:** ![](https://assets.glich.co/dsa/count-cells-in-overlapping-horizontal-and-vertical-substrings/image0.png) **Input:** grid = \[\["a","a","c","c"\],\["b","b","b","c"\],\["a","a","b","a"\],\["c","a","a","c"\],\["a","a","b","a"\]\], pattern = "abaca" **Output:** 1 **Explanation:** The pattern `"abaca"` appears once as a horizontal substring (colored blue) and once as a vertical substring (colored red), intersecting at one cell (colored purple). **Example 2:** ![](https://assets.glich.co/dsa/count-cells-in-overlapping-horizontal-and-vertical-substrings/image1.png) **Input:** grid = \[\["c","a","a","a"\],\["a","a","b","a"\],\["b","b","a","a"\],\["a","a","b","a"\]\], pattern = "aba" **Output:** 4 **Explanation:** The cells colored above are all part of at least one horizontal and one vertical substring matching the pattern `"aba"`. **Example 3:** **Input:** grid = \[\["a"\]\], pattern = "a" **Output:** 1 **Constraints:** * `m == grid.length` * `n == grid[i].length` * `1 <= m, n <= 1000` * `1 <= m * n <= 105` * `1 <= pattern.length <= m * n` * `grid` and `pattern` consist of only lowercase English letters. # Approaches ## Brute-Force Simulation This approach directly simulates the process described in the problem. It checks every possible starting cell in the grid for both horizontal and vertical occurrences of the pattern. For each potential start, it performs a direct character-by-character comparison. This method is straightforward but computationally expensive. **Time:** O((m * n) * L) - Let `N = m * n` and `L = pattern.length()`. For both horizontal and vertical scans, we iterate through `O(N)` possible starting positions. For each position, we perform a check that takes `O(L)` time. This results in a total time complexity of `O(N * L)`. · **Space:** O(m * n) - We use two boolean matrices of size `m x n` to store the match information. **Pros:** It is simple to understand and implement as it directly follows the problem statement. **Cons:** The time complexity is very high, making it impractical for large grids or patterns. It will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits. ### Explanation The brute-force approach involves two main stages. First, we identify all cells that are part of any horizontal substring matching the `pattern`. Second, we do the same for vertical substrings. We use two separate boolean grids, `horizontalMatch` and `verticalMatch`, to mark these cells. For the horizontal scan, we can imagine the `m x n` grid being flattened into a single long string of length `m * n` by concatenating rows. We then iterate through all possible starting positions in this flattened string and check if the `pattern` matches. If it does, we mark all the corresponding cells in our `horizontalMatch` grid. A similar process is repeated for the vertical scan, where we imagine the grid flattened column by column. Finally, we iterate through the grid one last time and count the number of cells `(r, c)` for which both `horizontalMatch[r][c]` and `verticalMatch[r][c]` are true. This count is our final answer. ```java class Solution { public int countMatchingCells(char[][] grid, String pattern) { int m = grid.length; int n = grid[0].length; int L = pattern.length(); int N = m * n; if (L > N) { return 0; } boolean[][] horizontalMatch = new boolean[m][n]; boolean[][] verticalMatch = new boolean[m][n]; // Horizontal scan for (int i = 0; i <= N - L; i++) { boolean isMatch = true; for (int k = 0; k < L; k++) { int r = (i + k) / n; int c = (i + k) % n; if (grid[r][c] != pattern.charAt(k)) { isMatch = false; break; } } if (isMatch) { for (int k = 0; k < L; k++) { int r = (i + k) / n; int c = (i + k) % n; horizontalMatch[r][c] = true; } } } // Vertical scan for (int i = 0; i <= N - L; i++) { boolean isMatch = true; for (int k = 0; k < L; k++) { int r = (i + k) % m; int c = (i + k) / m; if (grid[r][c] != pattern.charAt(k)) { isMatch = false; break; } } if (isMatch) { for (int k = 0; k < L; k++) { int r = (i + k) % m; int c = (i + k) / m; verticalMatch[r][c] = true; } } } // Count overlapping cells int count = 0; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (horizontalMatch[r][c] && verticalMatch[r][c]) { count++; } } } return count; } } ``` ### Algorithm * Initialize `m` as the number of rows, `n` as the number of columns, and `L` as the length of the `pattern`. * Create two boolean matrices, `horizontalMatch[m][n]` and `verticalMatch[m][n]`, and initialize all their elements to `false`. These will store whether a cell is part of any horizontal or vertical match, respectively. * **Horizontal Scan:** * Iterate through each possible starting index `i` from `0` to `m*n - L` in a conceptually flattened row-major representation of the grid. * For each `i`, perform a character-by-character comparison to check if the `pattern` matches the grid's content starting from that flattened index. * To get the character at a flattened index `k`, use the mapping `grid[k/n][k%n]`. * If a match is found starting at `i`, iterate from `k = 0` to `L-1` and set `horizontalMatch[(i+k)/n][(i+k)%n]` to `true`. * **Vertical Scan:** * Perform a similar scan, but this time for a column-major flattened representation. * Iterate through each possible starting index `i` from `0` to `m*n - L`. * To get the character at a flattened index `k`, use the mapping `grid[k%m][k/m]`. * If a match is found, update the corresponding cells in the `verticalMatch` matrix to `true`. * **Final Count:** * Initialize a counter `count` to `0`. * Iterate through every cell `(r, c)` of the grid. * If `horizontalMatch[r][c]` and `verticalMatch[r][c]` are both `true`, increment `count`. * Return `count`. ## KMP String Search with Sweep-line A highly efficient approach uses the Knuth-Morris-Pratt (KMP) algorithm for fast pattern searching, combined with a sweep-line technique to efficiently mark all cells covered by matches. This reduces the time complexity from polynomial to linear. **Time:** O(m * n + L) - Let `N = m * n` and `L = pattern.length()`. The KMP search takes `O(N+L)` and the sweep-line marking takes `O(N)`. This is done for both horizontal and vertical directions. The total time complexity is linear with respect to the size of the grid and the pattern. · **Space:** O(m * n + L) - We use boolean matrices and start arrays of size `m*n`, and an LPS array of size `L`. Since `L` can be at most `m*n`, this simplifies to `O(m*n)`. **Pros:** Extremely efficient, with an optimal time complexity that handles large inputs easily.; It's a robust solution for string searching-related problems. **Cons:** The implementation is more complex, requiring a good understanding of the KMP algorithm and the sweep-line technique. ### Explanation This optimal approach improves upon the brute-force method in two key areas: finding matches and marking covered cells. **1. Fast Pattern Searching with KMP:** Instead of a naive `O(N*L)` search, we use the KMP algorithm. KMP can find all occurrences of a pattern of length `L` in a text of length `N` in `O(N+L)` time. We apply KMP twice: once for the horizontal (row-major) traversal and once for the vertical (column-major) traversal. We don't need to build the flattened strings explicitly; we can simulate access to them. The results are stored in two boolean arrays, `hStarts` and `vStarts`, indicating the starting positions of matches. **2. Efficient Marking with Sweep-line:** After finding all match start positions, simply iterating through each match to mark cells would revert to a `O(N*L)` worst-case complexity. To avoid this, we use a sweep-line algorithm. For the horizontal matches, we iterate through the `N` cells of the flattened grid, maintaining a counter for `activeMatches`. This counter tracks how many patterns are currently covering the cell being processed. If the counter is greater than zero, the cell is part of at least one match. This allows us to populate the `horizontalMatch` and `verticalMatch` grids in `O(N)` time each. Finally, with both `horizontalMatch` and `verticalMatch` grids populated, we count the overlapping cells in `O(N)` time. ```java class Solution { public int countMatchingCells(char[][] grid, String pattern) { int m = grid.length; int n = grid[0].length; int L = pattern.length(); int N = m * n; if (L > N) { return 0; } boolean[][] horizontalMatch = new boolean[m][n]; boolean[][] verticalMatch = new boolean[m][n]; // Find and mark horizontal matches boolean[] hStarts = findMatchStarts(m, n, L, pattern, true, grid); markCoveredCells(m, n, L, hStarts, horizontalMatch, true); // Find and mark vertical matches boolean[] vStarts = findMatchStarts(m, n, L, pattern, false, grid); markCoveredCells(m, n, L, vStarts, verticalMatch, false); // Count overlapping cells int count = 0; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (horizontalMatch[r][c] && verticalMatch[r][c]) { count++; } } } return count; } private boolean[] findMatchStarts(int m, int n, int L, String pattern, boolean isHorizontal, char[][] grid) { int N = m * n; boolean[] starts = new boolean[N]; if (L == 0) return starts; int[] lps = computeLPS(pattern); int j = 0; // pattern index for (int i = 0; i < N; i++) { // text index char textChar = isHorizontal ? grid[i / n][i % n] : grid[i % m][i / m]; while (j > 0 && pattern.charAt(j) != textChar) { j = lps[j - 1]; } if (pattern.charAt(j) == textChar) { j++; } if (j == L) { starts[i - L + 1] = true; j = lps[j - 1]; } } return starts; } private int[] computeLPS(String pattern) { int L = pattern.length(); if (L == 0) return new int[0]; int[] lps = new int[L]; int length = 0; int i = 1; while (i < L) { if (pattern.charAt(i) == pattern.charAt(length)) { length++; lps[i] = length; i++; } else { if (length != 0) { length = lps[length - 1]; } else { lps[i] = 0; i++; } } } return lps; } private void markCoveredCells(int m, int n, int L, boolean[] starts, boolean[][] matchGrid, boolean isHorizontal) { int N = m * n; int activeMatches = 0; for (int i = 0; i < N; i++) { if (i >= L && starts[i - L]) { activeMatches--; } if (starts[i]) { activeMatches++; } if (activeMatches > 0) { int r = isHorizontal ? i / n : i % m; int c = isHorizontal ? i % n : i / m; matchGrid[r][c] = true; } } } } ``` ### Algorithm * **KMP Pre-computation:** Compute the Longest Proper Prefix Suffix (LPS) array for the `pattern`. This takes `O(L)` time. * **Find Horizontal Match Starts:** * Use the KMP algorithm to search for the `pattern` in the row-major flattened grid. Instead of creating the flattened string, access characters on-the-fly via `grid[i/n][i%n]`. * Store the starting indices of all found matches in a boolean array `hStarts` of size `m*n`. This step takes `O(m*n)`. * **Mark Covered Horizontal Cells:** * Use a sweep-line algorithm to populate the `horizontalMatch` boolean matrix. * Initialize an `activeMatches` counter to 0. Iterate `i` from `0` to `m*n - 1`. * At each `i`, decrement `activeMatches` if a match that started at `i-L` has just ended. Increment `activeMatches` if a new match starts at `i`. * If `activeMatches > 0`, the cell `i` is covered, so mark `horizontalMatch[i/n][i%n]` as true. This takes `O(m*n)`. * **Find and Mark Vertical Matches:** Repeat the previous two steps for the vertical (column-major) traversal, using `grid[i%m][i/m]` for character access and populating a `verticalMatch` matrix. * **Final Count:** Iterate through the grid and count cells where `horizontalMatch[r][c]` and `verticalMatch[r][c]` are both true. This takes `O(m*n)`.