From Passion to Profession
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Data Structure - Mark Entire Row and Column Zero if an Element of an MxN Matrix is Zero

10/6/2013

0 Comments

 
Picture
When you're asked to mark an entire row and an entire column with 0's if an element of an MxN matrix is 0, here's my thought process:

  1. Define the contract of the function.
  2. Code the 2-passes algorithm.

The code below implements the solution:
public static void setZeros(int[][] matrix) {
  int[] row = new int[matrix.length];
  int[] column = new int[matrix[0].length];


  // Store the row and column index with value 0 

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

      if (matrix[i][j] == 0) {
        row[i] = 1;
        column[j] = 1;

      }
    } 

  }

  // Set arr[i][j] to 0 if either row i or column j has a 0 

  for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length; j++)
 {
      if ((row[i] == 1 || column[j] == 1)) { 
        matrix[i][j] = 0;
      }
    }

  }
} 

#1) Define the contract of the function

Name the function setZeros() to operate on a passed-in a 2-dimension int array, which will set all rows and columns of the matrix to zero if the element is 0.
  public static void setZeros(int[][] matrix)

#2) Generic case algorithm

Use a 2-passes scanning approach.

The first pass scans through the entire int[][] matrix to see which row and column has 0. During the scan, on detecting element being 0, flag the corresponding rows/columns to indicate they have 0's. For storing the flags, introduce a int[] for flagging rows and another int[] for flagging columns.
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];

The second pass scans through the entire int[][] matrix again to set the element to 0 if the corresponding row flag or column flag indicate the element should be set to 0.

The key concepts here are that int[][] is used to store the matrix, and utilizes a row array (int[]) and a column array (int[]) to store flags.
0 Comments



Leave a Reply.

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar