FilesExpand file tree

master

/

set-matrix-zeroes.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

44 lines (38 loc) · 1.47 KB

master

/

set-matrix-zeroes.py

Copy path

Top

File metadata and controls

• Code
• Blame

44 lines (38 loc) · 1.47 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

# Time: O(m * n)

# Space: O(1)

#

# Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

#

# Follow up:

# Did you use extra space?

# A straight forward solution using O(mn) space is probably a bad idea.

# A simple improvement uses O(m + n) space, but still not the best solution.

# Could you devise a constant space solution?

#

class Solution:

# @param matrix, a list of lists of integers

# RETURN NOTHING, MODIFY matrix IN PLACE.

def setZeroes(self, matrix):

first_col = reduce(lambda acc, i: acc or matrix[i][0] == 0, xrange(len(matrix)), False)

first_row = reduce(lambda acc, j: acc or matrix[0][j] == 0, xrange(len(matrix[0])), False)

for i in xrange(1, len(matrix)):

for j in xrange(1, len(matrix[0])):

if matrix[i][j] == 0:

matrix[i][0], matrix[0][j] = 0, 0

for i in xrange(1, len(matrix)):

for j in xrange(1, len(matrix[0])):

if matrix[i][0] == 0 or matrix[0][j] == 0:

matrix[i][j] = 0

if first_col:

for i in xrange(len(matrix)):

matrix[i][0] = 0

if first_row:

for j in xrange(len(matrix[0])):

matrix[0][j] = 0

if __name__ == "__main__":

matrix = [ [1, 0, 1, 1]

, [1, 1, 0, 1]

, [1, 1, 1, 0]

, [1, 1, 1, 1]]

Solution().setZeroes(matrix)

print matrix