Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Arrays & Strings

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Zero Matrix

Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

👉 Link here to the repo to solve the problem

imagen

👌 Tips

If you just cleared the rows and columns as you found Os, you'd likely wind up clearing the whole matrix.Try finding the cells with zeros first before making any changes to the matrix.

Can you use 0 (N) additional space instead of 0 (N2 )? What information do you really need from the list of cells that are zero?

You probably need some data storage to maintain a list of the rows and columns that need to be zeroed. Can you reduce the additional space usage to a(1) by using the matrix itself for data storage?

👊 Solution 1

At first glance, this problem seems easy: just iterate through the matrix and every time we see a cell with value zero, set its row and column to 0. There's one problem with that solution though: when we come across other cells in that row or column, we'll see the zeros and change their row and column to zero. Pretty soon, our entire matrix will be set to zeros.

One way around this is to keep a second matrix which flags the zero locations. We would then do a second pass through the matrix to set the zeros. This would ta ke 0 (MN) space.

Do we really need O(MN) space? No. Since we're going to set the entire row and column to zero, we don't need to track that it was exactly ce11[2] [4] (row 2, column 4). We only need to know that row 2 has a zero somewhere, and column 4 has a zero somewhere.We'll set the entire row and column to zero anyway, so why would we care to keep track of the exact location of the zero?

The code below implements this algorithm.We use two arrays to keep track ofall the rows with zeros and all the columns with zeros.We then nullify rows and columns based on the values in these arrays.

void solution(int[][] matrix) {
    int length = matrix.length;
    boolean[] row = new boolean[length];
    boolean[] column = new boolean[length];

    // Store the row and column index with value 0
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 0) {
                row[i] = true;
                column[j] = true;
            }
        }
    }

    // nullify rows
    for (int i = 0; i < row.length; i++) {
        if (row[i]) nullifyRow(matrix, i);
    }

    // nullify columns
    for (int i = 0; i < column.length; i++) {
        if (column[i]) nullifyColumn(matrix, i);
    }
}

void nullifyRow(int[][] matrix, int row) {
    for (int i = 0; i < matrix[0].length; i++) {
        matrix[row][i] = 0;
    }
}

void nullifyColumn(int[][] matrix, int col) {
    for (int i = 0; i < matrix.length; i++) {
        matrix[i][col] = 0;
    }
}

Question borrowed from “Cracking the coding interview”

Last updated on 3/4/2020
← Rotate MatrixValid Parenthesis →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr