What is the time complexity of LeetCode 2482. Difference Between Ones and Zeros in Row and Column?

The Python solution on this page runs in O(m \times n), and if we ignore the space used by the answer, the space complexity is O(m + n).

What is the space complexity of LeetCode 2482. Difference Between Ones and Zeros in Row and Column?

The Python solution on this page uses O(m + n) auxiliary space.

Difference Between Ones and Zeros in Row and Column — LeetCode 2482 Python Solution

MediumArrayMatrixSimulation

Problem: #2482
Pattern: Matrix and Grid
Reading time: 3 min
Source: leetcode.com

The problem

You are given a 0-indexed m x n binary matrix grid. A 0-indexed m x n difference matrix diff is created with the following procedure: Let the number of ones in the ith row be onesRowi.

Example

Input: grid = [[0,1,1],[1,0,1],[0,0,1]]
Output: [[0,0,4],[0,0,4],[-2,-2,2]]
Explanation: - diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 2 + 1 - 1 - 2 = 0

Python solution

Python

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        rows = [0] * m
        cols = [0] * n
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                rows[i] += v
                cols[j] += v
        diff = [[0] * n for _ in range(m)]
        for i, r in enumerate(rows):
            for j, c in enumerate(cols):
                diff[i][j] = r + c - (n - r) - (m - c)
        return diff

Complexity

Measure	Complexity
Time	O(m \times n), and if we ignore the space used by the answer, the space complexity is O(m + n)
Space	O(m + n) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 2482. Difference Between Ones and Zeros in Row and Column is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2482. Difference Between Ones and Zeros in Row and Column?: LeetCode 2482. Difference Between Ones and Zeros in Row and Column is rated Medium on LeetCode.
What is the time complexity of LeetCode 2482. Difference Between Ones and Zeros in Row and Column?: The Python solution on this page runs in O(m \times n), and if we ignore the space used by the answer, the space complexity is O(m + n).
What is the space complexity of LeetCode 2482. Difference Between Ones and Zeros in Row and Column?: The Python solution on this page uses O(m + n) auxiliary space.
What topics does LeetCode 2482. Difference Between Ones and Zeros in Row and Column cover?: LeetCode 2482. Difference Between Ones and Zeros in Row and Column is tagged Array, Matrix and Simulation on LeetCode.