Prepin
Log in

Given a matrix named arr with dimensions M x N, the objective is to set all the rows and columns to zero if any specific element is zero, ensuring that the operation is performed with constant space complexity.

Approach / Explanation

In this task, you are presented with a matrix, which is essentially a 2-dimensional array or a list of lists (in Python), consisting of 'M' rows and 'N' columns. The objective is to create a solution that sets all elements in the row and column of any element that is zero to zero as well. Moreover, there is a limitation concerning space usage. The solution must have constant space complexity, meaning you cannot utilize any additional data structures like lists, sets, or other array types. To tackle this problem, consider the following important points: Have a clear understanding of how to navigate through a matrix, specifically how to interact with its rows and columns. Monitor each cell that contains a zero, along with its associated row and column. **

Suggested Answer

** One potential method is to utilize the first row and the first column of the matrix as indicators. Below is a step-by-step guide to accomplish this: First, determine whether the first row or the first column contains any zeroes. If they do, record these findings in two distinct boolean variables, as they may be needed later. Next, traverse the matrix beginning from the second row and the second column. For each cell that contains a zero, utilize the first row and the first column to signal this condition. Specifically, if matrix[i][j] is zero, set matrix[i][0] and matrix[0][j] to zero. Afterward, iterate through the matrix again in reverse, starting from the second row and second column. If you encounter a zero in the first cell of any row or column, set the entire respective row or column to zero. Finally, if the boolean variables for the first row and column that you recorded earlier are true, set those rows and columns to zero as well. This method operates in place, meaning it modifies the original matrix without the need for any additional data structures. As a result, the space complexity remains constant. **

Alternative Answer

** Another approach involves utilizing bitwise operators to identify rows and columns that contain zeros. The steps for this method are as follows: Initialize two variables, rowFlag and colFlag , with an initial value of 1. Examine the first row and first column. If a zero is detected, set either rowFlag or colFlag to zero. For the other cells, if a cell's value is zero, set the first cell of the corresponding row and column to zero. Go through the matrix again, and for each cell matrix[i][j] , if either matrix[i][0] or matrix[0][j] is zero, set matrix[i][j] to zero. Finally, based on the status of the first row and first column flags, update the first row and first column accordingly. This approach also maintains constant space complexity since it does not require additional space to track the state of the rows and columns. The time complexity is O(M*N) due to the need to iterate through every cell in the matrix.

Question Details

Difficulty & Category

Medium

Product

For CandidatesFor RecruitersCompaniesBrowse JobsInterview QuestionsDeep ProfileSkill AssessmentOpportunity Matching
Prepin.ai

© 2026 Prepin LLC · Philadelphia, PA · All rights reserved.