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.
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
(y,0) to 0. In a second iteration, we can set the row or column to fully 0 based on those indexes.
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.
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 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.
O(N * 3^n)
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.
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
The travelling direction is:
Wall is defined by either the edge of the matrix or a visited cell.
So, we need to:
Since we know the travel direction, we only traverse the number of elements in the matrix,
O(n), we atleast need to store all elements in a result array.
Return to Index