2D Geometry Etc. Flashcards
- Diagonal Traverse
Solved
Medium
Topics
Companies: Facebook 2024
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
Example 1:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
Example 2:
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
-105 <= mat[i][j] <= 105
Diagonals r,c have a property know which diaognal does this cell lies
https://leetcode.com/problems/diagonal-traverse/description/
From N Queens problem.
~~~
from collections import defaultdict, deque
class Solution(object):
def findDiagonalOrder(self, mat):
“””
:type mat: List[List[int]]
:rtype: List[int]
“””
diag = defaultdict(deque)
rows = len(mat)
cols = len(mat[0])
for r in range(rows):
for c in range(cols):
d = r+c
if d%2:
diag[d].append(mat[r][c])
else:
diag[d].appendleft(mat[r][c])
ret = []
for i in range(rows+cols):
ret.extend(diag[i])
return ret
~~~
- Toeplitz Matrix
Solved
Easy
Topics
Companies
Hint
Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false.
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.
Example 1:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
“[9]”, “[5, 5]”, “[1, 1, 1]”, “[2, 2, 2]”, “[3, 3]”, “[4]”.
In each diagonal all elements are the same, so the answer is True.
Example 2:
Input: matrix = [[1,2],[2,2]]
Output: false
Explanation:
The diagonal “[1, 2]” has different elements.
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 20
0 <= matrix[i][j] <= 99
Follow up:
What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
What if the matrix is so large that you can only load up a partial row into the memory at once?
Base:
~~~
class Solution(object):
def isToeplitzMatrix(self, matrix):
“””
:type matrix: List[List[int]]
:rtype: bool
“””
r = len(matrix)
c = len(matrix[0])
for row in range(1, r):
for col in range(1, c):
if matrix[row-1][col-1] != matrix[row][col]:
return False
return True
~~~
Follow ups: Since numbers are in range 0-99 we store all the cells where the numbers appear as we go down and check if the number was in r-1,c-1
Follow up 2: Split the row in half, and adjust the column for second half accordingly.
~~~
from collections import defaultdict
class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
rows = len(matrix)
cols = len(matrix[0])
store = defaultdict(set)
for r in range(rows):
row = matrix[r]
for c in range(cols):
if r == 0 or c == 0 or (r-1, c-1) in store[row[c]]:
store[row[c]].add((r,c))
else:
return False
return True
# Follow up 2
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
rows = len(matrix)
cols = len(matrix[0])
row_half = cols//2
first_half = row_half
second_half = first_half + 1 if cols%2 else first_half
store = defaultdict(set)
for r in range(rows):
row = matrix[r][:row_half]
for c in range(first_half):
if r == 0 or c == 0 or (r-1, c-1) in store[row[c]]:
store[row[c]].add((r,c))
else:
return False
row = matrix[r][row_half:]
for ic in range(second_half):
c = ic + row_half
if r == 0 or c == 0 or (r-1, c-1) in store[row[ic]]:
store[row[ic]].add((r,c))
else:
return False
return True ~~~
- Design Snake Game
Solved
Medium
Topics
Companies
Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.
The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.
You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game’s score both increase by 1.
Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.
When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.
The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).
Implement the SnakeGame class:
SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.
Example 1:
Input
[“SnakeGame”, “move”, “move”, “move”, “move”, “move”, “move”]
[[3, 2, [[1, 2], [0, 1]]], [“R”], [“D”], [“R”], [“U”], [“L”], [“U”]]
Output
[null, 0, 0, 1, 1, 2, -1]
Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move(“R”); // return 0
snakeGame.move(“D”); // return 0
snakeGame.move(“R”); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move(“U”); // return 1
snakeGame.move(“L”); // return 2, snake eats the second food. No more food appears.
snakeGame.move(“U”); // return -1, game over because snake collides with border
Constraints:
1 <= width, height <= 104
1 <= food.length <= 50
food[i].length == 2
0 <= ri < height
0 <= ci < width
direction.length == 1
direction is ‘U’, ‘D’, ‘L’, or ‘R’.
At most 104 calls will be made to move.
https://leetcode.com/problems/design-snake-game/description/
from collections import deque
class SnakeGame(object):
def \_\_init\_\_(self, width, height, food):
"""
:type width: int
:type height: int
:type food: List[List[int]]
"""
self.width = width
self.height = height
self.score = 0
self.food = deque(food)
self.body = deque()
self.head = (0,0)
self.movements = {"R": [0,1], "U": [-1,0], "D": [1,0], "L": [0, -1]}
def is_valid(self, pos_r, pos_c):
if 0 <= pos_r < self.height and 0 <= pos_c < self.width:
return True
else:
return False
def move(self, direction):
"""
:type direction: str
:rtype: int
"""
movement = self.movements[direction]
new_r,new_c = self.head[0] + movement[0], self.head[1] + movement[1]
if not self.is_valid(new_r, new_c):
return -1
if self.food and [new_r, new_c] == self.food[0]:
self.body.appendleft(self.head)
self.food.popleft()
self.score += 1
self.head = (new_r, new_c)
else:
# move
prev = self.head
self.head = (new_r, new_c)
if self.body and (new_r, new_c) in self.body and (new_r, new_c) != self.body[-1]:
return -1
for pos in range(len(self.body)):
self.body[pos], prev = prev, self.body[pos]
return self.score
Your SnakeGame object will be instantiated and called as such:
# obj = SnakeGame(width, height, food)
# param_1 = obj.move(direction)
Your SnakeGame object will be instantiated and called as such:
# obj = SnakeGame(width, height, food)
# param_1 = obj.move(direction)- Squirrel Simulation
Solved
Medium
Topics
Companies
Hint
You are given two integers height and width representing a garden of size height x width. You are also given:
an array tree where tree = [treer, treec] is the position of the tree in the garden,
an array squirrel where squirrel = [squirrelr, squirrelc] is the position of the squirrel in the garden,
and an array nuts where nuts[i] = [nutir, nutic] is the position of the ith nut in the garden.
The squirrel can only take at most one nut at one time and can move in four directions: up, down, left, and right, to the adjacent cell.
Return the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one.
The distance is the number of moves.
https://leetcode.com/problems/squirrel-simulation/
from itertools import starmap
from functools import reduce
class Solution:
def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:
def manhattan_distance(point_a, point_b):
return abs(point_a[0]-point_b[0]) + abs(point_a[1]-point_b[1])
_, idx_closest_nut = min(list(starmap(lambda idx, nut: (manhattan_distance(nut, squirrel) - manhattan_distance(nut, tree), idx), enumerate(nuts))))
distance = reduce(lambda prev, cur: prev + manhattan_distance(cur, tree) * 2, nuts, 0)
return (distance - manhattan_distance(nuts[idx_closest_nut], tree)) + manhattan_distance(nuts[idx_closest_nut], squirrel)
Find the minimum extra distance that will be incurred bt choosing one of the nuts as the starting point.
Normal distance = Tree to nut + nut to tree
Squirrel Distance = Squirrel to nut + nut to tree
Extra distance if squirrel was to pick this nut = Squirrel Distance - Normal Distance = Squirrel to nut + tree to nut + nut to tree - nut to tree = squirrel to nut - tree to nut
minimize this to get the first point and adjust final distance accordinly.
O(n) time O(1) space
