This content originally appeared on DEV Community and was authored by Nayan Pahuja
Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-2.The goal is simple. I will solve one or more than one leetcode/gfg problem a day and post what I learnt. I am confident that this will help me improve my concepts and help me be more consistent in my practice. Looking forward to a positive interaction with all of you.
DAY-2 PROBLEM 1
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.
Example:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Intuition:
On the first look , The question seems pretty straightforward. For every 0 in the original matrix at their place, set their rows and columns to 0.
The brute force approach would be to make a copy of matrix. Then traverse the original matrix and for every 0's index. We change the rows and columns of the new matrix we made. But that would take O(m*n) space but the question and constraints demand us to solve the problem in less space than this. So we are going to have to look at another approach.
An approach I thought initially is to make a vector of pair to store the indexes of 0's and then make changes in the original vector.
Let's understand by looking at the example:
- We first using two for loops, traverse the whole matrix.
- We find a 0 at {1,1} so we store it in our vector.
- Now that we have the indexes of all 0's in the original matrix, we traverse the vector to set rows and columns 0.
Code:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
vector<pair<int,int>> vec; //stores indexes of all 0's
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
{
if(matrix[i][j] == 0)
{
vec.push_back({i,j});
}
}
}
for(int k = 0; k < vec.size(); k++)
{
for(int l = 0; l < matrix[0].size(); l++)
{
matrix[vec[k].first][l] = 0;
}
for(int l = 0; l < matrix.size(); l++)
{
matrix[l][vec[k].second] = 0;
}
}
}
};
Time Complexity: O(m*n)
Worst Case Space Complexity: O(n)**
Although this approach is good, We can give it a tweak to do it in place and yet not compromise any time complexity.
Optimal Solution:
For the optimal solution,
We are going to assume the top row and leftmost column as the dummy arrays for rows and columns index. Just like we stored the index in the past, we will just be changing the rows and cols index of the dummy array to 0.
Here is the optimized code:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int colFlag = 1;
int rows = matrix.size();
int cols = matrix[0].size();
for(int i = 0; i < rows; i++)
{
for(int j =0; j < cols; j++)
{
if(matrix[i][j] == 0)
{
matrix[i][0] = 0;
if( j != 0)
{
matrix[0][j] = 0;
}
else
{
colFlag = 0;
}
}
}
}
for(int i = 1; i < rows; i++)
{
for(int j = 1; j< cols; j++)
{
if(matrix[i][0] == 0 || matrix[0][j] == 0)
{
matrix[i][j] =0;
}
}
}
if (matrix[0][0] == 0) {
for (int j = 0; j < cols; j++)
{
matrix[0][j] = 0;
}
}
if (colFlag == 0) {
for (int i = 0; i < rows; i++) {
matrix[i][0] = 0;
}
}
}
};
I will be providing a detailed explanation of this soon.
This content originally appeared on DEV Community and was authored by Nayan Pahuja
Nayan Pahuja | Sciencx (2023-06-05T16:26:51+00:00) 100 DAYS- DAY 2. Retrieved from https://www.scien.cx/2023/06/05/100-days-day-2/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.