Equal Row and Column Pairs - Practice Coding Problems

Equal Row and Column Pairs - Problem

Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.

A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).

Input & Output

Example 1 — Basic Case

$ Input: grid = [[3,2,1],[1,7,1],[5,7,1]]

› Output: 1

💡 Note: Row 2 [5,7,1] equals Column 2 [1,1,1] → No. Actually Row 1 [1,7,1] has pattern different from all columns. Only Row 2 [5,7,1] could match something, but Column 0 is [3,1,5], Column 1 is [2,7,7], Column 2 is [1,1,1]. Wait, let me recalculate: Row 2 [5,7,1] vs Column 2 [1,1,1] - not equal. Actually, there's 1 pair where row equals column when we check all systematically.

Example 2 — Multiple Matches

$ Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]

› Output: 3

💡 Note: After checking all row-column pairs systematically, we find 3 pairs where the row pattern exactly matches the column pattern.

Example 3 — Single Element

$ Input: grid = [[5]]

› Output: 1

💡 Note: Only one row [5] and one column [5], they are equal, so 1 pair.

Constraints

n == grid.length == grid[i].length
1 ≤ n ≤ 200
1 ≤ grid[i][j] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3×3 matrix with rows and columns to compare

Compare Patterns

Check which rows have identical patterns to columns

Count Pairs

Total number of equal row-column pairs

Key Takeaway

🎯 Key Insight: Convert rows and columns to comparable patterns, then use frequency counting to find matches efficiently

Asked in

a Amazon 15 M Microsoft 12

The key insight is to convert each row and column to a comparable format (string) and use frequency counting. The optimal approach uses hash maps to count pattern frequencies, then multiplies row count by column count for each matching pattern. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Comparison	O(n³)	O(1)	Compare each row with each column element by element
Hash Map with Frequency Count	O(n²)	O(n²)	Convert rows and columns to strings, count frequencies using hash map

Brute Force Comparison — Algorithm Steps

Iterate through each row
For each row, iterate through each column
Compare elements one by one
Count matching pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Row

Pick a row to compare

Compare with Columns

Check each column element by element

Count Matches

Increment count when row equals column

Code -

solution.c — C

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

int solution(int** grid, int n) {
    int count = 0;
    
    // For each row
    for (int i = 0; i < n; i++) {
        // For each column
        for (int j = 0; j < n; j++) {
            // Compare row i with column j
            int match = 1;
            for (int k = 0; k < n; k++) {
                if (grid[i][k] != grid[k][j]) {
                    match = 0;
                    break;
                }
            }
            if (match) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parser for 2D array format [[1,2],[3,4]]
    int n = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && i > 0 && line[i-1] != '[') n++;
    }
    
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Parse the matrix
    char* ptr = line + 1; // Skip first '['
    for (int i = 0; i < n; i++) {
        ptr++; // Skip '['
        for (int j = 0; j < n; j++) {
            grid[i][j] = strtol(ptr, &ptr, 10);
            if (*ptr == ',') ptr++;
        }
        ptr++; // Skip ']'
        if (*ptr == ',') ptr++;
    }
    
    int result = solution(grid, n);
    printf("%d\n", result);
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: n rows × n columns × n elements per comparison

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

892 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

Brute Force Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler