778. Swim in Rising Water
You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.
Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).
Discussion
I originally was going to do a greedy algorithm that would as far as it could at each time point. I think, because each cell value is unique, there is always going to be a single solution.
I didn’t finish my solution and it seems that I should take a step back and not immediately think in terms of time.
import heapq
from collections import namedtuple
Cell = namedtuple('Cell', ['val', 'x', 'y'])
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
"""
O(n^2 log(n)) time. Pushing and popping a heap takes O(log n) time and
we will do for each cell in the worst case.
O(n^2) space. The heap could contain all cells in the grid.
"""
m, n = len(grid), len(grid[0])
# pq is a min heap
pq, seen, min_time = [Cell(grid[0][0], 0, 0)], set([(0, 0)]), 0
while True:
# pop cell with lowest value
val, x, y = heapq.heappop(pq)
min_time = max(min_time, val)
if x == m-1 and y == n-1:
return min_time
for i, j in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
in_bounds = 0 <= i < m and 0 <= j < n
if in_bounds and (i, j) not in seen:
seen.add((i, j))
heapq.heappush(pq, Cell(grid[i][j], i, j))
200. Number of Islands
Given an m x n 2D binary grid grid which represents a map of '1's (land) and
'0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
count = 0
if not grid:
return count
rows, cols = len(grid), len(grid[0])
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
self.dfs(grid, i, j)
count += 1
return count
def dfs(self, grid: list[list[str]], i: int, j: int):
rows, cols = len(grid), len(grid[0])
row_out_of_bounds = i < 0 or i >= rows
col_out_of_bounds = j < 0 or j >= cols
if row_out_of_bounds or col_out_of_bounds:
return
water = grid[i][j] != '1'
if water:
return
# If we're on land, mark as visited
grid[i][j] = '#'
# Explore rest of island
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)
EPI 18.1. Search a maze
WHITE, BLACK = range(2)
Coord = nametuple('Coord', ['x', 'y'])
def search_maze(maze, s, e):
def search_maze_helper(cur):
if not (0 <= cur.x < len(maze) and
0 <= cur.y < len(maze[cur.x]) and
maze[cur.x][cur.y] != WHITE):
return False
path.append(cur)
maze[cur.x][cur.y] = BLACK
if cur == e:
return True
if any(map(search_maze_helper,
(Coord(cur.x-1, cur.y), Coord(cur.x+1, cur.y),
Coord(cur.x, cur.y-1, Coord(cur.x, cur.y+1)))):
return True
del path[-1]
return False
path = []
return path if search_maze_helper(s) else []
EPI 14.2. Find first key greater than key in BST
Node = namedtuple('Node', ['data', 'left', 'right'], defaults=[None] * 3)
def find_next_greatest(tree, key):
sub_tree, closest = tree, None
while sub_tree:
if subtree.data > key:
closest, sub_tree = sub_tree, subtree.left
else:
# Root and all keys in left subtree are <= k, so skip them.
sub_tree = sub_tree.right
return closest
LeetCode 50. Implement Pow()
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).
class Solution:
def myPow(self, x: float, n: int) -> float:
r, power = 1.0, n
if n < 0:
power, x = -power, 1.0 / x
while power:
if power & 1:
r *= x
x *= x
power >>= 1
return r
Recursive solution:
class Solution:
def myPow(self, base: float, exponent: int) -> float:
def calculate(base, exponent):
if base == 0: return 0
if base == 1 or exponent == 0: return 1
if exponent == 1: return base
result = calculate(base, exponent//2)
result = result * result
return base * result if exponent%2 != 0 else result
return calculate(base, abs(exponent)) if exponent >= 0 else 1/calculate(base, abs(exponent))
LeetCode. Largest rectangle in histogram
Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
"""Solution from gcobs0834"""
stack = []
maxArea = 0
for i in range(len(heights)):
startIdx = i
while stack and stack[-1][1] > heights[i]:
idx, height = stack.pop()
maxArea = max(maxArea, height * (i - idx))
startIdx = idx
stack.append((startIdx, heights[i])) # store (idx, height)
for startIdx, height in stack:
maxArea = max(maxArea, height * (len(heights) - startIdx))
return maxArea
LeetCode. Same tree
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if (not p) and (not q):
return True
if (not p) or (not q):
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
LeetCode. Product of Array except itself
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [1 for _ in range(n)]
for i in range(1, n):
res[i] = res[i-1] * nums[i-1]
left = 1
for i in reversed(range(n)):
res[i] *= left
left *= nums[i]
return res
LeetCode. Add two numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
result = curr = ListNode()
rem = 0
while l1 and l2:
rem, digit = divmod(l1.val + l2.val + rem, 10)
curr.next = ListNode(digit)
curr = curr.next
l1 = l1.next
l2 = l2.next
longer = l1 or l2
while longer:
rem, digit = divmod(longer.val + rem, 10)
curr.next = ListNode(digit)
curr = curr.next
longer = longer.next
curr.next = ListNode(rem) if rem else None
return result.next
LeetCode. Validate Binary Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.dfs(root, float('-inf'), float('inf'))
def dfs(self, root, lo, hi):
if not root:
return True
elif not lo < root.val < hi:
return False
return (self.dfs(root.left, lo, root.val) and
self.dfs(root.right, root.val, hi))
LeetCode 662. Maximum Width of Binary Tree
Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.
It is guaranteed that the answer will in the range of 32-bit signed integer.
from collections import deque
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
"""This is a solution from the discussions section"""
dic = defaultdict(list)
level = 0
column = 0
res = []
self.dfs(root, dic, level, column)
for level in dic:
dis = max(dic[level]) - min(dic[level]) + 1
res += [dis]
return max(res)
def dfs(self, root, dic, level, column):
if root:
dic[level].append(column)
self.dfs(root.left, dic, level + 1, column * 2)
self.dfs(root.right, dic, level + 1, column * 2 + 1)