Problem Overview
LeetCode 2352 gives you an n x n integer matrix and asks you to count the number of pairs (r, c) such that row r and column c are equal as sequences. Two sequences are equal if every element at every position matches — so row r[0], r[1], ..., r[n-1] must equal column c[0], c[1], ..., c[n-1] in the same order.
The return value is an integer count of all such valid pairs. Note that multiple rows can equal the same column and one row can equal multiple columns, so you must count every matching (row, column) combination — not just distinct ones.
Understanding the constraints helps frame the solution. The matrix is always square (n x n), so rows and columns have the same length, making direct comparison meaningful.
- n x n integer matrix — rows and columns always have equal length
- 1 <= n <= 200 — small enough for O(n^2) or O(n^3) but O(n^2) is preferred
- 1 <= grid[i][j] <= 10^5 — positive integers, no negative edge cases
- Count every (r, c) pair where row r equals column c as a sequence
- The same row may match multiple columns and vice versa — all pairs count
Brute Force
The naive approach iterates over every possible (row, column) pair. For each of the n rows and n columns, you extract the column as a list and compare element by element with the row. A single comparison takes O(n) time, and there are n^2 pairs, yielding O(n^3) overall — correct but slow for large n.
For n=200, that is 200^3 = 8 million operations — manageable, but there is a much cleaner approach. The key observation is that many rows may be identical, and you are repeating the same comparisons unnecessarily.
To cut from O(n^3) to O(n^2), precompute the row frequency map once and then look up each column tuple in constant time. This avoids redundant element-by-element comparisons.
Hash Each Row as a Tuple
Store row frequencies in a map (tuple → count), then check each column as a tuple against the map. A single dictionary lookup replaces an O(n) element-by-element comparison, reducing O(n^3) to O(n^2) with minimal code.
Row Hashing
The first pass converts every row into a hashable tuple and records its frequency. In Python, a list is not hashable but a tuple is, so convert each row with tuple(row). Use a Counter (or defaultdict) mapping tuple → count. If two rows are identical their tuples are equal, and the count increments automatically.
In Java, int arrays do not have content-based hashCode, so you must use a different key. The simplest approach is Arrays.toString(row), which produces a canonical string like "[3, 2, 1]" that serves as a reliable HashMap key.
After this pass the map contains every distinct row pattern and how many times it appears in the grid. Duplicate rows are handled correctly — their frequency is simply greater than one.
- 1Initialize an empty Counter / HashMap for row frequencies
- 2For each row index i from 0 to n-1, extract grid[i] as a tuple
- 3Increment row_map[tuple(grid[i])] by 1
- 4After the loop, row_map holds every distinct row pattern and its occurrence count
- 5Duplicate rows are naturally counted — their tuple key appears multiple times
Column Matching
The second pass builds each column as a tuple and looks it up in the row frequency map. For column j, read elements grid[0][j], grid[1][j], ..., grid[n-1][j] in order to form the column tuple. If that tuple exists in the row map, add its count to the result.
Adding the count (not just 1) handles the case where multiple identical rows each match the same column. If three rows are all equal to column j, the pair count increases by three.
After iterating all n columns the accumulated result is the final answer. The total work is O(n) to build each column tuple times n columns = O(n^2), and each map lookup is O(n) for hashing the tuple — giving O(n^2) overall.
Tuples as HashMap Keys
Tuples are hashable in Python, making them perfect for Counter keys with no extra conversion. In Java, convert to a String with Arrays.toString(row) or join elements with a delimiter — this gives a content-based key since Java int[] arrays do not override hashCode.
Walk-Through Example
Take grid = [[3,2,1],[1,7,6],[2,7,7]]. First pass: row 0 → tuple (3,2,1), row 1 → (1,7,6), row 2 → (2,7,7). All three rows are distinct, so row_map = {(3,2,1):1, (1,7,6):1, (2,7,7):1}.
Second pass builds column tuples. Column 0: grid[0][0]=3, grid[1][0]=1, grid[2][0]=2 → tuple (3,1,2). Column 1: 2,7,7 → (2,7,7). Column 2: 1,6,7 → (1,6,7). Look up each column in row_map.
Column 0 → (3,1,2): not in row_map, add 0. Column 1 → (2,7,7): found with count 1, add 1. Column 2 → (1,6,7): not in row_map, add 0. Final result = 1. The matching pair is (row 2, column 1) since both equal [2,7,7].
- 1Row pass: (3,2,1)→1, (1,7,6)→1, (2,7,7)→1 in row_map
- 2Col 0 tuple: (3,1,2) — not in row_map → +0
- 3Col 1 tuple: (2,7,7) — found, count=1 → +1
- 4Col 2 tuple: (1,6,7) — not in row_map → +0
- 5Result = 1: pair (row 2, col 1) both equal [2,7,7]
Code Walkthrough: Python and Java
In Python, Counter(map(tuple, grid)) builds the entire row frequency map in one line. For columns, zip(*grid) unpacks the grid into column iterables, so Counter(map(tuple, zip(*grid))) similarly builds a column frequency map. The answer is then sum(row_map[k] * col_map[k] for k in row_map if k in col_map) — a concise dot-product over matching keys.
A more explicit Python loop: initialize result=0, build row_map with Counter, then for j in range(n) build col_tuple = tuple(grid[i][j] for i in range(n)) and add row_map.get(col_tuple, 0) to result. This two-pass loop is O(n^2) time and O(n^2) space for the map.
In Java, use a HashMap<String, Integer>. For rows: String key = Arrays.toString(grid[i]); map.merge(key, 1, Integer::sum). For columns: build int[] col = new int[n]; for each i set col[i] = grid[i][j]; then String colKey = Arrays.toString(col); result += map.getOrDefault(colKey, 0).
Java int[] hashCode Pitfall
In Java, use Arrays.toString(row) as the HashMap key since int[] does not override hashCode or equals — two arrays with identical contents will not be equal under ==. Alternatively, join elements with a delimiter string or use a List<Integer> which does implement content-based equals and hashCode.