Scale Engineer

Count Cells in Overlapping Horizontal and Vertical Substrings

Med
#3140Time: 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.
Patterns
String MatchingRolling HashHash Function
Data structures
ArrayStringMatrix

Prompt

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:

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:

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem