Questions

Set Matrix Zeroes

Leetcode

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

You must do it in place.

1 1 1
1 0 1
1 1 1

to

1 0 1
0 0 0
1 0 1
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

When we encounter the 0 at (1,1), we can set 0's to the whole row and column. But the problem with that approach is that when we go to (1,2), we would (incorrectly) set column 2 to 0's as well. So we cannot set the row and column to 0 as we encounter the 0. Instead, we need to track the row and column we need to set 0's and set it later.

What we can do is fix the first row(0) and column(0) and if we need to set the row or column to 0, we mark (0,x) or (y,0) to 0. In a second iteration, we can set the row or column to fully 0 based on those indexes.

Implementation: SetMatrixZeroes

Time complexity

O(n^2)

Space complexity

O(1)

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

A B C E
S F C S
A D E E
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

One approach would be to start from any character that matches the first character of the word and continue if it continues matching. If the end of the word is reached, we found the word. In each step, we can go in 3 potential directions, so it will cost us 3^n time. 3 because we dont need to go back the direction we came from, as we cannot re-use a character. Now we need to do it for all characters in the word, so total time complexity becomes N * 3^n, where N is the number of characters in the word and n is the number of characters on the board.

Another concern we need to take care of is track the visited elements. We can do this by either (1) taking a visited board and marking the cell visited, or (2) marking the current board as visited with a character like $.

Now if a path doesn't work out, we need to backtrack and try out a different path. During backtracking, we also need to un-mark the cell.

Implementation: WordSearch

Time complexity

O(N * 3^n)

Space complexity

O(n), for the recursion stack. We need to store the number of characters in the word in the recursion stack to verify if the word exists.

Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Input:

1   2   3

4   5   6

7   8   9

Output: 1, 2, 3, 6, 9, 8, 7, 4, 5

Leetcode

The travelling direction is:

  1. Travel right till we hit a wall.
  2. Travel bottom till we hit a wall.
  3. Travel left till we hit a wall.
  4. Travel up till we hit a wall.
  5. Rinse and repeat.

Wall is defined by either the edge of the matrix or a visited cell.

So, we need to:

  1. Keep track of the direction of travel. Change direction once we hit a wall.
  2. Travel in that direction and store the elements in a result array.
  3. Mark a visited cell visited with something. We can keep a visited matrix.

Implementation: SpiralMatrix

Time complexity

Since we know the travel direction, we only traverse the number of elements in the matrix, O(n).

Space complexity

O(n), we atleast need to store all elements in a result array.

Return to Index