N-All Flashcards
Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.
class Solution:
#Like walls and gates: multi-source bfs from all land tiles
def maxDistance(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
q = deque()
visit = set()
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1:
q.append((r, c))
visit.add((r, c))
dist = -1 #based on how the math works out
directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
#we can maintain a dist here.. or not too!
while q:
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
if neiR >= 0 and neiR < ROWS and neiC >= 0 and neiC < COLS and (neiR, neiC) not in visit and grid[neiR][neiC] == 0:
q.append((neiR, neiC))
visit.add((neiR, neiC))
dist += 1
#Why like this? We always increment dist by 1, so even if just iterate through land and add nothing -> -1 + 1 = 0
return -1 if dist == 0 else dist
#Runtime: O(mn)
#Space: O(mn)You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
def dfs(node, path):
if not node:
return 0
path = path * 10 + node.val
#This ordering of the above and below statements are important. Otherwise, we won't capture the leaf node value into the path!
if not node.left and not node.right:
return path
return dfs(node.left, path) + dfs(node.right, path)
return dfs(root, 0)
#Runtime: O(n)
#Space: O(h)
#Idea: When a leaf node returns, it will return the value
#of the path from the root to it.
#So when a parent looks and its 2 children (even if parent) is in the middle of tree, it will see the path values
#from root to its two children. It then takes the sum of
#those two path values and return those.You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
res = 0
l, r = 0, len(people) - 1
while l <= r:
#We will take the heaviest person for sure
res += 1
remainingWeight = limit - people[r]
r -= 1
#Take the lightest person if possible, and only if pointers have not crossed.
#Example [1, 2]: At this point l and r are both at i = 0, so that's fine. We can still take 1
#Example [1]. At this point, r is -1, so cannot possibly take l.
if l <= r and remainingWeight >= people[l]:
l += 1
return res
#O(n log n) for sorting, O(n) for traversal
#O(1) pointersGiven an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
class Solution:
def integerBreak(self, n: int) -> int:
dp = {1: 1}
for num in range(2, n + 1):
#We are required to break n up, so max result so far is zero.
#Otherwise if not n, we don't have to break num up since that can
#potentially be the max, and further subdivisions will worsen our result
dp[num] = 0 if num == n else num
#Two pieces: i and num - i
#i goes to num not num + 1! The reason is we want to disallow
#Breaking into (0, num).
for i in range(1, num):
val = dp[i] * dp[num - i]
dp[num] = max(dp[num], val)
return dp[n]
#Runtime: O(n ^ 2): n num subproblems 1 through n, each num takes O(n) time for the breakage into two pieces
#Space: O(n) for the dp cacheYou are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.
You are given two arrays redEdges and blueEdges where:
redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and
blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.
Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
redAdj = defaultdict(list) #maps a node to the red edge neighbors
blueAdj = defaultdict(list) #maps node to blue
for u, v in redEdges:
redAdj[u].append(v)
for u, v in blueEdges:
blueAdj[u].append(v)
visit = set() #(node, incoming color)
visit.add((0, None))
q = deque() #(node, incoming color, path length)
q.append((0, None, 0))
answer = [-1] * n
answer[0] = 0
while q:
for _ in range(len(q)):
curNode, prevColor, curLength = q.popleft()
#If first time ever visiting this node, that's the minimum
if answer[curNode] == -1:
answer[curNode] = curLength
#For source, prevColor is None, so both will fire.
if prevColor != "RED":
for v in redAdj[curNode]:
if (v, "RED") not in visit:
visit.add((v, "RED"))
q.append((v, "RED", curLength + 1))
if prevColor != "BLUE":
for v in blueAdj[curNode]:
if (v, "BLUE") not in visit:
visit.add((v, "BLUE"))
q.append((v, "BLUE", curLength + 1))
return answer
#O(2*N) -> O(N)
#O(2*N -> O(N)Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Input: nums = [1,1,1], k = 2
Output: 2
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefixCounts = {0: 1} #for prefixSum of 0, there's 1 way at least.
curSum = 0
res = 0
for n in nums:
curSum += n
diff = curSum - k
res += prefixCounts.get(diff, 0)
prefixCounts[curSum] = prefixCounts.get(curSum, 0) + 1
return res
#Runtime: O(n) to runthrough all elts and just do a check if diff is inside.
#Space: O(n) for the prefixCounts mapWe are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for curAst in asteroids:
while stack and stack[-1] > 0 and curAst < 0:
diff = stack[-1] + curAst
if diff < 0:
stack.pop()
elif diff > 0:
curAst = 0 #curAst is destroyed so set it to zero
else:
curAst = 0 #curAst is destroyed
stack.pop() #both are destroyed
if curAst: #if we still have an asteroid as a result of these operations
stack.append(curAst)
return stack
#Runtime: O(n)
#Space: O(n)You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 109.
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
ROWS, COLS = len(obstacleGrid), len(obstacleGrid[0])
dp = [0] * COLS #Think of the dp array as one row below the grid. So the loop will need to start from the last row and go upwards. But we do prefill the last entry with a 0 as base case.
dp[COLS - 1] = 1 #1 way to get from itself to destination
for r in range(ROWS - 1, -1, -1):
for c in range(COLS - 1, -1, -1):
if obstacleGrid[r][c]: #obstacle is if it's a 1.
dp[c] = 0 #immediately zero out. There's no way to get from this square to the bottom right.
#The current entry reflects the cell below. So just potentially add the cell from the right
elif c + 1 < COLS: #not COLS - 1.
dp[c] += dp[c + 1]
return dp[0]
#Runtime: O(mn)
#Space: O(n) single row array needed.Unique Paths (Single Array Solution)
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [0] * n #reflects the row below the grid
dp[n - 1] = 1 #base case: number of ways to reach bottom right from bottom right is 1
for r in range(m - 1, -1, -1):
for c in range(n - 1, -1, -1):
#dp[c] contains the number of ways from below already! (in-place)
#Potentially add number of ways from the right, if in bounds
if c + 1 < n:
dp[c] += dp[c + 1]
return dp[0]
#Runtime: O(mn)
#Space: O(n) one array only.
783. Minimum Distance Between BST Nodes
Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.
Input: root = [4,2,6,1,3]
Output: 1
# 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 minDiffInBST(self, root: Optional[TreeNode]) -> int:
prev, res = None, float('inf') #prev is the prev node.
#This forms an IOT.
def dfs(node):
if not node:
return
dfs(node.left)
nonlocal prev, res #Since these are just variables, have to set these.
#On the very first IOT call, res is not yet set since prev is None
#But then prev will later be set to node corresponding to 1.
#Then when popped back up, after dfs(node.left) is completed, prev corresponds to 1, so comparison will be made with 2, etc.
if prev:
res = min(res, node.val - prev.val)
prev = node
dfs(node.right)
dfs(root)
return res
#O(n)
#O(h)Decode String
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Input: s = “3[a2[c]]”
Output: “accaccacc”
class Solution:
def decodeString(self, s: str) -> str:
stack = []
for i in range(len(s)):
if s[i] != "]":
stack.append(s[i])
else: #is "]"
#Phase 1: Get the string until we see a left brace
sub = ""
while stack[-1] != "[":
sub = stack.pop() + sub
#Pop the "["
stack.pop()
#Phase 2: Get the count
count = ""
while stack and stack[-1] in "0123456789":
count = stack.pop() + count
stack.append((int(count) * sub))
return "".join(stack)
#Runtime: O(sum of the numbers in string * n) #e.g. 1000[ab]
#Space: O(n) for stackDesign HashMap
Design a HashMap without using any built-in hash table libraries.
Implement the MyHashMap class:
MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.
Input
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]
Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]
class ListNode:
def \_\_init\_\_(self, key = -1, val = -1, nxt = None):
#Default values above
self.key = key
self.val = val
self.next = nxt
class MyHashMap:
def \_\_init\_\_(self):
self.map = [ListNode() for i in range(1000)]
def getHash(self, key):
return key % len(self.map)
def put(self, key: int, value: int) -> None:
cur = self.map[self.getHash(key)]
while cur and cur.next:
if cur.next.key == key:
cur.next.val = value
return
cur = cur.next
#At the final node
cur.next = ListNode(key, value)
def get(self, key: int) -> int:
cur = self.map[self.getHash(key)]
while cur:
if cur.key == key:
return cur.val
cur = cur.next
return -1
def remove(self, key: int) -> None:
cur = self.map[self.getHash(key)]
while cur and cur.next:
if cur.next.key == key:
cur.next = cur.next.next
cur = cur.next
#Runtime: O(1) usually, or O(N) if long chained at an index
#Space: O(N) for hashmap
Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)Trim a Binary Search Tree
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.
Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]
# 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 trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root:
return None
if root.val > high:
return self.trimBST(root.left, low, high)
elif root.val < low:
return self.trimBST(root.right, low, high)
else:
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
#O(N)
#O(H)Unique Binary Search Trees
Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.
Input: n = 3
Output: 5
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for numNodes in range(2, n + 1):
total = 0
for root in range(1, numNodes + 1):
left = root - 1 #so if our root is value 1, then the node 0 is on the left
right = numNodes - root
total += dp[left] * dp[right]
dp[numNodes] = total
return dp[n]
#O(n^2)
#O(n)
#So if 3 nodes total
#2 nodes to the right. 3 - 1Remove Duplicates from Sorted List
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Input: head = [1,1,2,3,3]
Output: [1,2,3]
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur:
while cur.next and cur.next.val == cur.val:
cur.next = cur.next.next
cur = cur.next
return head
#O(n)
#O(1)Robot Bounded In Circle
On an infinite plane, a robot initially stands at (0, 0) and faces north. Note that:
The north direction is the positive direction of the y-axis.
The south direction is the negative direction of the y-axis.
The east direction is the positive direction of the x-axis.
The west direction is the negative direction of the x-axis.
The robot can receive one of three instructions:
“G”: go straight 1 unit.
“L”: turn 90 degrees to the left (i.e., anti-clockwise direction).
“R”: turn 90 degrees to the right (i.e., clockwise direction).
The robot performs the instructions given in order, and repeats them forever.
Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.
Input: instructions = “GGLLGG”
Output: true
Explanation: The robot is initially at (0, 0) facing the north direction.
“G”: move one step. Position: (0, 1). Direction: North.
“G”: move one step. Position: (0, 2). Direction: North.
“L”: turn 90 degrees anti-clockwise. Position: (0, 2). Direction: West.
“L”: turn 90 degrees anti-clockwise. Position: (0, 2). Direction: South.
“G”: move one step. Position: (0, 1). Direction: South.
“G”: move one step. Position: (0, 0). Direction: South.
Repeating the instructions, the robot goes into the cycle: (0, 0) –> (0, 1) –> (0, 2) –> (0, 1) –> (0, 0).
Based on that, we return true.
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
#We are bounded if
#Position never changes
#Position changes AND direction changes
dx, dy = 0, 1
x, y = 0, 0
for c in instructions:
if c == "G":
x, y = x + dx, y + dy
elif c == "L":
#Example: 0, 1 becomes -1, 0
dx, dy = -dy, dx
else: #it's an R
#Example: 1, 0 becomes 0, -1
dx, dy = dy, -dx
return (x, y) == (0, 0) or (dx, dy) != (0, 1) #When the second statement is executed, (x, y) is not (0, 0). No need to include that in that condition.
#Runtime O(n)
#Space: O(1)Maximum Sum Circular Subarray
Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.
A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].
A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], …, nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
curMax = 0
globalMax = nums[0]
curMin = 0
globalMin = nums[0]
total = 0
#If it's circular... We either take the global max, or we take the sum of the whole array and subtract out the globalMin
for n in nums:
total += n
curMax = max(curMax + n, n)
globalMax = max(curMax, globalMax)
curMin = min(curMin + n, n)
globalMin = min(curMin, globalMin)
#What does our current code do if all negative? We take the sum of all the values (-8), subtract by curMin = -8, to get a value of 0 which is incorrect
#The cause of the above issue is that globalMax is negative. So in the event of all negatives, globalMax is the biggest negative number. We can just then return that globalMax negative number.
return max(globalMax, total - globalMin) if globalMax > 0 else globalMax
#Runtime: O(n)
#Space: O(1)
Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
#O(n)
#O(1)
#Second middle node: slow, fast = head, head
#First middle node: slow, fast = head, head.next
Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
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.
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
res = float('inf')
curSum = 0
l = 0
for r in range(len(nums)):
curSum += nums[r]
while curSum >= target:
res = min(res, r - l + 1)
curSum -= nums[l]
l += 1
return res if res != float('inf') else 0
#O(n)
#O(1)You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.
You are given a list of strings operations, where operations[i] is the ith operation you must apply to the record and is one of the following:
An integer x.
Record a new score of x.
‘+’.
Record a new score that is the sum of the previous two scores.
‘D’.
Record a new score that is the double of the previous score.
‘C’.
Invalidate the previous score, removing it from the record.
Return the sum of all the scores on the record after applying all the operations.
The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer and that all operations are valid.
Input: ops = [“5”,”2”,”C”,”D”,”+”]
Output: 30
Explanation:
“5” - Add 5 to the record, record is now [5].
“2” - Add 2 to the record, record is now [5, 2].
“C” - Invalidate and remove the previous score, record is now [5].
“D” - Add 2 * 5 = 10 to the record, record is now [5, 10].
“+” - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.
class Solution:
def calPoints(self, operations: List[str]) -> int:
stack = []
for op in operations:
if op == "+":
stack.append(stack[-1] + stack[-2])
elif op == "D":
stack.append(2 * stack[-1])
elif op == "C":
stack.pop()
else:
stack.append(int(op))
return sum(stack)
#O(n)
#O(n)Valid Perfect Square
Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
class Solution:
def isPerfectSquare(self, num: int) -> bool:
l, r = 1, num
while l <= r:
mid = l + (r - l) // 2
squared = mid ** 2
if squared == num:
return True
elif squared > num:
r = mid - 1
else:
l = mid + 1
return False
#O(log num)
#O(1)First Missing Positive
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
#Mark negative values with a zero
for i in range(len(nums)):
if nums[i] < 0:
nums[i] = 0
#Mark idx val - 1 with a negative, if in bounds.
for i in range(len(nums)):
idx = abs(nums[i]) - 1
if idx >= 0 and idx < len(nums):
#If the target to negate is a 0, mark it as -(len(nums) + 1)
if nums[idx] == 0:
nums[idx] = -(len(nums) + 1)
else:
nums[idx] = -abs(nums[idx])
#iterate through 1... len(A) and see which one is missing. This won't go out of bounds, since this is a predefined solution set, so no need to check OOB.
for i in range(1, len(nums) + 1):
idx = i - 1
if nums[idx] >= 0:
return i
return len(nums) + 1
#Runtime: O(n)
#Space: O(1) #modify input array
# We got to the 1 dx, check if that value is NEGATIVE. If it is negative, 2 exists in the input array
But what if negative values in array?
We don't care about negative values. We'll replace them with a zero.
Solution set is bounded within [1..len(A)] Example: [123] -> 4
1) Pre-work: Iterate through the array, mark negative values with a 0. This is because we don't care about negative values at all.
# 2) Traverse through the input array, and for every val, mark slot for idx i = val - 1 as visited with a negative, if it's in bounds.
# #To account for edge cases for which a negative value was flipped to a 0, we can instead flip it to a negative value that is not
# #within [1..len(A)]. Let's do -(len(A) + 1), because index len(A) is out of bounds!
# 3) Traverse through [1... len(A)]. For each value here, check if slot for idx = val - 1 is negative. If it's non-negative, immediately return the val.
# #If the loop terminates and still not returned, return len(A) + 1.
# #Example: [123] -> [-1 -2 -3], so 4.Number of Distinct Islands
You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.
Return the number of distinct islands.
Input: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
Output: 3
Each recursive pop-up has a “B” attached to it. The total number of “B” is equal to the size of the recursion stack.. the number of cells in the island.
class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
visit = set()
uniqueIslands = set()
def dfs(r, c, direction):
if r < 0 or r == ROWS or c < 0 or c == COLS or (r, c) in visit or grid[r][c] == 0:
return
visit.add((r, c))
curPath.append(direction)
dfs(r + 1, c, "D")
dfs(r - 1, c, "U")
dfs(r, c - 1, "L")
dfs(r, c + 1, "R")
curPath.append("B") #backtracked to disambiguate
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1 and (r, c) not in visit:
curPath = []
dfs(r, c, "S") #Start
if curPath:
uniqueIslands.add(tuple(curPath))
return len(uniqueIslands)
#Runtime: O(MN) for running DFS from every island, etc.
#Space: O(MN) for visit set, and also much larger than the path signature set.
# Each recursive pop-up has a "B" attached to it. The total number of "B" is equal to the size of the recursion stack.. the number of cells in the island.
# grid =
# [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
# Output = 1
# {('START', 'D', 'R', 'U', 'B', 'B', 'B', 'B')}
[[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
# Output: 3
# {('START', 'D', 'L', 'B', 'B', 'B'), ('START', 'D', 'B', 'R', 'B', 'B'), ('START', 'R', 'B', 'B')}
Count Primes
Given an integer n, return the number of prime numbers that are strictly less than n.
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
class Solution:
def countPrimes(self, n: int) -> int:
# res = 0
# #0 and 1 are not prime, we know that.
# for num in range(2, n):
# isPrime = True
# for j in range(2, num):
# if num % j == 0:
# isPrime = False
# if isPrime:
# res += 1
# return res
if n <= 2: #0 and 1 are not prime
return 0
primes = [True] * n
primes[0] = False
primes[1] = False
#Assume prime by default
for p in range(2, int(n ** 0.5) + 1): #we don't need to go until n. At most 0 to sqrt n. So we do (sqrt n) + 1 to exclude the +1 part of it.
if primes[p]:
for multiple in range(p * p, n, p):
primes[multiple] = False
return sum(primes) #Sum up the entries in primes that are True
#Runtime: O(sqrt(n) * log log n)
#log log n is n /2 + n / 3 + n / 5 + ... + n/(last prime < n)
#Space: O(n) for primes array
Spiral Matrix II
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
res = [[0] * n for i in range(n)]
top, bot = 0, n
left, right = 0, n
curVal = 1
while top < bot and left < right:
for c in range(left, right):
res[top][c] = curVal
curVal += 1
#shift the top
top += 1
#Down the right column
for r in range(top, bot):
res[r][right - 1] = curVal
curVal += 1
#Shift the right pointer
right -= 1
if not (top < bot and left < right):
break
#Traverse the bottom
for c in range(right - 1, left - 1, -1):
res[bot - 1][c] = curVal
curVal += 1
bot -= 1
#Traverse the left column
for r in range(bot - 1, top - 1, -1):
res[r][left] = curVal
curVal += 1
left += 1
return res
#Runtime: O(n^2)
#Space: O(n^2) Replace Elements with Greatest Element on Right Side
Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.
After doing so, return the array.
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation:
- index 0 –> the greatest element to the right of index 0 is index 1 (18).
- index 1 –> the greatest element to the right of index 1 is index 4 (6).
- index 2 –> the greatest element to the right of index 2 is index 4 (6).
- index 3 –> the greatest element to the right of index 3 is index 4 (6).
- index 4 –> the greatest element to the right of index 4 is index 5 (1).
- index 5 –> there are no elements to the right of index 5, so we put -1.
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
rightMax = -1
for i in range(len(arr) - 1, -1, -1):
newMax = max(rightMax, arr[i])
arr[i] = rightMax
rightMax = newMax
return arr
#O(n)
#O(1)Is Subsequence
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Input: s = “abc”, t = “ahbgdc”
Output: true
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i, j = 0, 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
#O(max(s, t))
#O(1)
Remove Elt
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,,]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
l = 0
for r in range(len(nums)):
if nums[r] != val:
nums[l] = nums[r] #Place non-vals where l is. So first elt will swap nums[l] with itself.
l += 1
return l
#O(n)
#O(1)
Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
Input: s = “paper”, t = “title”
Output: true
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
sMapToT = {}
tMapToS = {}
for c1, c2 in zip(s, t):
if c1 in sMapToT and sMapToT[c1] != c2 or c2 in tMapToS and tMapToS[c2] != c1:
return False
sMapToT[c1] = c2
tMapToS[c2] = c1
return True
#O(len(s)) #same length
#O(26) -> O(1)Range Sum Query - Immutable
Given an integer array nums, handle multiple queries of the following type:
Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
Implement the NumArray class:
NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + … + nums[right]).
Input
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]
Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
class NumArray:
def \_\_init\_\_(self, nums: List[int]):
self.prefixSums = []
#prefixSums: the prefix include the current element too. So for i
#it's [:i + 1]
curSum = 0
for n in nums:
curSum += n
self.prefixSums.append(curSum)
def sumRange(self, left: int, right: int) -> int:
leftSum = self.prefixSums[left - 1] if left - 1 >= 0 else 0
rightSum = self.prefixSums[right]
return rightSum - leftSum
#O(1) per operation, except O(n) init
#Space: O(n) for prefixSUms
Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)Find Pivot Index
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index’s right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
totalSum = sum(nums)
prefixSum = 0
for i in range(len(nums)):
rightSum = totalSum - prefixSum - nums[i]
if prefixSum == rightSum:
return i
prefixSum += nums[i]
return -1
#O(n)
#O(1)
Majority Element
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Input: nums = [2,2,1,1,1,2,2]
Output: 2
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count, res = 0, 0
for n in nums:
if count == 0:
res = n
count += 1 if n == res else -1
return res
#O(n)
#O(1)Find All Anagrams in a String
Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Input: s = “cbaebabacd”, p = “abc”
Output: [0,6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
if len(p) > len(s):
return []
pCount = {}
sCount = {}
for i in range(len(p)):
pCount[p[i]] = pCount.get(p[i], 0) + 1
sCount[s[i]] = sCount.get(s[i], 0) + 1
l = 0
r = len(p)
res = [0] if pCount == sCount else []
while r < len(s):
sCount[s[r]] = sCount.get(s[r], 0) + 1
sCount[s[l]] -= 1 #remove left from window
if sCount[s[l]] == 0:
del sCount[s[l]]
l += 1
r += 1
if pCount == sCount:
res.append(l)
return res
#O(26*s) -> O(s)
#O(26) -> O(1)Find the Index of the First Occurrence in a String
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Input: haystack = “sadbutsad”, needle = “sad”
Output: 0
Explanation: “sad” occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return -1
#sadbutsad sad... 9 3
#last index is 6. So we want len(h) - len(n) + 1
for i in range(len(haystack) - len(needle) + 1): #since python exclusive
if haystack[i: i + len(needle)] == needle:
return i
return -1
#O(hn)
#1Valid Palindrome II
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Input: s = “aba”
Output: true
class Solution:
def validPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]: #can delete from one end of the ends once and try
skipL, skipR = s[l + 1: r + 1], s[l: r]
return skipL == skipL[::-1] or skipR == skipR[::-1]
l += 1
r -= 1
return True
#O(n) two pter
#O(n) #for skipL and skipR arraysValid Palindrome II
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Input: s = “aba”
Output: true
class Solution:
def validPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]: #can delete from one end of the ends once and try
skipL, skipR = s[l + 1: r + 1], s[l: r]
return skipL == skipL[::-1] or skipR == skipR[::-1]
l += 1
r -= 1
return True
#O(n) two pter
#O(n) #for skipL and skipR arraysMinimum Difference Between Highest and Lowest of K Scores
You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.
Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.
Return the minimum possible difference.
Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: There are six ways to pick score(s) of two students:
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
- [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
l, r = 0, k - 1
res = float('inf')
while r < len(nums):
res = min(res, nums[r] - nums[l])
l += 1
r += 1
return res
#O(n log n)
#O(1)Remove Duplicates from Sorted Array
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
l = 1
for r in range(1, len(nums)):
if nums[r] != nums[r - 1]:
nums[l] = nums[r]
l += 1
return l
#O(n)
#O(1)Contains Duplicate II
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
windowSize = k + 1
window = set()
l = 0
for r in range(len(nums)):
if r - l + 1 > windowSize:
window.remove(nums[l])
l += 1
if nums[r] in window:
return True
window.add(nums[r])
return False
#O(n)
#O(k) for the windowMaximum Number of Balloons
Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.
You can use each character in text at most once. Return the maximum number of instances that can be formed.
Input: text = “loonbalxballpoon”
Output: 2
class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
charMap = {}
for c in text:
charMap[c] = charMap.get(c, 0) + 1
balloonMap = {}
for c in "balloon":
balloonMap[c] = balloonMap.get(c, 0) + 1
res = float('inf')
for c in balloonMap:
if c not in charMap:
return 0
res = min(res, charMap[c] // balloonMap[c])
return res
#O(n)
#O(26) -> O(1)Word Pattern
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s
Input: pattern = “abba”, s = “dog cat cat dog”
Output: true
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split(" ") #split on empty space
if len(words) != len(pattern):
return False
charToWord = {}
wordToChar = {}
for c, word in zip(pattern, words):
if (c in charToWord and charToWord[c] != word) or (word in wordToChar and wordToChar[word] != c):
return False
wordToChar[word] = c
charToWord[c] = word
return True
#O(n + m) #pattern and s #m is total number of chars in s
#O(n + m). We need to split and create words still.Encode and Decode TinyURL
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL.
There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
Implement the Solution class:
Solution() Initializes the object of the system.
String encode(String longUrl) Returns a tiny URL for the given longUrl.
String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.
Input: url = “https://leetcode.com/problems/design-tinyurl”
Output: “https://leetcode.com/problems/design-tinyurl”
Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after deconding it.
class Codec:
def \_\_init\_\_(self):
self.encodeMap = {}
self.decodeMap = {}
self.domain = "tinyurl.com/"
def encode(self, longUrl: str) -> str:
"""Encodes a URL to a shortened URL.
"""
if not longUrl in self.encodeMap:
shortUrl = self.domain + str(len(self.encodeMap) + 1)
self.encodeMap[longUrl] = shortUrl
self.decodeMap[shortUrl] = longUrl
return self.encodeMap[longUrl]
def decode(self, shortUrl: str) -> str:
"""Decodes a shortened URL to its original URL.
"""
return self.decodeMap[shortUrl]
#Runtime: O(1)
#Space: O(n) where n is basically the number of urls. We can encode 10 ^ number of digits urls.
Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))Best Time to Buy and Sell Stock II
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] - prices[i - 1] > 0:
profit += prices[i] - prices[i - 1]
return profit
#O(n)
#O(1)Remove K Digits
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
Input: num = “1432219”, k = 3
Output: “1219”
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
#examples: [12345] #we remove 345
#Examples: [54321] #We remove 543
#So the idea is that we WANT our stack to be monotonically increasing. If we ever encounter a violation, we remove it
#Example: 1432219.
#We remove the 4, 3, 2 from 12219
stack = []
for n in num:
while k > 0 and stack and stack[-1] > n:
k -= 1
stack.pop()
stack.append(n)
#If haven't finished using up our k removals, then remove from the end, since we know stack is definitely monotonically increasing.
stack = stack[:len(stack) - k] #if k is 0, then :len(stack) is fine
#We also don't want leading zeroes.
res = "".join(stack)
return str(int(res)) if res else "0" #if empty, return 0
#convert to int to remove leading 0s, then back to a string
#O(n)
#O(n)
Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
l, r = 0, len(nums) - 1
res = []
while l <= r:
#we want the bigger values to go into the array first, then we reverse it.
leftSquared = nums[l] ** 2
rightSquared = nums[r] ** 2
if leftSquared >= rightSquared:
res.append(leftSquared)
l += 1
else:
res.append(rightSquared)
r -= 1
return res[::-1]
#O(n)
#O(n) for answerIntersection of Two Linked Lists
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
l1, l2 = headA, headB
while l1 != l2:
l1 = l1.next if l1 else headB
l2 = l2.next if l2 else headA
#Two exit conditions: 1) They reach intersection
#If they don't cross, both will be None
#The coniditions inside is if l1 and if l2, not if l1.next and if l2.next
return l1
#O(l1 + l2)
#O(1)Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, curSum):
if not node: #if no node, then that is False
return False
curSum += node.val
if not node.left and not node.right: #If it's a leaf, we will return before the if not node check to return False is triggered.
return curSum == targetSum
return dfs(node.left, curSum) or dfs(node.right, curSum)
return dfs(root, 0)
#O(N)
#O(h) Remove All Adjacent Duplicates in String II
You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.
Input: s = “deeedbbcccbdaa”, k = 3
Output: “aa”
Explanation:
First delete “eee” and “ccc”, get “ddbbbdaa”
Then delete “bbb”, get “dddaa”
Finally delete “ddd”, get “aa”
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = [] #(character, counts)
for c in s:
if stack and stack[-1][0] == c:
stack[-1][1] += 1
else:
stack.append([c, 1])
if stack[-1][1] == k:
stack.pop()
res = ""
for c, count in stack:
res += count * c
return res
#O(n)
#O(n)
#THEME: StackConvert Sorted Array to Binary Search Tree
Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced binary search tree.
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def dfs(l, r):
if l > r:
return None
m = l + (r - l) // 2
root = TreeNode(nums[m])
root.left = dfs(l, m - 1)
root.right = dfs(m + 1, r)
return root
return dfs(0, len(nums) - 1)
#Runtime: O(n)
#Space: O(h)
#Theme: Trees, DFSMerge Two Binary Trees
You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1 and not root2:
return None
if root1 and not root2:
return root1
if not root1 and root2:
return root2
root = TreeNode(root1.val + root2.val)
root.left = self.mergeTrees(root1.left, root2.left)
root.right = self.mergeTrees(root1.right, root2.right)
return root
#Runtime: O(n + m)
#Space: O(min(h1, h2))
#Theme: DFSBinary Search Tree Iterator
Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):
BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.
Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.
You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.
Input
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]
Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False
# 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 BSTIterator:
def \_\_init\_\_(self, root: Optional[TreeNode]):
self.stack = []
cur = root
while cur:
self.stack.append(cur)
cur = cur.left
def next(self) -> int:
resNode = self.stack.pop()
cur = resNode.right
while cur:
self.stack.append(cur)
cur = cur.left
return resNode.val
def hasNext(self) -> bool:
return len(self.stack) > 0
#Runtime: O(1) avg time
#Space: O(h) memory for stack
#Theme: Iterative IOT
Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()Maximum Number of Removable Characters
You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).
You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.
Return the maximum k you can choose such that p is still a subsequence of s after the removals.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Input: s = “abcacb”, p = “ab”, removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, “abcacb” becomes “accb”.
“ab” is a subsequence of “accb”.
If we remove the characters at indices 3, 1, and 0, “abcacb” becomes “ccb”, and “ab” is no longer a subsequence.
Hence, the maximum k is 2.
class Solution:
def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
def isSubsequence(s, subseq):
i, j = 0, 0
while i < len(s) and j < len(subseq):
if i in removed or s[i] != subseq[j]:
i += 1
else:
i += 1
j += 1
return j == len(subseq)
res = 0 #number of removable chars
l, r = 0, len(removable) - 1
while l <= r:
m = l + (r - l) // 2
removed = set(removable[: m + 1]) #we removed everything up to m inclusive
if isSubsequence(s, p):
res = max(res, m + 1) #m is index, res we want the number of characters
l = m + 1
else:
r = m - 1
return res
#Runtime: O(n log r) #where r is length of removable
#Space: O(n) The size of the remove set.
#Theme: Subsequences, Binary SearchBrick Wall
There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.
Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.
Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.
Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2
class Solution:
def leastBricks(self, wall: List[List[int]]) -> int:
gaps = {} #Maps the gap to the count of those gaps
#Minimum number of crossed bricks is when the number of gaps is maximized.
for line in wall:
xPos = 0
for b in line[:-1]: #ignore the last brick. We don't count the rightmost edge as a gap
xPos += b
gaps[xPos] = gaps.get(xPos, 0) + 1
maxGaps = max(gaps.values()) if gaps else 0
return len(wall) - maxGaps
#Runtime: O(n) for the total number of bricks
#Space: O(width) for the gaps.
Unique Email Addresses
Every valid email consists of a local name and a domain name, separated by the ‘@’ sign. Besides lowercase letters, the email may contain one or more ‘.’ or ‘+’.
For example, in “alice@leetcode.com”, “alice” is the local name, and “leetcode.com” is the domain name.
If you add periods ‘.’ between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. Note that this rule does not apply to domain names.
For example, “alice.z@leetcode.com” and “alicez@leetcode.com” forward to the same email address.
If you add a plus ‘+’ in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered. Note that this rule does not apply to domain names.
For example, “m.y+name@email.com” will be forwarded to “my@email.com”.
It is possible to use both of these rules at the same time.
Given an array of strings emails where we send one email to each emails[i], return the number of different addresses that actually receive mails.
Input: emails = [“test.email+alex@leetcode.com”,”test.e.mail+bob.cathy@leetcode.com”,”testemail+david@lee.tcode.com”]
Output: 2
Explanation: “testemail@leetcode.com” and “testemail@lee.tcode.com” actually receive mails.
class Solution:
def numUniqueEmails(self, emails: List[str]) -> int:
unique = set()
for email in emails:
local, domain = email.split('@')
#ignore the "+" in the local name
local = local.split('+')[0]
#ignore dots too in local
local = local.replace(".", "")
unique.add((local, domain))
return len(unique)
#O(n)
#O(n)House Robber III
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.
Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
# 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 rob(self, root: Optional[TreeNode]) -> int:
#returns 2 values (withRoot, withoutRoot)
def dfs(root):
if not root:
return [0, 0]
leftWithRoot, leftWithoutRoot = dfs(root.left)
rightWithRoot, rightWithoutRoot = dfs(root.right)
withRoot = root.val + leftWithoutRoot + rightWithoutRoot
withoutRoot = max(leftWithRoot, leftWithoutRoot) + max(rightWithRoot, rightWithoutRoot)
return [withRoot, withoutRoot]
return max(dfs(root))
#O(n)
#O(h)
#DFS but return two values
Range Sum Query 2D - Immutable
Given a 2D matrix matrix, handle multiple queries of the following type:
Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Implement the NumMatrix class:
NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
You must design an algorithm where sumRegion works on O(1) time complexity.
Input
[“NumMatrix”, “sumRegion”, “sumRegion”, “sumRegion”]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]
Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)
class NumMatrix:
def \_\_init\_\_(self, matrix: List[List[int]]):
ROWS, COLS = len(matrix), len(matrix[0])
self.prefixSums = [[0] * (COLS + 1) for r in range(ROWS + 1)]
#We will pad the top and the left with zeroes to make our lives easier and avoid edges cases
#any r c in matrix is remapped to r + 1, c + 1 in prefixSums.
for r in range(ROWS):
rowPrefix = 0
for c in range(COLS):
rowPrefix += matrix[r][c]
above = self.prefixSums[r][c + 1] #one row above in the output array.
self.prefixSums[r + 1][c + 1] = rowPrefix + above
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
#Let's just remap this since we only need to use the prefixSums indices
row1, col1, row2, col2 = row1 + 1, col1 + 1, row2 + 1, col2 + 1
bottomRight = self.prefixSums[row2][col2]
left = self.prefixSums[row2][col1 - 1]
top = self.prefixSums[row1 - 1][col2]
topLeft = self.prefixSums[row1 - 1][col1 - 1]
return bottomRight - left - top + topLeft
#Runtime: O(mn) for init, O(1) each subsequent operation
#Space: O(mn) for the prefixSums 2D matrix
Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)Count Odd Numbers in an Interval Range
Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).
Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].
class Solution:
def countOdds(self, low: int, high: int) -> int:
# 3 to 7: 5 numbers in this range, 3 5 7 odd. Therefore, it's 5 // 2 + 1 = 3 odd numbers. The 1 comes from an odd endpoint
# 2 to 6: 5 numbers in this range, 3 5 odd. Therefore it's 5 // 2 = 2 odd numbers
#1 to 4: 4 numbers in this range, 1 3 odd. 4 // 2 = 2 odds
#2 to 5: 4 numbers in this range, 3 5 odd. 4 // 2 = 2 odds
#So the rule is:
#We always do the size // 2
#If it's odd length, and if endpoint has an odd number, we add 1 to it.
intervalLength = high - low + 1
res = intervalLength // 2
#Add 1 if odd interval length and an endpoint is odd
if intervalLength % 2 and low % 2:
res += 1
return res
#O(1)
#O(1)Insert into a Binary Search Tree
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:
# 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 insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return root
#Runtime: O(h)
#Space: O(h)Delete Node in a BST
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it’s also accepted.
# 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 deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
#1) Find the node
if key < root.val:
#recursively find and delete
root.left = self.deleteNode(root.left, key)
elif key > root.val:
#recursively find and delete
root.right = self.deleteNode(root.right, key)
else:
#We found the value. Do different things based on number of children
#2a) 1 child cases
#If no left child, return right child. This is either populated right or None
if not root.left:
return root.right
#If no right child, return left child. Left is either populated left or None
elif not root.right:
return root.left
#2b) 2 children cases. If here, left and right are both populated
#The goal is to swap the minimum in the right subtree with the root
#then recursively delete downwards from here as well.
else:
#3) Find the minimum node in the right subtree by keep going left
cur = root.right
while cur.left:
cur = cur.left
root.val = cur.val #set root to this minimum value
#4) Recursively delete that min val from the right subtree
root.right = self.deleteNode(root.right, root.val) #baroot.val same as cur.val here
return root
#Runtime: O(h)
#Space: O(h)Longest Turbulent Subarray
Given an integer array arr, return the length of a maximum size turbulent subarray of arr.
A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
More formally, a subarray [arr[i], arr[i + 1], …, arr[j]] of arr is said to be turbulent if and only if:
For i <= k < j:
arr[k] > arr[k + 1] when k is odd, and
arr[k] < arr[k + 1] when k is even.
Or, for i <= k < j:
arr[k] > arr[k + 1] when k is even, and
arr[k] < arr[k + 1] when k is odd.
Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
res, prev = 1, ""
l, r = 0, 1
while r < len(arr):
if arr[r - 1] > arr[r] and prev != ">":
res = max(res, r - l + 1)
r += 1
prev = ">"
elif arr[r - 1] < arr[r] and prev != "<":
res = max(res, r - l + 1)
r += 1
prev = "<"
else:
prev = "" #Just put prev as whatever since we're essentially starting a new sequence in either case.
#If equal
# L R
#Example 7 8 8 1
# L R
#If unequal
# R
#Example 7 8 9 1
# L R
r = r + 1 if arr[r] == arr[r - 1] else r
l = r - 1
return res
#O(n)
#O(1)Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = ""
for i in range(len(strs[0])):
for s in strs:
if i == len(s) or s[i] != strs[0][i] :
return res
res += strs[0][i]
return res
#Runtime: O(number of strings *length of shortest string)
#Space: O(1)Remove Linked List Elements
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Definition for singly-linked list.
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
cur = dummy
while cur:
while cur.next and cur.next.val == val:
cur.next = cur.next.next
cur = cur.next
return dummy.next
# dummy = ListNode(0, head)
# prev, cur = dummy, head
# while cur:
# nxt = cur.next
# if cur.val == val:
# prev.next = nxt
# else:
# prev = cur
# cur = cur.next #cur moves to next value
# return dummy.next
#O(N)
#O(1)
Palindrome Linked List
Given the head of a singly linked list, return true if it is a
palindrome
or false otherwise.
Input: head = [1,2,2,1]
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
#slow is at the second half
#Reverse the second half
prev = None
cur = slow
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
left, right = head, prev
#The condition is while right, because at some point right will point at None when we cut it off at the point. Left we never cut off the last pointer!
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
#O(n)
#O(1)Length of Last Word
Given a string s consisting of words and spaces, return the length of the last word in the string.
A word is a maximal
substring
consisting of non-space characters only.
Input: s = “ fly me to the moon “
Output: 4
Explanation: The last word is “moon” with length 4.
class Solution:
def lengthOfLastWord(self, s: str) -> int:
return len(s.split()[-1])
#O(n)
#O(n) for splitting
#s = " fly me to the moon "
#print(s.split()) #['fly', 'me', 'to', 'the', 'moon']
#Splits on whitespace, so leading and trailing whitespaces also resolved.
Find All Numbers Disappeared in an Array
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
res = []
for i in range(len(nums)):
idx = abs(nums[i]) - 1
nums[idx] = -abs(nums[idx])
for i in range(len(nums)):
if nums[i] > 0:
res.append(i + 1)
return res
#O(n)
#O(n)
#This is used in first missing positive basically. Same idea.Maximal Square
Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
Output: 4
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
ROWS, COLS = len(matrix), len(matrix[0])
dp = [[0] * (COLS + 1) for r in range(ROWS + 1)]
maxSideLength = 0
#What is the side length of the largest square we can make with dp[r][c] as the top left corner?
for r in range(ROWS - 1, -1, -1):
for c in range(COLS - 1, -1, -1):
if matrix[r][c] == "1":
dp[r][c] = 1 + min(dp[r][c + 1], dp[r + 1][c], dp[r + 1][c + 1])
maxSideLength = max(maxSideLength, dp[r][c])
return maxSideLength ** 2
#Runtime: O(mn)
#Space: O(mn)Add to Array-Form of Integer
The array-form of an integer num is an array representing its digits in left to right order.
For example, for num = 1321, the array form is [1,3,2,1].
Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.
Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234
class Solution:
def addToArrayForm(self, num: List[int], k: int) -> List[int]:
num.reverse()
i = 0
while k:
digit = k % 10
if i < len(num):
num[i] += digit
else:
num.append(digit)
carry = num[i] // 10
num[i] = num[i] % 10
k = k // 10
k += carry
i += 1
num.reverse()
return num
#Runtime: O(max(num, k))
#Space: O(max(num, k))Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
You must solve it in O(n) time complexity.
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
k = len(nums) - k
def quickSelect(l, r):
p, pivot = l, nums[r]
for i in range(l, r):
if nums[i] <= pivot:
nums[i], nums[p] = nums[p], nums[i]
p += 1
nums[p], nums[r] = nums[r], nums[p]
if p == k:
return nums[k]
elif p < k:
return quickSelect(p + 1, r)
else:
return quickSelect(l, p - 1)
return quickSelect(0, len(nums) - 1)
#Runtime: O(n) average O(n^2) worst case
#Space: O(1)
#Notes: pivot comparison is <=, not <
#Notes: don't reassign k on every recursive call. Make sure it's done outside the recursive call.
#Define an outer function find kth largest next time, before the recrusive quickSelect(l, r).Number of Sub-arrays of Size K and Average Greater than or Equal to Thre
Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
curSum = sum(arr[:k - 1]) # k = 3, sum up 0 1 to start
l = 0
res = 0
for r in range(k - 1, len(arr)):
curSum += arr[r]
if curSum / k >= threshold:
res += 1
curSum -= arr[l]
l += 1
return res
#O(n)
#O(1)Sort an Array
Given an array of integers nums, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def merge(arr, l, r, m):
left = arr[l: m + 1]
right = arr[m + 1: r + 1]
i, j, k = l, 0, 0
while j < len(left) and k < len(right):
if left[j] <= right[k]:
arr[i] = left[j]
j += 1
else:
arr[i] = right[k]
k += 1
i += 1
while j < len(left):
arr[i] = left[j]
j += 1
i += 1
while k < len(right):
arr[i] = right[k]
k += 1
i += 1
#Need an extra arr variable since things change
def mergeSort(arr, l, r):
if l == r:
return arr
m = l + (r - l) // 2
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
merge(arr, l, r, m)
return arr
return mergeSort(nums, 0, len(nums) - 1)
#Runtime: O(n log n)
#Space: O(n)Fruit Into Baskets
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
fruitMap = defaultdict(int)
l = 0
res = 0
for r in range(len(fruits)):
fruitMap[fruits[r]] += 1
while len(fruitMap) > 2:
f = fruits[l]
fruitMap[f] -= 1
if fruitMap[f] == 0:
del fruitMap[f]
l += 1
res = max(res, r - l + 1)
return res
#O(n)
#O(2 keys) -> O(1)
#Basically.. What is the length of the longest sliding window such that the number of keys that we have is less than or
#equal to 2?Path with Maximum Probability
You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].
Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.
If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
adj = defaultdict(list)
for i in range(len(edges)):
u, v = edges[i]
adj[u].append((v, succProb[i]))
adj[v].append((u, succProb[i]))
minHeap = [(-1, start)] #(the probability, node)
visit = set()
while minHeap:
prob, node = heapq.heappop(minHeap)
if node in visit:
continue
visit.add(node)
if node == end:
return -1 * prob
for neiNode, edgeProb in adj[node]:
if neiNode not in visit:
newProb = prob * edgeProb
heapq.heappush(minHeap, (newProb, neiNode))
return 0
#Runtime: O(E log V) -> O(V^2 log V)
#Space: O(V + E) -> O(V^2)
Remove Duplicates from Sorted Array II
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
l = 0
#l indicates the spot that the next number shold go. Everything before l is
#considered valid!
r = 0
while r < len(nums):
count = 1
#Goal is to reach the final element of the current streak.
while r + 1 < len(nums) and nums[r] == nums[r + 1]:
count += 1
r += 1
#Replace, starting from index l, the number of elts of the current streak. At most 2. This is copied over from nums[r]
for i in range(min(count, 2)):
nums[l] = nums[r]
l += 1
#We're done with the streak. Increment r so that we are on our new streak.
r += 1
return l
#Runtime: O(n)
#Space: O(1)Continuous Subarray Sum
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
its length is at least two, and
the sum of the elements of the subarray is a multiple of k.
Note that:
A subarray is a contiguous part of the array.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
remainders = {0: -1} #remainder, endIndex (inclusive for that remainder)
curSum = 0
for i, n in enumerate(nums):
curSum += n
remainder = curSum % k
if remainder not in remainders:
remainders[remainder] = i
#Explanation. If previously you had a sum with remainder r,
# and now you again have a new sum of remainder r, that means that
# the difference between oldSum and newSum must be a multiple of k.
# Therefore, the sbuarray in between is a multiple of k
# Has to be at least gap of 2.
#Example:
#24 2 4 6 7, k = 6
#23 has a remainder of 5, at index 0
#29 has a remainder of 5, at index 2
#Since there is a gap of length 2 - 0 = 2, 2 + 4 = 6 is a valid subarray
elif i - remainders[remainder] > 1:
return True
return False
#Runtime: O(n)
#Space: O(n)Last Stone Weight II
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that’s the optimal value.
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
dp = {} # maps (i, curSum) -> smallest remaining stone weight from this point on as a result of subsequent calls
stonesSum = sum(stones)
target = ceil(stonesSum / 2)
def dfs(i, curSum):
#Why >= target? If target, definitely return. If >, we can't get closer to
#the target anymore as a result of increments so return remainingWeight for this
if curSum >= target or i == len(stones):
secondPileSum = stonesSum - curSum
#Why abs? If in the case i == len(stones) and first pile is
#less than second pile in weight, it'll be negative
remainingWeight = abs(curSum - secondPileSum)
return remainingWeight
if (i, curSum) in dp:
return dp[(i, curSum)]
#The result of (i, curSum) is the minimum of results from this point on as a result of subsequent calls. To include or not include
dp[(i, curSum)] = min(dfs(i + 1, curSum + stones[i]), dfs(i + 1, curSum))
return dp[(i, curSum)]
return dfs(0, 0)
#Runtime: O(n * sum(stones))
#Space: O(n * sum(stones)) #for dp mapReverse Linked List II
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
leftPrev = dummy
cur = head
#1) Go to the left position. If left is 2nd and we start
#at 1st node, we only go once. So from range(0, 1):
for i in range(left - 1):
leftPrev = cur
cur = cur.next
#2)Reverse from left to right. How many iterations?
#left = 2, right = 4. So we reverse nodes at
#index 2, 3, and 4. So 4 - 2 + 1 times # 0, 1, 2
prev = None
for i in range(right - left + 1):
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
#3) Point the new final node to the node after right. That is at cur.
leftPrev.next.next = cur
#4) Point the leftPrev's next to the beginning of the reversed list. That is at prev
leftPrev.next = prev
return dummy.next
#O(n)
#O(1)
Partition List
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
dummy1, dummy2 = ListNode(), ListNode()
tail1, tail2 = dummy1, dummy2
while head:
if head.val < x:
tail1.next = head
tail1 = tail1.next
else:
tail2.next = head
tail2 = tail2.next
head = head.next
#Point end of first list to second list
tail1.next = dummy2.next
#Ensure end of second list points to None
tail2.next = None
return dummy1.next
#O(n)
#O(1)Largest Number
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.
Input: nums = [10,2]
Output: “210”
class Solution:
def largestNumber(self, nums: List[int]) -> str:
nums = list(map(str, nums))
def compare(n1, n2):
num1, num2 = n1 + n2, n2 + n1
if num1 > num2:
return -1
elif num2 < num1:
return 1
else:
return 0
nums.sort(key = cmp_to_key(compare))
return str(int("".join(nums))) #do this to map "0000" -> "0"
#Runtime: O(n log n) for sorting
#Space: O(n) needed for sorting probably
Maximum Twin Sum of a Linked List
In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.
For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
The twin sum is defined as the sum of a node and its twin.
Given the head of a linked list with even length, return the maximum twin sum of the linked list.
Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def pairSum(self, head: Optional[ListNode]) -> int:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
#Slow is at the second half of the list. Begin reversing!
prev = None
cur = slow
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
#prev is at the final node of the linked list
left, right = head, prev
res = 0
while left and right:
res = max(res, left.val + right.val)
left = left.next
right = right.next
return res
#O(n)
#O(1)Simplify Path
Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.
In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.
The canonical path should have the following format:
The path starts with a single slash ‘/’.
Any two directories are separated by a single slash ‘/’.
The path does not end with a trailing ‘/’.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘.’ or double period ‘..’)
Return the simplified canonical path.
Input: path = “/home//foo/”
Output: “/home/foo”
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for portion in path.split('/'):
if portion == "..":
if stack:
stack.pop()
elif not portion or portion == ".":
#not portion means empty, which is possible if
#print("//".split("/")) becomes ['', '', '']
continue
else:
stack.append(portion)
return "/" + "/".join(stack)
#Runtime: O(n)
#Space: O(n)Online Stock Span
Design an algorithm that collects daily price quotes for some stock and returns the span of that stock’s price for the current day.
The span of the stock’s price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.
For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.
Implement the StockSpanner class:
StockSpanner() Initializes the object of the class.
int next(int price) Returns the span of the stock’s price given that today’s price is price.
Input
[“StockSpanner”, “next”, “next”, “next”, “next”, “next”, “next”, “next”]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]
Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today’s price of 75) were less than or equal to today’s price.
stockSpanner.next(85); // return 6
class StockSpanner:
def \_\_init\_\_(self):
self.stack = [] #(span, price)
def next(self, price: int) -> int:
span = 1
while self.stack and self.stack[-1][1] <= price:
#The idea is that: if the price of stack top is less than price,
#and it has some span, then the span would contribute to the
#new price that we're adding. That information becomes combined
span += self.stack.pop()[0]
self.stack.append((span, price))
return span
#Runtime: O(n) potentially look back at every elt
#Space: O(n) for the stack
Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)Find the Kth Largest Integer in the Array
You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.
Return the string that represents the kth largest integer in nums.
Note: Duplicate numbers should be counted distinctly. For example, if nums is [“1”,”2”,”2”], “2” is the first largest integer, “2” is the second-largest integer, and “1” is the third-largest integer
Input: nums = [“3”,”6”,”7”,”10”], k = 4
Output: “3”
Explanation:
The numbers in nums sorted in non-decreasing order are [“3”,”6”,”7”,”10”].
The 4th largest integer in nums is “3”.
class Solution:
def kthLargestNumber(self, nums: List[str], k: int) -> str:
#Largest, so we need maxHeap
maxHeap = [-int(n) for n in nums]
heapq.heapify(maxHeap)
#Can also do quicksort but ehh...
while k > 1: #pop from the heap k - 1 times
heapq.heappop(maxHeap)
k -= 1
return str(-maxHeap[0])
#Runtime: O(k log n)
#Space: O(n) for maxHeapN-Queens II
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.
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
class Solution:
def totalNQueens(self, n: int) -> int:
res = 0
cols = set()
posDiag = set() #r + c
negDiag = set() # r - c
def backtrack(r):
if r == n:
nonlocal res
res += 1
return
for c in range(n):
if c in cols or r + c in posDiag or r - c in negDiag:
continue
#Place the queen here
cols.add(c)
posDiag.add(r + c)
negDiag.add(r - c)
backtrack(r + 1)
#Remove the queens
cols.remove(c)
posDiag.remove(r + c)
negDiag.remove(r - c)
backtrack(0)
return res
#Runtime: O(n!)
#Space: O(n) for recursion stack
Shortest Path in Binary Matrix
Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
N = len(grid)
#Technically not needed since the for loop will do nothing if it's a 1.
if grid[0][0] == 1:
return -1
q = deque() #(r, c, pathLength)
q.append((0, 0, 1))
visit = set()
visit.add((0, 0))
directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
while q:
for _ in range(len(q)):
r, c, curLength = q.popleft()
if r == N - 1 and c == N - 1:
return curLength
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
if neiR >= 0 and neiR < N and neiC >= 0 and neiC < N and (neiR, neiC) not in visit and grid[neiR][neiC] == 0:
q.append((neiR, neiC, curLength + 1))
visit.add((neiR, neiC))
return -1
#Runtime: O(MN)
#Space: O(MN)Maximum Points You Can Obtain from Cards
There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.
In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.
Your score is the sum of the points of the cards you have taken.
Given the integer array cardPoints and the integer k, return the maximum score you can obtain.
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
#r will be the first element we will DELETE when we slide
l, r = 0, len(cardPoints) - k
curSum = sum(cardPoints[r:])
res = curSum #res is at least curSum to start.
while r < len(cardPoints):
curSum -= cardPoints[r]
curSum += cardPoints[l]
res = max(res, curSum)
l += 1
r += 1
return res
#O(n) #sliding window
#O(1)Shift 2D Grid
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.
In one shift operation:
Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].
Return the 2D grid after applying shift operation k times.
grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
class Solution:
def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
ROWS, COLS = len(grid), len(grid[0])
res = [[0] * COLS for r in range(ROWS)]
def posToIdx(r, c):
return r * COLS + c
def idxToPos(idx):
return idx // COLS, idx % COLS
for r in range(ROWS):
for c in range(COLS):
idx = posToIdx(r, c)
idx = (idx + k) % (ROWS * COLS)
newR, newC = idxToPos(idx)
res[newR][newC] = grid[r][c]
return res
#O(MN)
#O(MN)Triangle
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp = [0] * (len(triangle) + 1)
for r in range(len(triangle) - 1, -1, -1):
for c in range(len(triangle[r])):
#bottom is at dp[c]. Bottom right is dp[c + 1]
dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])
return dp[0]
#Runtime: O(n^2) runtime: n rows, each at most length n
#Space: O(n) - longest side length
