DSA/MATRIX/BOOLEAN_MATRIX.PY at main · aditya-2703/DSA · GitHub

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
70
71
# INPUT
# 1 0 0
# 0 0 0
# 0 0 1
# MAKE ONE'S ROW AND COLUMN 1
# OUTPUT
# 1 1 1
# 1 0 1
# 1 1 1

def fill_row_col(row,col,matrix):
    for i in range(len(matrix)):
        if matrix[row][i]==0:
            matrix[row][i]=1
    for j in range(len(matrix)):
        if matrix[j][col]==0:
            matrix[j][col]=1

# METHOD 1 -- O(N^3) TIME AND O(N^N) SPACE COMPLEXITY (if n(row) == m(col))
def Method_1(matrix):
    newmatrix=[[0 for i in range(len(matrix))]for i in range(len(matrix))]
    for row in range(len(matrix)):
        for col in range(len(matrix)):
            if matrix[row][col]==1:
                fill_row_col(row,col,newmatrix)

    return newmatrix

def fill_row_col_min_one(row,col,matrix):
    for i in range(len(matrix)):
        if matrix[row][i]==0:
            matrix[row][i]=-1
    for j in range(len(matrix)):
        if matrix[j][col]==0:
            matrix[j][col]=-1

# METHOD 2 -- O(N^3) TIME AND O(1) SPACE COMPLEXITY
def Method_2(matrix):
    for row in range(len(matrix)):
        for col in range(len(matrix)):
            if matrix[row][col]==1:
                fill_row_col_min_one(row,col,matrix)
    for i in range(len(matrix)):
        for j in range(len(matrix)):
            if matrix[i][j]==-1:
                matrix[i][j]=1
    return matrix

# METHOD 3 -- O(N^2) TIME ANS O(N) SPACE COMPLEXITY
def Method_3(matrix):
    row=[0]*len(matrix)
    col=[0]*len(matrix[0])
    n=len(row)
    m=len(col)
    for i in range(n):
        for j in range(m):
            if matrix[i][j]==1:
                row[i]=1
                col[j]=1
    for i in range(n):
        for j in range(m):
            if row[i]==1 or col[j]==1:
                matrix[i][j]=1
    return matrix
if __name__ == '__main__':
    matrix=[[1,0,0],
            [0,0,1],
            [0,0,0]]
    mat=Method_3(matrix)
    for i in mat:
        print(i)