Count Cells in Overlapping Horizontal and Vertical Substrings solution and explanation
Google
4 more videos on this problem
Leetcode 3529 | Count Cells in Overlapping Horizontal and Vertical Substrings | Biweekly Contest 155Road To FAANG · 18:44 · 408 views
3529. Count Cells in Overlapping Horizontal and Vertical SubstringsTech Courses · 14:42 · 288 views
Count Cells in Overlapping Horizontal and Vertical Substrings (Leetcode Biweekly 155)Soumya Bhattacharjee · 15:04 · 211 views
3529. Count Cells in Overlapping Horizontal and Vertical Substrings (Leetcode Medium)Programming Live with Larry · 15:09 · 162 views
3529. Count Cells in Overlapping Horizontal and Vertical SubstringsAmit Choraria · 43:35 · 74 views
The 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:
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.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 1051 <= pattern.length <= m * ngridandpatternconsist of only lowercase English letters.
Approach overview
Problem Overview: You are given a character matrix and two target strings. One string must appear horizontally in rows and the other vertically in columns. The goal is to count how many cells belong to both a valid horizontal substring match and a vertical substring match at the same time.
Approach 1: Brute Force Substring Scanning (O(m * n * k) time, O(m * n) space)
Iterate through every row and check every possible starting position where the horizontal string could fit. Compare characters one by one to confirm the substring. Mark each cell that belongs to a successful horizontal match. Repeat the same process for columns to detect vertical matches. Maintain two boolean matrices to track marked cells, then count positions where both matrices are true. This approach is straightforward but expensive because each candidate substring requires a full character comparison.
Approach 2: Rolling Hash String Matching (O(m * n) time, O(m * n) space)
Use a rolling hash (Rabin–Karp style) to detect substring matches efficiently across rows and columns. Precompute the hash of the horizontal and vertical target strings. For each row, maintain a sliding hash window of length k and update it in constant time as the window moves. When the hash matches the target hash, verify the substring and mark the cells involved. Repeat the same sliding window technique for each column to detect vertical matches. Finally, scan the grid and count cells marked by both passes.
The key insight is that rolling hash removes repeated character comparisons. Instead of checking k characters at every position, the algorithm updates the hash in O(1) time while sliding across the grid. This reduces the total work from substring-by-substring comparisons to linear scans over the matrix.
Implementation relies on concepts from string processing, rolling hash, and matrix traversal. The grid is scanned twice: once row-wise and once column-wise. A boolean matrix records cells participating in horizontal matches, another for vertical matches.
Recommended for interviews: The rolling hash approach is the expected solution. Brute force demonstrates baseline understanding of substring search, but interviewers typically look for the optimized string matching strategy that reduces repeated comparisons and achieves near O(mn) runtime.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Scan | O(m * n * k) | O(m * n) | Good for small grids or when implementing the simplest correct solution |
| Rolling Hash (Rabin–Karp) | O(m * n) | O(m * n) | Preferred for large matrices and interview settings where efficient substring matching is required |
Frequently asked questions
Is Count Cells in Overlapping Horizontal and Vertical Substrings easy or hard?
The problem is rated Medium because it combines multiple concepts: grid traversal, substring detection, and efficient hashing. The brute force idea is simple, but implementing an optimized rolling hash solution requires understanding sliding window hashing and careful indexing.
Count Cells in Overlapping Horizontal and Vertical Substrings Python/Java solution
Typical implementations compute rolling hashes for the target strings and slide a window across every row and column. When a match occurs, the cells covered by the substring are marked. Python, Java, C++, and Go implementations follow the same logic with minor differences in hash arithmetic and array handling.
How to solve Count Cells in Overlapping Horizontal and Vertical Substrings in O(n)?
Treat each row and column as a string and apply a rolling hash sliding window equal to the target substring length. Update the hash in constant time as the window moves. When hashes match, verify the substring and mark the cells. Two passes over the matrix allow counting cells that belong to both match sets.
What is the best approach for Count Cells in Overlapping Horizontal and Vertical Substrings?
The rolling hash (Rabin–Karp) approach is the most efficient method. It scans each row and column using a sliding window hash to detect substring matches in O(1) time per shift. This reduces the total complexity to O(mn) while marking cells that belong to horizontal and vertical matches.
Is Count Cells in Overlapping Horizontal and Vertical Substrings asked at Google/Amazon/Meta?
Problems combining matrix traversal with string matching appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often require detecting patterns in rows and columns or combining grid traversal with hashing or substring search techniques.
What data structure is used in Count Cells in Overlapping Horizontal and Vertical Substrings?
The solution primarily uses arrays and matrices to represent the grid and track matched cells. Rolling hash values are computed while sliding across rows and columns, which falls under string matching and hash function techniques.
What is the time complexity of Count Cells in Overlapping Horizontal and Vertical Substrings?
The optimized solution runs in O(m * n) time where m and n are the grid dimensions. Each row and column is scanned once using a rolling hash window. Space complexity is O(m * n) to track cells that participate in horizontal and vertical matches.