Count Cells in Overlapping Horizontal and Vertical Substrings

Count Cells in Overlapping Horizontal and Vertical Substrings - 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.

Input & Output

Example 1 — Basic Pattern Match

$ Input: grid = [["a","b"],["b","a"]], pattern = "ab"

› Output: 1

💡 Note: Horizontal "ab" at (0,0)→(0,1) and vertical "ab" at (0,0)→(1,0). Cell (0,0) is in both patterns.

Example 2 — No Overlap

$ Input: grid = [["a","b"],["c","d"]], pattern = "ab"

› Output: 0

💡 Note: Horizontal "ab" exists at (0,0)→(0,1) but no vertical "ab" pattern, so no overlapping cells.

Example 3 — Multiple Overlaps

$ Input: grid = [["x","y"],["x","y"]], pattern = "xy"

› Output: 2

💡 Note: Both rows contain "xy" horizontally, both columns contain "xy" vertically. Cells (0,0) and (0,1) are in both.

Constraints

1 ≤ m, n ≤ 10³
1 ≤ pattern.length ≤ 10³
grid[i][j] and pattern consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Matrix grid and pattern string to find

Process

Find horizontal and vertical pattern matches

Output

Count cells in both horizontal and vertical matches

Key Takeaway

🎯 Key Insight: Count cells that are part of BOTH horizontal and vertical pattern occurrences

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to find cells that participate in both horizontal and vertical pattern matches. Best approach uses two-pass scanning with hash sets for O(m·n·k) time and efficient set intersection. Time: O(m·n·k), Space: O(m·n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Two-Pass with Sets	O(m·n·k)	O(m·n)	Use hash sets to efficiently track and intersect horizontal and vertical matches
Brute Force - Check All Positions	O(m·n·k²)	O(m·n)	For each cell, check if it's part of both horizontal and vertical pattern matches

Optimized - Two-Pass with Sets — Algorithm Steps

Build horizontal pattern matches using linear scanning
Build vertical pattern matches using linear scanning
Use set intersection to count overlapping cells efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Validate & Collect

Check pattern validity before collecting cells

Set Operations

Use hash set intersection for fast overlap detection

Efficient Count

O(1) lookup time per cell

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

int canFormHorizontalPattern(char grid[][MAX_SIZE], int startI, int startJ, char* pattern, int m, int n) {
    int k = strlen(pattern);
    int row = startI, col = startJ;
    
    for (int pos = 0; pos < k; pos++) {
        if (row >= m || grid[row][col] != pattern[pos]) {
            return 0;
        }
        col++;
        if (col == n) {
            col = 0;
            row++;
        }
    }
    return 1;
}

int canFormVerticalPattern(char grid[][MAX_SIZE], int startI, int startJ, char* pattern, int m, int n) {
    int k = strlen(pattern);
    int row = startI, col = startJ;
    
    for (int pos = 0; pos < k; pos++) {
        if (col >= n || grid[row][col] != pattern[pos]) {
            return 0;
        }
        row++;
        if (row == m) {
            row = 0;
            col++;
        }
    }
    return 1;
}

int solution(char grid[][MAX_SIZE], int m, int n, char* pattern) {
    int k = strlen(pattern);
    if (k == 0) return 0;
    
    char horizontalCells[MAX_SIZE*MAX_SIZE][20];
    char verticalCells[MAX_SIZE*MAX_SIZE][20];
    int hCount = 0, vCount = 0;
    
    // Optimized horizontal scanning
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (canFormHorizontalPattern(grid, i, j, pattern, m, n)) {
                int row = i, col = j;
                for (int pos = 0; pos < k; pos++) {
                    sprintf(horizontalCells[hCount++], "%d,%d", row, col);
                    col++;
                    if (col == n) {
                        col = 0;
                        row++;
                        if (row == m) break;
                    }
                }
            }
        }
    }
    
    // Optimized vertical scanning
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m; i++) {
            if (canFormVerticalPattern(grid, i, j, pattern, m, n)) {
                int row = i, col = j;
                for (int pos = 0; pos < k; pos++) {
                    sprintf(verticalCells[vCount++], "%d,%d", row, col);
                    row++;
                    if (row == m) {
                        row = 0;
                        col++;
                        if (col == n) break;
                    }
                }
            }
        }
    }
    
    int count = 0;
    for (int i = 0; i < hCount; i++) {
        for (int j = 0; j < vCount; j++) {
            if (strcmp(horizontalCells[i], verticalCells[j]) == 0) {
                count++;
                break;
            }
        }
    }
    return count;
}

int main() {
    char grid[MAX_SIZE][MAX_SIZE];
    char pattern[MAX_SIZE];
    int m = 3, n = 3;
    
    fgets(pattern, sizeof(pattern), stdin);
    pattern[strcspn(pattern, "\n")] = 0;
    
    int result = solution(grid, m, n, pattern);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m·n·k)

Linear scan for each direction, k operations per starting position

✓ Linear Growth

Space Complexity

O(m·n)

Hash sets store at most m·n cell coordinates

⚡ Linearithmic Space

12.8K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Two-Pass with Sets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler