LeetCode Entry

2352. Equal Row and Column Pairs

13.06.2023 medium 2023 kotlin

Count of rowArray == colArray in an n x n matrix.

2352. Equal Row and Column Pairs medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/244

Problem TLDR

Count of rowArray == colArray in an n x n matrix.

Intuition

Compute hash function for each row and each col, then compare them. If hash(row) == hash(col), then compare arrays. For hashing, we can use simple 31 * prev + curr, that encodes both value and position.

Approach

  • For this Leetcode data, tan hash works perfectly, we can skip comparing the arrays.

Complexity

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(n)\)

Code


fun equalPairs(grid: Array<IntArray>): Int {
    val rowHashes = grid.map { it.fold(0.0) { r, t ->  Math.tan(r) + t } }
    val colHashes = (0..grid.lastIndex).map { x ->
        (0..grid.lastIndex).fold(0.0) { r, t -> Math.tan(r) + grid[t][x] } }
        return (0..grid.size * grid.size - 1).count {
            rowHashes[it / grid.size] == colHashes[it % grid.size]
        }
    }