Desc

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.
• Let the number of ones in the jth column be onesColj.
• Let the number of zeros in the ith row be zerosRowi.
• Let the number of zeros in the jth column be zerosColj.
• diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj

Return the difference matrix diff.

 

Example 1:

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 
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[2][0] = onesRow2 + onesCol0 - zerosRow2 - zerosCol0 = 1 + 1 - 2 - 2 = -2
- diff[2][1] = onesRow2 + onesCol1 - zerosRow2 - zerosCol1 = 1 + 1 - 2 - 2 = -2
- diff[2][2] = onesRow2 + onesCol2 - zerosRow2 - zerosCol2 = 1 + 3 - 2 - 0 = 2

Example 2:

Input: grid = [[1,1,1],[1,1,1]]
Output: [[5,5,5],[5,5,5]]
Explanation:
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• grid[i][j] is either 0 or 1.

Code

Success - Ref

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        n, m = len(grid), len(grid[0])
        diff = [[0] * m for _ in range(n)]
        row, col = [0] * n, [0] * m
        
        for i in range(n):
            for j in range(m):
                row[i] += grid[i][j]
                col[j] += grid[i][j]
        
        for i in range(n):
            for j in range(m):
                diff[i][j] = row[i] + col[j] - (n - row[i]) - (m - col[j])

        return diff

Failed

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        n, m = len(grid), len(grid[0])
        diff = [[0] * m for _ in range(n)]
        
        for i in range(n):
            for j in range(m):
                diff[i][j] = grid[i].count(1) - grid[i].count(0) + list(zip(*grid))[j].count(1) - list(zip(*grid))[j].count(0)
        
        return diff

파이썬의 count() 메소드는 $O(N)$의 시간복잡도를 갖는다.
위의 코드의 총 시간복잡도를 구해보면 $O(N * M * (N + M))$ 이므로
결과적으로 $O(N^2M + NM^2)$이다.

문제의 조건에서 $1 <= m * n <= 10^5$ 이므로, TLE가 발생한다.

Code Desc

count를 사용하지 않은 다른 사람의 풀이를 참고했다.

row : 특정 행의 1의 개수를 저장하는 리스트
col : 특정 열의 1의 개수를 저장하는 리스트
n - row[i] : 특정 행의 0의 개수
m - col[i] : 특정 열의 0의 개수

먼저, 각 행과 열의 1의 개수를 모두 구해서 리스트에 저장한다.

그 다음으로, 각 행과 열의 0의 개수를 구하기 전에, 문제의 조건을 살펴보자

grid 가 가질 수 있는 값은 0과 1 둘 뿐이다.
그 말은 각 행과 열의 길이에서 1의 개수 를 빼면 0의 개수 를 구할 수 있다는 말과 같다.

문제의 조건에서 diff[i][j] 의 값은,
(각 행의 1의 개수 - 0의 개수) + (각 열의 1의 개수 - 0의 개수) 이다.

따라서, 위에서 구한 값들을 조건에 맞게 더해서 diff[i][j] 에 저장한다.