FilesExpand file tree

 master

/

073_SetMatrixZeroes73.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

69 lines (62 loc) · 2.01 KB

 master

/

073_SetMatrixZeroes73.java

Copy path

Top

File metadata and controls

• Code
• Blame

69 lines (62 loc) · 2.01 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

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

/**

* 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?

*/

public class SetMatrixZeroes73 {

public void setZeroes(int[][] matrix) {

boolean[] rows = new boolean[matrix.length];

boolean[] cols = new boolean[matrix[0].length];

for (int i=0; i<matrix.length; i++) {

for (int j=0; j<matrix[0].length; j++) {

if (matrix[i][j] == 0) {

rows[i] = true;

cols[j] = true;

}

}

}

for (int i=0; i<matrix.length; i++) {

for (int j=0; j<matrix[0].length; j++) {

if (rows[i] || cols[j]) matrix[i][j] = 0;

}

}

}

/**

* https://leetcode.com/problems/set-matrix-zeroes/discuss/26008/My-AC-java-O(1)-solution-(easy-to-read)

*/

public void setZeroes2(int[][] matrix) {

boolean fr = false,fc = false;

for(int i = 0; i < matrix.length; i++) {

for(int j = 0; j < matrix[0].length; j++) {

if(matrix[i][j] == 0) {

if(i == 0) fr = true;

if(j == 0) fc = true;

matrix[0][j] = 0;

matrix[i][0] = 0;

}

}

}

for(int i = 1; i < matrix.length; i++) {

for(int j = 1; j < matrix[0].length; j++) {

if(matrix[i][0] == 0 || matrix[0][j] == 0) {

matrix[i][j] = 0;

}

}

}

if(fr) {

for(int j = 0; j < matrix[0].length; j++) {

matrix[0][j] = 0;

}

}

if(fc) {

for(int i = 0; i < matrix.length; i++) {

matrix[i][0] = 0;

}

}

}

}