Leetcode: Matrix

Question 1

Strategies for matrix

Answer 1

1. Different ways to traverse a grid, LongestIncreasingSubsequence, colored_graph problen,

Question 2

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Answer 2

brute is getting the smallest row/col, then do linear loop through smallest one and binary search through the larger one. O(n log m) time and constant space. You can optimize it with a diagonal binary search too.

1. draw matrix
2. start at bottom left, matrix[10][0] an example
3. while the row and col are in bounds
4. if that value is larger than target, it cannot be in this row, row -= 1
5. if the value is less than target, it could be in the row, col -= 1
6. at each iteration, check both of these and move the column accordingly

time: O(n + m), worst case it is in the top right
space: O(1), no space

class Solution:

• —def optimal(self, matrix, target):
• ——-if not matrix:
• ———–return False
• ——-row, col = len(matrix) - 1, 0
• ——-while 0 <= row < len(matrix) and 0 <= col < len(matrix[0]):
• ———–cur = matrix[row][col]
• ———–if cur == target:
• —————return True
• ———–elif cur < target:
• —————col += 1
• ———–else:
• —————row -= 1
• ——-return False

divide and conquer

time: O(n logN)
space: O(log(n)) bc each divide can require logN space

class Solution3:

• —def searchMatrix(self, matrix, target: int) -> bool:
• ——-if not matrix:
• ———–return False
• ——-return self.helper(0, 0, len(matrix)-1, len(matrix[0])-1, matrix, target)
• —def helper(self, top, left, bottom, right, matrix, target):
• ——-if left>right or top>bottom:
• ———–return False
• ——-elif targetmatrix[bottom][right]:
• ———–return False
• ——-mid=(right+left)//2
• ——-i=top
• ——-while i < bottom+1 and matrix[i][mid]<=target:
• ———–if matrix[i][mid]==target:
• —————return True
• ———–i+=1

——–return self.helper(i, left, bottom, mid-1, matrix, target) or self.helper(top, mid+1, i-1, right, matrix, target)

Question 3

n-qeeuns 2

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Answer 3

brute force would be to generate all combinations of squares with N queens, see if they are attacking, return each time they are not, n^n time

Custom solution, not optimal but better than brute force. N!*N^2 time (initial backtracking loop + placing a queen and incrementing numbers on matrix), N^2 space for matrix

• —def brute(self, n: int) -> int:
• ——-self.matrix = self.make_matrix(n)
• ——-self.answer=0
• ——-self.backtrack(0, 0, n)
• ——-return self.answer
• —def backtrack(self, y, x, n):
• ——-if y0 and not remove:
• ———–return False
• ——-self.matrix[y][x]+=increment
• ——-li=[-1, 1]
• ——-for i in li:
• ———–self.helper(y+i, i, x, 0, n, increment)
• ———–self.helper(y, 0, x+i, i, n, increment)
• ———–for j in li:
• —————self.helper(y+i, i, x+j, j, n, increment)
• ——-return True
• —def helper(self, y, dy, x, dx, n, increment):
• ——-if x=0 and y=0:
• ———–self.matrix[y][x]+=increment
• ———–self.helper(y+dy, dy, x+dx, dx, n, increment)

1. recognize diagonals are constant on row-column, and anti-diagonals are constant on row+column
2. create 3 sets for columns (queens cant be on the same column), diagonals and anti diagonals
3. create a backtracking algo that loops through each column on a given row, checks if any set contains a diagonal
4. if not, add diagonals/antis/columns to sets, move 1 row up, once call returns backtrack by removing the values from the sets
5. each backtracking call if row==4 (meaning we are beyond the capacity of the board) solution+=1
6. I found it easier to use global instance variables, but you could also just put those values in each method call. make sure the solutions variable is a default argument=0

time: O(N!), bc of backtracking this makes sense bc each row has N…N-1…1 options to go through
space: N, the 3 sets each take of N space, the recursion on backtracking will only go N deep as well

class Solution:

• —def totalNQueens(self, n: int) -> int:
• ——-self.solutions=0
• ——-self.diagonals, self.anti_diagonals, self.columns = set(),set(),set()
• ——-self.helper(0, n)
• ——-return self.solutions
• —def helper(self, row, n):
• ——-if row==n:
• ———–self.solutions+=1
• ——-for i in range(n):
• ———–diagonal=row-i
• ———–a_diagonal=row+i
• ———–if i in self.columns or diagonal in self.diagonals or a_diagonal in self.anti_diagonals:
• —————continue
• ———–self.columns.add(i)
• ———–self.diagonals.add(diagonal)
• ———–self.anti_diagonals.add(a_diagonal)
• ———–self.helper(row+1, n)
• ———–self.columns.remove(i)
• ———–self.diagonals.remove(diagonal)
• ———–self.anti_diagonals.remove(a_diagonal)

Question 4

pacific atlantic water flow

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Answer 4

brute force is a double for loop, with a DFS on each item to search if it touches both atlantic and pacific by setting the “goal” values. this is (m*n)^2 bc each iteration can go through all the other points. We also need to make sure we don’t get an infinite loop by tracking which points we have been to on each iteration

• —def brute(self, heights):
• ——-out = []
• ——-self.m = len(heights)
• ——-self.n = len(heights[0])
• ——-self.heights = heights
• ——-self.seen = [[False for i in range(self.n)] for i in range(self.m)]
• ——-for i in range(self.m):
• ———–for j in range(self.n):
• —————if self.helper(i, j, 0, 0, float(‘inf’)) and self.helper(i, j, self.m-1, self.n-1, float(‘inf’)):
• ——————-out.append([i, j])
• ——-return out
• —def helper(self, i, j, goalY, goalX, ph):
• ——-if i [greater than]= 0 and i [less than] self.m and j [greater than]= 0 and j [less than] self.n and self.heights[i][j] [less than]= ph:
• ———–if not self.seen[i][j]:
• —————self.seen[i][j] = True
• ———–else:
• —————return False
• ———–if i is goalY or j is goalX:
• —————self.seen[i][j] = False
• —————return True
• ———–else:
• —————# up, down, left, right
• —————if (self.helper(i -1, j, goalY, goalX, self.heights[i][j])
• ——————-or self.helper(i, j - 1, goalY, goalX, self.heights[i][j])
• ——————-or self.helper(i + 1, j, goalY, goalX, self.heights[i][j])
• ——————-or self.helper(i , j + 1, goalY, goalX, self.heights[i][j])):
• ——————-self.seen[i][j] = False
• ——————-return True
• —————else:
• ——————-self.seen[i][j] = False
• ——————-return False
• ——-else:
• ———–return False

1. search from outside in for both oceans, collect the points that flow to each ocean, then do an intersection between both sets to see which points are in both
2. BFS uses a queue, we add all the edges to both sets, then do a BFS iteration
3. check boundaries, check if it has been seen, check if the next point has equal to or greater than height, if so add to the final response
4. intersection on response

DFS/BFS have same time/space

time: O(n * m), we have to check each point, if each point has the same height, we check them both for each ocean
space: O(n * m), the sets can, in the worst case, hold all points in the matrix. The queue/recurion stack for DFS could also hold all the points at once

class BFS:

• —def BFS(self, heights):
• ——-self.m = len(heights)
• ——-self.n = len(heights[0])
• ——-self.heights = heights
• ——-pacific = []
• ——-atlantic = []
• ——-for i in range(self.m):
• ———–pacific.append([i, 0])
• ———–atlantic.append([i, self.n-1])
• ——-for i in range(self.n):
• ———–pacific.append([0, i])
• ———–atlantic.append([self.m-1, i])
• ——-pacific_set = self.helper(pacific)
• ——-atlantic_set = self.helper(atlantic)
• ——-return list(pacific_set.intersection(atlantic_set))
• —def helper(self, li):
• ——-response = set()
• ——-while li:
• ———–y, x = li.pop(0)
• ———–response.add((y, x))
• ———–for yy, xx in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
• —————cy, cx = y + yy, x + xx
• —————if cy [less than] 0 or cy [greater than]= self.m or cx [less than] 0 or cx [greater than]= self.n:
• ——————-continue
• —————if (cy, cx) in response:
• ——————-continue
• —————if self.heights[cy][cx] [greater than]= self.heights[y][x]:
• ——————-li.append([cy, cx])
• ——-return response

1. instead of getting all valid ocean edges in the beginning, go through them 1 at a time. same principle as BFS

class DFS:

• —def DFS(self, heights):
• ——-self.m = len(heights)
• ——-self.n = len(heights[0])
• ——-self.heights = heights
• ——-pacific = set()
• ——-atlantic = set()
• ——-for i in range(self.m):
• ———–self.helper(i, 0, pacific)
• ———–self.helper(i, self.n-1, atlantic)
• ——-for i in range(self.n):
• ———–self.helper(0, i, pacific)
• ———–self.helper(self.m-1, i, atlantic)
• ——-return list(pacific.intersection(atlantic))
• —def helper(self, y, x, ocean):
• ——-ocean.add((y, x))
• ——-for yy, xx in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
• ———–cy, cx = y + yy, x + xx
• ———–if cy [less than] 0 or cy [greater than]= self.m or cx [less than] 0 or cx [greater than]= self.n:
• —————continue
• ———–if (cy, cx) in ocean:
• —————continue
• ———–if self.heights[cy][cx] [greater than]= self.heights[y][x]:
• —————self.helper(cy, cx, ocean)

Question 5

search 2d matrix 1

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Answer 5

brute force is linear search, or linear/binary search at NlogN time

1. you can binary search a matrix if you index the matrix using divmod(mid, row length)
2. given a 3x4, we get the total distance as 11, divmod(11, 4) is 2, 3 which gives us the last item in the matrix. using this we can iterate through the matrix in a binary search fashion

time: O(log(n * m) where n*m is the total size of the matrix
space: constant

class Solution:

• —def searchMatrix(self, matrix, target) -[greater than] bool:
• ——-if len(matrix) == 0:
• ———–return False
• ——-y = len(matrix)
• ——-x = len(matrix[0])
• ——-left, right = 0, y * x - 1
• ——-while right [greater than]= left:
• ———–mid = (right + left) // 2
• ———–div, mod = divmod(mid, x)
• ———–element = matrix[div][mod]
• ———–if element == target:
• —————return True
• ———–elif target [less than] element:
• —————right = mid - 1
• ———–else:
• —————left = mid + 1
• ——-return False

Question 6

diagonal traversal

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Answer 6

1. think of a state machine. If we are going up we have different directions than if we are going down
2. going up if we are less than 0 or greater than col, we go right or down. We prefer to go right first, but if we cannot we go down
3. going down we do the reverse
4. For both up and down, looking at a picture we can see if we can’t go right we are able to go down. Vise versa is true for going down

time: O(N * M), or linear in terms of elements in the matrix
space: constant, other than the output array.

class Solution:

• —def findDiagonalOrder(self, mat):
• ——-if not mat:
• ———–return []
• ——-response = []
• ——-end_row = len(mat) - 1
• ——-end_col = len(mat[0]) - 1
• ——-up = True
• ——-row, col = 0, 0
• ——-while True:
• ———–response.append(mat[row][col])
• ———–if row == end_row and col == end_col:
• —————return response
• ———–if up:
• —————if row - 1 < 0 or col + 1 > end_col:
• ——————-if col + 1 <= end_col:
• ———————–col += 1
• ——————-else:
• ———————–row += 1
• ——————-up = False
• —————else:
• ——————-row -= 1
• ——————-col += 1
• ———–else:
• —————if row + 1 > end_row or col - 1 < 0:
• ——————-if row + 1 <= end_row:
• ———————–row += 1
• ——————-else:
• ———————–col += 1
• ——————-up = True
• —————else:
• ——————-row += 1
• ——————-col -= 1

Question 7

n queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.

Answer 7

1. a queen cannot be in the same column, diagonal, anti-diagonal, or row. The backtracking algorithm takes care of the row, we check for the rest
2. draw out numbers on diagonals and anti-diagonals, 2 different graphs, see that for diagonals each one calculates to row - col, while anti-diagonal calcs to row + col, and col is just col
3. make 3 sets for each, backtrack to add and remove into each
4. you COULD build the strings during each backtrack, but that would increase the time from N! to N!*N, so we make a blank board, use insertion to modify the lists of each row from “.” to “Q”, backtrack to change it

time: O(N!), you may think we add N^2 to it bc we have to append the board state to the response, but that can only happen N times because it only happens at the end of the solution. meaning it is N! + n*N^2, so N! is larger.
space: O(N^2), space for the empty board

class Solution:

• —def0, self.a_diagonals, self.columns = set(), set(), set()
• ——-self.response = []
• ——-self.empty_board = [[”.” for _ in range(n)] for _ in range(n)]
• ——-self.calculate_collisions(0, n)
• ——-return self.response
• —def append_board(self):
• ——-answer = []
• ——-for row in self.empty_board:
• ———–answer.append(““.join(row))
• ——-self.response.append(answer)
• —def calculate_collisions(self, row, n):
• ——-if row == n:
• ———–self.append_board()
• ———–return
• ——-else:
• ———–for i in range(n):
• —————diagonal = row - i
• —————a_diagonal = row + i
• —————if i in self.columns or diagonal in self.diagonals or a_diagonal in self.a_diagonals:
• ——————-continue
• —————self.diagonals.add(diagonal)
• —————self.a_diagonals.add(a_diagonal)
• —————self.columns.add(i)
• —————self.empty_board[row][i] = “Q”
• —————self.calculate_collisions(row + 1, n)
• —————self.diagonals.remove(diagonal)
• —————self.a_diagonals.remove(a_diagonal)
• —————self.columns.remove(i)
• —————self.empty_board[row][i] = “.”

Question 8

spiral matrix

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

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Answer 8

1. we control the code, we know when it transitions, we can make a state machine!
2. base case is when the response has equal length to the input matrix
3. right -> down -> left -> up -> right
4. careful on the transitions, make sure to run through the code, do not do matrix[left + i], i has left factored into it bc of the dynamic range updates we have, so no need!

time: O(n*m) which is the total size of the matrix
space: constant

class Solution:
—-def spiralOrder(self, matrix):
——–response = []
——–right, left, up, down = Direction(“right”), Direction(“left”), Direction(“up”), Direction(“down”)
——–right.next, left.next, up.next, down.next = down, up, right, left
——–state = StateMachine(right)
——–left, up = 0, 0
——–rows, cols = len(matrix), len(matrix[0])
——–down = rows - 1
——–right = cols - 1
——–
——–while len(response) < rows * cols:
————if state.state.direction == “right”:
—————-for i in range(left, right + 1):
——————–response.append(matrix[up][i])
—————-up += 1
—————-state.transition()
————elif state.state.direction == “down”:
—————-for i in range(up, down + 1):
——————–response.append(matrix[i][right])
—————-right -= 1
—————-state.transition()
————
————elif state.state.direction == “left”:
—————-for i in range(right, left - 1, -1):
——————–response.append(matrix[down][i])
—————-down -= 1
—————-state.transition()
————
————elif state.state.direction == “up”:
—————-for i in range(down, up - 1, -1):
——————–response.append(matrix[i][left])
—————-left += 1
—————-state.transition()
——–return response
————————
class StateMachine:
—-def __init__(self, state):
——–self.state = state
—-
—-def get_direction(self):
——–return self.state.direction
—-
—-def transition(self):
——–self.state = self.state.next
————
class Direction:
—-def __init__(self, direction):
——–self.direction = direction
——–self.next = None

1. can also do with just if-statements

class Solution:
—-def spiralOrder(self, matrix):
——–response = []
——–state = Direction()
——–left, up = 0, 0
——–rows, cols = len(matrix), len(matrix[0])
——–down = rows - 1
——–right = cols - 1
——–
——–while len(response) < rows * cols:
————if state.direction == “right”:
—————-for i in range(left, right + 1):
——————–response.append(matrix[up][i])
—————-up += 1
—————-state.transition()
————elif state.direction == “down”:
—————-for i in range(up, down + 1):
——————–response.append(matrix[i][right])
—————-right -= 1
—————-state.transition()
————
————elif state.direction == “left”:
—————-for i in range(right, left - 1, -1):
——————–response.append(matrix[down][i])
—————-down -= 1
—————-state.transition()
————
————elif state.direction == “up”:
—————-for i in range(down, up - 1, -1):
——————–response.append(matrix[i][left])
—————-left += 1
—————-state.transition()
——–return response
————————
——–
class Direction:
—-def __init__(self):
——–self.direction = “right”
—-
—-def get_direction(self):
——–return self.direction
—-
—-def transition(self):
————self.direction = “down”
——–elif self.direction == “down”:
————self.direction = “left”
——–elif self.direction ==”left”:
————self.direction = “up”
——–elif self.direction == “up”:
————self.direction = “right”

Question 9

minimum sub array

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Answer 9

brute force is n^2, do a double for loop

1. you see an array and you have to search through it for some value, pointers or binary search, in this case, you can do both, but pointers are better

time: O(N), worse case we could see each element twice, so maybe 2N
space: constant, we do not create new ds’s

class Solution:

• —def optimal(self, target, nums):
• ——-_sum = sum(nums)
• ——-if _sum < target:
• ———–return 0
• ——-if _sum == target:
• ———–return len(nums)
• ——-l, r = 0, -1
• ——-length = len(nums)
• ——-_sum = 0
• ——-while l < len(nums):
• ———–if _sum < target and r + 1 < len(nums):
• —————r += 1
• —————_sum += nums[r]
• ———–else:
• —————_sum -= nums [l]
• —————l += 1
• ———–if _sum >= target:
• —————length = min(r - l + 1, length)
• ——-return length
• —def minSubArrayLen(self, target, nums):
• ——-if not nums:
• ———–return 0
• ——-if len(nums) == 1:
• ———–if nums[0] == target:
• —————return 1
• ———–else:
• —————return 0
• ——-left, right = 0, 1
• ——-response = float(“inf”)
• ——-current = nums[0]
• ——-while left < len(nums):
• ———–if current >= target:
• —————response = min(response, right - left)
• —————current -= nums[left]
• —————left += 1
• ———–elif current < target and right < len(nums):
• —————current += nums[right]
• —————right += 1
• ———–else: #it is less than, but right is at the end
• —————left += 1
• ——-return response if response != float(“inf”) else 0