DSA Day 1

Data Structures and Algorithms are not something to be taken lightly, considering their importance from my experience in all my coding interviews. I have understood its very important to have a good understanding of these basics concepts

I am following the Striver SDE sheet for problems

Let's Start !!!

Arrays: Set Matrix Zeros 💤

Problem Courtesy: Leetcode ✨

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Initial Thoughts:

When I started to solve the problem, I was like whatttttt!!? why am I not able to think of anything? I was blank then I understood that this is what I have to change in myself. I took a notebook and started to write the approach in which I could solve the problem

First Approach: Big O(n^2)

So let's do it the basic way. Iterate through the matrix and if the matrix has an element zero just change all its neighboring rows and columns to zero. The code may seem big but it's very simple. let's take row value as the length of the array and the col value as the number of columns given as input

#brute force
def BFsetMatrix(arr):
    row = len(arr)
    col = len(arr[0])

the idea was to iterate whenever we face a 0 and iterate until we complete all rows and columns. Now let's change the values to -1, I initially kept it to a dummy variable but then when I looked up in the solution I understood what Striver meant to keep -1, For not affecting the existing values of the rows and columns

#Double for loop for iterating over input
    for i in range(row):
        for j in range(col):
            if (arr[i][j] == 0):
                ind = i-1
                #convert all rows to -1
                while(ind >= 0):
                    if(arr[ind][j] != 0):
                        arr[ind][j] = -1
                    ind -=1
                    print(ind)
                ind = i+1
                #convert all cols to -1
                while(ind < row):
                    if(arr[ind][j] != 0):
                        arr[ind][j] = -1
                    ind +=1
                ind = j-1
                #same as the above iterations
                while(ind >= 0):
                    if(arr[i][ind] != 0):
                        arr[i][ind] = -1
                    ind -=1
                ind = j+1
                while(ind < row):
                    if(arr[i][ind] != 0):
                        arr[i][ind] = -1
                    ind +=1
    for i in range(row):
        for j in range(col):
            if (arr[i][j] <= 0):
                #Change all the values marked as -1 to 0
                arr[i][j] = 0
                #Resultant matrix is the required answer
    Time complexity = O(n^2)
    Space complexity = O(1)

now, that's brute force.

Optimal Code

def setZeroes(self, matrix: List[List[int]]) -> None:
        R=[]
        C=[]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==0:
                    R.append(i)
                    C.append(j)

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i in R or j in C:
                    matrix[i][j]=0
        return matrix

Thus giving the solution in O(N) time complexity