Matrix Flashcards
Print matrix in spiral order
Given an M × N integer matrix, print it in spiral order.
The idea is to read elements from the given matrix and print the matrix in spiral order. Four loops are used to maintain the spiral order, each for the top, right, bottom, and left corner of the matrix.
The time complexity of the proposed solution is O(M × N) for an M × N matrix. The auxiliary space required by the program is O(M × N) for recursion (call stack).
############ code def printSpiralOrder(mat):
# base case
if not mat or not len(mat):
return
top = left = 0
bottom = len(mat) - 1
right = len(mat[0]) - 1
while True:
if left > right:
break
# print top row
for i in range(left, right + 1):
print(mat[top][i], end=' ')
top = top + 1
if top > bottom:
break
# print right column
for i in range(top, bottom + 1):
print(mat[i][right], end=' ')
right = right - 1
if left > right:
break
# print bottom row
for i in range(right, left - 1, -1):
print(mat[bottom][i], end=' ')
bottom = bottom - 1
if top > bottom:
break
# print left column
for i in range(bottom, top - 1, -1):
print(mat[i][left], end=' ')
left = left + 1
if __name__ == ‘__main__’:
mat = [
[1, 2, 3, 4, 5],
[16, 17, 18, 19, 6],
[15, 24, 25, 20, 7],
[14, 23, 22, 21, 8],
[13, 12, 11, 10, 9]
]
printSpiralOrder(mat)
recursive solution
def printSpiral(mat, top, bottom, left, right):
# base case
if not mat or not len(mat) or left > right:
return
# print top row
for i in range(left, right + 1):
print(mat[top][i], end=' ')
top = top + 1
if top > bottom:
return
# print right column
for i in range(top, bottom + 1):
print(mat[i][right], end=' ')
right = right - 1
if left > right:
return
# print bottom row
for i in range(right, left - 1, -1):
print(mat[bottom][i], end=' ')
bottom = bottom - 1
if top > bottom:
return
# print left column
for i in range(bottom, top - 1, -1):
print(mat[i][left], end=' ')
left = left + 1 printSpiral(mat, top, bottom, left, right)
if __name__ == ‘__main__’:
mat = [
[1, 2, 3, 4, 5],
[16, 17, 18, 19, 6],
[15, 24, 25, 20, 7],
[14, 23, 22, 21, 8],
[13, 12, 11, 10, 9]
]
top = 0 bottom = len(mat) - 1 left = 0 right = len(mat[0]) - 1 printSpiral(mat, top, bottom, left, right)
Create a spiral matrix from a given array
Given an integer array containing M × N elements, construct an M × N matrix from it in spiral order.
This problem is mainly the reverse of the following problem:
Print matrix in spiral order
The idea remains the same – read elements from the given array one by one and fill the matrix in spiral order. Four loops are used to maintain the spiral order, each for the top, right, bottom, and left corner of the matrix.
The time complexity of the proposed solution is O(M × N) for an M × N matrix and doesn’t require any extra space.
##################### Code def printSpiralOrder(A, M, N):
# base case
if not A:
return []
top = left = 0 bottom = M - 1 right = N - 1
# construct an `M × N` matrix
mat = [[0 for x in range(N)] for y in range(M)]
index = 0
while True:
if left > right:
break
# print top row
for i in range(left, right + 1):
mat[top][i] = A[index]
index = index + 1
top = top + 1
if top > bottom:
break
# print right column
for i in range(top, bottom + 1):
mat[i][right] = A[index]
index = index + 1
right = right - 1
if left > right:
break
# print bottom row
for i in range(right, left - 1, -1):
mat[bottom][i] = A[index]
index = index + 1
bottom = bottom - 1
if top > bottom:
break
# print left column
for i in range(bottom, top - 1, -1):
mat[i][left] = A[index]
index = index + 1
left = left + 1
for r in mat:
print(r)
Shift all matrix elements by 1 in spiral order
Given an M × N integer matrix, shift all its elements by 1 in spiral order.
We can easily solve this problem by reading elements from the given matrix one by one in spiral order and replacing them with their previous elements. Four loops are used to maintain the spiral order, each for the top, right, bottom, and left corner of the matrix.
O(M.N)
code
# Shift all matrix elements by 1 in spiral order def shiftMatrix(mat):
# base case
if not mat or not len(mat):
return
top = 0
bottom = len(mat) - 1
left = 0
right = len(mat[0]) - 1
prev = mat[0][0]
while True:
if left > right:
break
# change top row
for i in range(left, right + 1):
temp = mat[top][i]
mat[top][i] = prev
prev = temp
top = top + 1
if top > bottom:
break
# change right column
for i in range(top, bottom + 1):
temp = mat[i][right]
mat[i][right] = prev
prev = temp
right = right - 1
if left > right:
break
# change bottom row
for i in range(right, left - 1, -1):
temp = mat[bottom][i]
mat[bottom][i] = prev
prev = temp
bottom = bottom - 1
if top > bottom:
break
# change left column
for i in range(bottom, top - 1, -1):
temp = mat[i][left]
mat[i][left] = prev
prev = temp
left = left + 1
# first element of the matrix will be the last element replaced
mat[0][0] = prev
if __name__ == ‘__main__’:
matrix = [
[ 1, 2, 3, 4, 5],
[16, 17, 18, 19, 6],
[15, 24, 25, 20, 7],
[14, 23, 22, 21, 8],
[13, 12, 11, 10, 9]
]
shiftMatrix(matrix)
for row in matrix:
print(row)
Change all elements of row i and column j in a matrix to 0 if cell (i, j) is 0
Given an M × N matrix consisting of only 0 or 1, change all elements of row i and column j to 0 if cell (i, j) has value 0. Do this without using any extra space for every (i, j) having value 0.
A simple solution is to traverse the matrix and if we encounter any cell (i, j) that has value 0, change each element in the row i and column j to some arbitrary value other than 0 or 1. Later traverse the matrix once again and replace all elements with assigned value to 0.
O(M × N × (M + N))
#################### Code############### # Function to change all elements of row `x` and column `y` to -1 def changeRowColumn(mat, M, N, x, y):
for j in range(N):
if mat[x][j]:
mat[x][j] = -1
for i in range(M):
if mat[i][y]:
mat[i][y] = -1
# Function to convert the matrix def convert(mat):
# base case
if not mat or not len(mat):
return
# `M × N` matrix
(M, N) = (len(mat), len(mat[0]))
# traverse the matrix
for i in range(M):
for j in range(N):
if mat[i][j] == 0: # cell `(i, j)` has value 0
# change each non-zero element in row `i` and column `j` to -1
changeRowColumn(mat, M, N, i, j)
# traverse the matrix once again and replace cells having
# value -1 with 0
for i in range(M):
for j in range(N):
if mat[i][j] == -1:
mat[i][j] = 0
if __name__ == ‘__main__’:
mat = [
[1, 1, 0, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 0, 1, 1],
[1, 1, 1, 1, 1],
[0, 1, 1, 1, 1]
]
# convert the matrix
convert(mat)
# print matrix
for r in mat:
print(r)
Print diagonal elements of a matrix having a positive slope
Given an M × N integer matrix, print all its diagonal elements having a positive slope.
The idea is to start from each cell of the first column of the matrix to print / diagonal for the matrix’s upper-left half. Similarly, after the upper-left half, start from each cell of the last row to print the / diagonal for the matrix’s lower-right half.
time complexity of the proposed solution is O(M × N) for an M × N
code
def printMatrixDiagonally(mat):
# base case
if not mat or not len(mat):
return
(M, N) = (len(mat), len(mat[0]))
# print `/` diagonal for the upper-left half of the matrix
for r in range(M):
# start from each cell of the first column
i = r
j = 0
while j < N and i >= 0:
print(mat[i][j], end=' ')
i = i - 1
j = j + 1
print()
# print `/` diagonal for the lower-right half of the matrix
for c in range(1, N):
# start from each cell of the last row
i = M - 1
j = c
while j < N and i >= 0:
print(mat[i][j], end=' ')
i = i - 1
j = j + 1
print()
if __name__ == ‘__main__’:
mat = [
[1, 2, 3, 4, 5],
[2, 3, 4, 5, 6],
[3, 4, 5, 6, 7],
[4, 5, 6, 7, 8],
[5, 6, 7, 8, 9]
]
printMatrixDiagonally(mat)
Find all paths from first cell to last cell of a matrix
The problem is to count all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down
So this problem has both propertiesof a dynamic programming problem ( overlapying sub problems and the optimal subtracture). Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array count[][] in bottom up manner.
The following is bottom up approach.
####### code
# Returns count of possible paths to reach cell
# at row number m and column number n from the
# topmost leftmost cell (cell at 1, 1)
def numberOfPaths(m, n):
# Create a 2D table to store
# results of subproblems
# one-liner logic to take input for rows and columns
# mat = [[int(input()) for x in range (C)] for y in range(R)]
count = [[0 for x in range(n)] for y in range(m)]
# Count of paths to reach any
# cell in first column is 1
for i in range(m):
count[i][0] = 1;
# Count of paths to reach any
# cell in first column is 1
for j in range(n):
count[0][j] = 1;
# Calculate count of paths for other
# cells in bottom-up
# manner using the recursive solution
for i in range(1, m):
for j in range(1, n):
count[i][j] = count[i-1][j] + count[i][j-1]
return count[m-1][n-1]
# Driver program to test above function m = 3 n = 3 print( numberOfPaths(m, n))
