LeetCode #3529 — MEDIUM

Count Cells in Overlapping Horizontal and Vertical Substrings

Move from brute-force thinking to an efficient approach using array strategy.

Solve on LeetCode
The Problem

Problem Statement

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.
Patterns Used
🔎String Matching→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · String Matching

Example 1

[["a","a","c","c"],["b","b","b","c"],["a","a","b","a"],["c","a","a","c"],["a","a","b","a"]]
"abaca"

Example 2

[["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]]
"aba"

Example 3

[["a"]]
"a"
Step 02

Core Insight

What unlocks the optimal approach

  • Use a string hashing or pattern matching algorithm to efficiently find all horizontal and vertical occurrences of the pattern in the grid.
  • Track the positions of each match and count only the cells that appear in both horizontal and vertical matches.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Upper-end input sizes
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3529: Count Cells in Overlapping Horizontal and Vertical Substrings
class Solution {
  public int countCells(char[][] grid, String pattern) {
    final int m = grid.length;
    final int n = grid[0].length;
    int ans = 0;
    StringBuilder flattenedGridRow = new StringBuilder();
    StringBuilder flattenedGridCol = new StringBuilder();

    // Flatten the grid for horizontal matching.
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        flattenedGridRow.append(grid[i][j]);

    // Flatten the grid for vertical matching.
    for (int j = 0; j < n; ++j)
      for (int i = 0; i < m; ++i)
        flattenedGridCol.append(grid[i][j]);

    // Find matching positions.
    boolean[][] horizontalMatches =
        markMatchedCells(flattenedGridRow.toString(), pattern, m, n, true);
    boolean[][] verticalMatches =
        markMatchedCells(flattenedGridCol.toString(), pattern, m, n, false);

    // Count overlapping match positions.
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (horizontalMatches[i][j] && verticalMatches[i][j])
          ++ans;

    return ans;
  }

  private static final long BASE = 13;
  private static final long HASH = 1_000_000_007;

  private boolean[][] markMatchedCells(final String flattenedGrid, final String pattern, int m,
                                       int n, boolean isHorizontal) {
    boolean[][] matchMatrix = new boolean[m][n];
    int[] matchPrefix = new int[flattenedGrid.length() + 1];
    long[] pows = new long[pattern.length()]; // pows[i] := BASE^i % HASH
    pows[0] = 1;
    long patternHash = 0;
    long runningHash = 0;

    for (int i = 1; i < pattern.length(); ++i)
      pows[i] = (pows[i - 1] * BASE) % HASH;

    for (final char c : pattern.toCharArray())
      patternHash = (patternHash * BASE + (c - 'a')) % HASH;

    for (int i = 0; i < flattenedGrid.length(); ++i) {
      runningHash = (runningHash * BASE + (flattenedGrid.charAt(i) - 'a')) % HASH;
      if (i >= pattern.length() - 1) {
        if (runningHash == patternHash) { // Match found.
          ++matchPrefix[i - pattern.length() + 1];
          --matchPrefix[i + 1];
        }
        // Remove the contribution of the oldest letter.
        final long oldestLetterHash =
            (pows[pattern.length() - 1] * (flattenedGrid.charAt(i - pattern.length() + 1) - 'a')) %
            HASH;
        runningHash = (runningHash - oldestLetterHash + HASH) % HASH;
      }
    }

    for (int k = 0; k < flattenedGrid.length(); ++k) {
      matchPrefix[k] += (k > 0) ? matchPrefix[k - 1] : 0;
      if (matchPrefix[k] > 0) {
        final int i = isHorizontal ? k / n : k % m;
        final int j = isHorizontal ? k % n : k / m;
        matchMatrix[i][j] = true;
      }
    }

    return matchMatrix;
  }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(n + m)
Space
O(m)

Approach Breakdown

BRUTE FORCE
O(n × m) time
O(1) space

At each of the n starting positions in the text, compare up to m characters with the pattern. If a mismatch occurs, shift by one and restart. Worst case (e.g., searching "aab" in "aaaa...a") checks m characters at nearly every position: O(n × m).

KMP / Z-ALGO
O(n + m) time
O(m) space

KMP and Z-algorithm preprocess the pattern in O(m) to build a failure/Z-array, then scan the text in O(n) — never backtracking. Total: O(n + m). Rabin-Karp uses rolling hashes for O(n + m) expected time. All beat the O(n × m) brute force of checking every position.

Shortcut: Preprocessing avoids backtracking → O(n + m). The failure function is the key insight.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Related Problems
#1023Camelcase Matchingmedium→#1408String Matching in an Arrayeasy→#1764Form Array by Concatenating Subarrays of Another Arraymedium→#2185Counting Words With a Given Prefixeasy→#2301Match Substring After Replacementhard→