N-All Flashcards
1
Q
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.
A
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)
2
Q
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.
A
# 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.
3
Q
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)
A
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) pointers
4
Q
Given 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.
A
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 cache
5
Q
You 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]
A
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)
6
Q
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
A
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 map
7
Q
We 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.
A
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)
8
Q
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
A
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.
9
Q
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
A
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.
10
Q
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
A
# 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)
11
Q
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”
A
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 stack
12
Q
Design 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]]
A
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)
13
Q
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]
A
# 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)
14
Q
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
A
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 - 1
15
Q
Remove 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]
A
# 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)
16
Q
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.
A
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)
17
Q
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.
A
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)
18
Q
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.
A
# 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
19
Q
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.
A
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)
20
Q
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.
A
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)
21
Q
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.
A
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)
22
Q
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.
A
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.
23
Q
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
A
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')}
24
Q
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.
A
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
25
# Spiral Matrix II
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
## Footnote
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)
```
26
# 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.
## Footnote
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)
```
27
# 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).
## Footnote
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)
```
28
# 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.
## Footnote
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)
```
29
# 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.
## Footnote
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)
```
30
# 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]).
## Footnote
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)
```
31
# 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.
## Footnote
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)
```
32
# 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.
## Footnote
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)
```
33
# 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.
## Footnote
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)
```
34
# 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.
## Footnote
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)
#1
```
35
# Valid Palindrome II
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
## Footnote
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 arrays
```
36
# Valid Palindrome II
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
## Footnote
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 arrays
```
37
# Minimum 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.
## Footnote
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)
```
38
# 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.
## Footnote
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)
```
39
# 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.
## Footnote
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 window
```
40
# Maximum 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.
## Footnote
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)
```
41
# 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
## Footnote
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.
```
42
# 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.
## Footnote
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))
```
43
# 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.
## Footnote
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)
```
44
# 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.
## Footnote
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)
```
45
# 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.
## Footnote
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 answer
```
46
# Intersection 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)
```
47
# 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.
## Footnote
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)
```
48
# 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.
## Footnote
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: Stack
```
49
# Convert 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.
## Footnote
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, DFS
```
50
# Merge 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.
## Footnote
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: DFS
```
51
# Binary 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.
## Footnote
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()
```
52
# 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.
## Footnote
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 Search
```
53
# Brick 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.
## Footnote
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.
```
54
# 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.
## Footnote
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)
```
55
# 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.
## Footnote
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
```
56
# 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.
## Footnote
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)
```
57
# 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).
## Footnote
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)
```
58
# 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.
## Footnote
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)
```
59
# 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.
## Footnote
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)
```
60
# 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.
## Footnote
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)
```
61
# 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 "".
## Footnote
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)
```
62
# 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.
## Footnote
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)
```
63
# Palindrome Linked List
Given the head of a singly linked list, return true if it is a
palindrome
or false otherwise.
## Footnote
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)
```
64
# 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.
## Footnote
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.
```
65
# 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.
## Footnote
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.
```
66
# 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.
## Footnote
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)
```
67
# 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.
## Footnote
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))
```
68
# 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.
## Footnote
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).
```
69
# 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.
## Footnote
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)
```
70
# 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
## Footnote
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)
```
71
# 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.
## Footnote
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?
```
72
# 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.
## Footnote
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)
```
73
# 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.
## Footnote
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)
```
74
# 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.
## Footnote
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)
```
75
# 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.
## Footnote
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 map
```
76
# Reverse 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.
## Footnote
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)
```
77
# 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.
## Footnote
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)
```
78
# 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.
## Footnote
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
```
79
# 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.
## Footnote
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)
```
80
# 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.
## Footnote
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)
```
81
# 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.
## Footnote
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)
```
82
# 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
## Footnote
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 maxHeap
```
83
# N-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.
## Footnote
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
```
84
# 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.
## Footnote
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)
```
85
# 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.
## Footnote
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)
```
86
# 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.
## Footnote
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)
```
87
# 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.
## Footnote
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
```
88
# Maximum Frequency Stack
Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.
Implement the FreqStack class:
FreqStack() constructs an empty frequency stack.
void push(int val) pushes an integer val onto the top of the stack.
int pop() removes and returns the most frequent element in the stack.
If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.
## Footnote
Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]
Explanation
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
```
class FreqStack:
def __init__(self):
self.counts = {} #maps val to count
self.stacks = {} #maps count to all vals that have that count. These are in groups. For example: 1:[2], 2:[2] if 2 appears twice
self.maxCount = 0
def push(self, val: int) -> None:
valCount = self.counts.get(val, 0) + 1
self.counts[val] = valCount
if valCount > self.maxCount:
self.maxCount = valCount
self.stacks[valCount] = []
self.stacks[valCount].append(val)
def pop(self) -> int:
res = self.stacks[self.maxCount].pop()
self.counts[res] -= 1
if not self.stacks[self.maxCount]:
self.maxCount -= 1
return res
#Runtime: O(n)
#Space: O(n)
Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
```
89
# Reverse String
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
## Footnote
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
```
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
l, r = 0, len(s) - 1
while l <= r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
return s
#O(n)
#O(1)
#Instead of return s[::-1]
```
90
# Move Zeroes
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
## Footnote
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
```
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
#The idea is to move non-zeroes to the beginning (and swap whatever was in l to where r was)
l = 0
for r in range(len(nums)):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
return nums
#O(n)
#O(1)
```
91
# Frequency of the Most Frequent Element
The frequency of an element is the number of times it occurs in an array.
You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.
Return the maximum possible frequency of an element after performing at most k operations.
## Footnote
Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.
```
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
#Because we can increment values, we want elts to be next to each other as closely as possible. The window size is the frequency of elements
l = 0
total = 0
res = 0
for r in range(len(nums)):
total += nums[r]
#If the windowSize * nums[r] is greater than
#the maximum allowance we can possibly get with
#total + k:
while (r - l + 1) * nums[r] > total + k:
total -= nums[l]
l += 1
res = max(res, r - l + 1)
return res
#O(n log n) for sorting
#O(1)
```
92
# Implement Stack using Queues
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement the MyStack class:
void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.
Notes:
You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.
## Footnote
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
```
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x: int) -> None:
self.q.append(x)
def pop(self) -> int:
#Push everything but the last elt from the q into the back
for i in range(len(self.q) - 1):
self.push(self.q.popleft())
#pop off the last elt
return self.q.popleft()
def top(self) -> int:
#Push everything but the last elt from the q into the back
for i in range(len(self.q) - 1):
self.push(self.q.popleft())
#Be able to access the elt on the top of the stack
res = self.q[0]
#Revert back to original order, so we move the front elt to the back again
self.push(self.q.popleft())
return res
def empty(self) -> bool:
return len(self.q) == 0
#Runtime: O(n) for pop and top, O(1) for push
#Space: O(n) for the q
Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
```
93
# Guess Number Higher or Lower
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
-1: Your guess is higher than the number I picked (i.e. num > pick).
1: Your guess is lower than the number I picked (i.e. num < pick).
0: your guess is equal to the number I picked (i.e. num == pick).
Return the number that I picked.
## Footnote
Input: n = 10, pick = 6
Output: 6
```
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
# 1 if num is lower than the picked number
# otherwise return 0
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
l, r = 1, n
while l <= r:
m = l + (r - l) // 2
myGuess = guess(m) #api call once.
if myGuess == -1:
r = m - 1
elif myGuess == 1:
l = m + 1
else:
return m
#Runtime: O(log n)
#Space: O(1)
```
94
# Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
## Footnote
Input: nums = [1,3,5,6], target = 5
Output: 2
```
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = l + (r - l) // 2
if nums[m] == target:
return m
elif nums[m] < target:
l = m + 1
else:
r = m - 1
return l
#Example: [1 2] #Try to find 0
#In first iteration, l = 0, r = 1, m = 0
#Because 0 < 1, r = 0 - 1 = -1 and then out of bounds
#So l = 0 is the spot to insert it.
#O(log n)
#O(1)
```
95
# Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
## Footnote
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
```
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left, right = self.binarySearch(nums, target, True), self.binarySearch(nums, target, False)
return [left, right]
def binarySearch(self, nums, target, leftBias):
res = -1 #Since this is the default we return if not found
l, r = 0, len(nums) - 1
while l <= r:
m = l + (r - l) // 2
if nums[m] < target:
l = m + 1
elif nums[m] > target:
r = m - 1
else:
res = m
if leftBias:
r = m - 1
else:
l = m + 1
return res
#Runtime: O(log n)
#Space: O(1)
```
96
# Pascal's Triangle
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
## Footnote
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = [[1]]
for i in range(1, numRows): #because firstRow is already done
tmp = [0] + res[-1] + [0] #pad previous row with zeroes
row = []
for j in range(len(tmp) - 1):
#We take the value immediately above, and the one to the right of it. j j+1
#Example: [0][1][0]
# j j+1
#row [1][1]
row.append(tmp[j] + tmp[j + 1])
res.append(row)
return res
#O(n^2) #n rows, length n iteration for each
#O(n) for temporary rows
```
97
# Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values.
## Footnote
Input: root = [1,null,2,3]
Output: [1,3,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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(root):
if not root:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res
#O(n)
#O(h)
```
98
# Permutations II
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
## Footnote
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
```
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
counts = {}
curPerm = []
res = []
for n in nums:
counts[n] = counts.get(n, 0) + 1
def dfs():
if len(curPerm) == len(nums):
res.append(curPerm.copy())
return
for n in counts:
if counts[n] > 0:
#Take it
counts[n] -= 1
curPerm.append(n)
dfs()
#Clean it up
counts[n] += 1
curPerm.pop()
#The "don't take it" aspect is handled by subsequent calls of the for loop when we skip over n and go to next iteration instead
dfs()
return res
#Runtime: O(n!) for the number of permutations, O(n*n!) if factor in copying
#Space: O(n) for stack, or O(n*n!) if factor in copying
```
99
# Perfect Squares
Given an integer n, return the least number of perfect square numbers that sum to n.
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. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
## Footnote
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
```
class Solution:
def numSquares(self, n: int) -> int:
dp = [n] * (n + 1) #number to least # of perfect squares required
dp[0] = 0
for target in range(1, n + 1): #solving the subproblems
for s in range(1, target + 1): #we'll try every square less than target
square = s * s
if square > target:
break # we went too far, so break.
#the min number of perfect squares to form target is:
#either what it already is, or 1 for this s * s, and then
#the min number from what's remaining
dp[target] = min(dp[target], 1 + dp[target - square])
return dp[n]
#O(n * sqrt n) #n values for target, each we consider sqrt (n) values to form target
#O(n) for the dp
```
100
# Stone Game
Alice and Bob play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].
The objective of the game is to end with the most stones. The total number of stones across all the piles is odd, so there are no ties.
Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.
Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.
## Footnote
Input: piles = [5,3,4,5]
Output: true
Explanation:
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.
```
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
#See predict the winner for the more generalized problem statement, same solution
dp = {} #(l, r): maxDifference of current player - other player, from numbers between i to j.
def dfs(l, r):
if l == r:
return piles[l]
if (l, r) in dp:
return dp[(l, r)]
#The maximum difference for dp[(l, r)] is. The max we can get from an end, minus the max difference
#that the OTHER player can get that's in the other player's benefit. This is minimax!
dp[(l, r)] = max(piles[l] - dfs(l + 1, r), piles[r] - dfs(l, r - 1))
return dp[(l, r)]
return dfs(0, len(piles) - 1) >= 0
#O(N^2)
#O(N^2)
piles = [5,3,4,5]
print(stoneGame(piles)) ->1
piles = [3, 7, 2, 1]
print(stoneGame(piles)) ->
piles = [3, 7, 1]
print(stoneGame(piles))
# def find(i, j):
# if (i, j) not in dp:
# if i == j:
# return nums[i]
# dp[i,j] = max(nums[i]-find(i+1, j), nums[j]-find(i, j-1))
# return dp[i,j]
# return find(0, len(nums)-1) >= 0
```
101
# Delete and Earn
You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.
Return the maximum number of points you can earn by applying the above operation some number of times.
## Footnote
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.
```
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
counts = {}
for n in nums:
counts[n] = counts.get(n, 0) + 1
nums = sorted(list(set(nums)))
earn1, earn2 = 0, 0
for i in range(len(nums)):
curEarn = nums[i] * counts[nums[i]]
#Can't include cur and the earn2
if i > 0 and nums[i] == nums[i - 1] + 1:
tmp = max(curEarn + earn1, earn2)
earn1 = earn2
earn2 = tmp
# Otherwise able to include earn2
else:
tmp = curEarn + earn2
earn1 = earn2
earn2 = tmp
return earn2
#O(n log n) for sorting, O(n) for iteration
#O(n) for the map, but only need 2 variables for the dp
```
102
# Wiggle Sort
Given an integer array nums, reorder it such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
You may assume the input array always has a valid answer.
## Footnote
Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.
```
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
#[3 5 2 1 6 4]
# E O E O If odd and less than prev, swap (2 and 1)
# This works because 2 was guaranteed less than 5, and 1 is
# even smaller than 2
#[3 5 1 2 6 4]
# E O E O E If even and greater than prev, swap (2 and 6)
# This works because 2 was greater than 1, and 6 is even greater than 2
for i in range(1, len(nums)):
if (i > 0 and i % 2 and nums[i] < nums[i - 1]) or (i > 0 and i % 2 == 0 and nums[i] > nums[i - 1]):
nums[i], nums[i - 1] = nums[i - 1], nums[i]
return nums
#O(n)
#O(1)
```
103
# Ugly Number
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return true if n is an ugly number.
## Footnote
Input: n = 6
Output: true
Explanation: 6 = 2 × 3
```
class Solution:
def isUgly(self, n: int) -> bool:
if n <= 0:
return False
primes = [2, 3, 5]
for p in primes:
while n % p == 0:
n = n // p
return n == 1
#Runtime: O(n)
#Space: O(1)
#Idea. Divide by the prime factors as much as possible. If can reduce, is ugly.
#Example of NOT: 14. 2 and 7. 7 can't be reduced to 1
```
104
# Flip String to Monotone Increasing
A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).
You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.
## Footnote
Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.
```
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
countOnes = 0
res = 0
for n in s:
if n == "1":
#We don't have to worry, since we assume up to now it's correct.
countOnes += 1
#CountOnes contains the number of DEFINITE 1s in the input string. Doesn't count the ones we potentially flip from 0 to 1 below.
else: #Otherwise if we see a 0
#Either: Flip all the ones before to zero
#OR, flip current into a 1, then flip the necessary
#beforehand to be monotonic increasing
res = min(countOnes, 1 + res)
return res
#O(n)
#O(1)
```
105
# Fibonacci Number
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
```
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
n1 = 0
n2 = 1
for i in range(2, n + 1):
tmp = n1 + n2
n1 = n2
n2 = tmp
return n2
#O(n)
#O(1)
```
106
# Greatest Common Divisor of Strings
For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
## Footnote
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
```
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
def isDivisor(L):
if len(str1) % L or len(str2) % L:
return False
multiple1 = len(str1) // L
multiple2 = len(str2) // L
substring = str1[:L]
return multiple1 * substring == str1 and multiple2 * substring == str2
for L in range(min(len(str1), len(str2)), 0, -1): #we go until 0, because at minimum, our length needs to be at least 1. Which signifies a single character.
if isDivisor(L):
return str1[:L] #If it's a divisor, it divides both. So can just return str1[:L], since L is guaranteed to be the shorter one and can fit
return ""
#Note: We are GREEDY and try from the end of the minimum length moving forward.
#Runtime: O(min(M, N)) * (M + N) #We take the minimum length of the two strings, and check if that substring can fit into both strings which requires making copies, etc..
#Space: O(min(M, N)) for the string creation and comparison etc..
```
107
# Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
## Footnote
Input: root = [1,2,2,3,4,4,3]
Output: true
```
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(leftChild, rightChild):
if not leftChild and not rightChild:
return True
if not leftChild or not rightChild or leftChild.val != rightChild.val:
return False
return dfs(leftChild.left, rightChild.right) and dfs(leftChild.right, rightChild.left)
return dfs(root.left, root.right)
#Runtime: O(n)
#Space: O(h)
```
108
# Array With Elements Not Equal to Average of Neighbors
You are given a 0-indexed array nums of distinct integers. You want to rearrange the elements in the array such that every element in the rearranged array is not equal to the average of its neighbors.
More formally, the rearranged array should have the property such that for every i in the range 1 <= i < nums.length - 1, (nums[i-1] + nums[i+1]) / 2 is not equal to nums[i].
Return any rearrangement of nums that meets the requirements.
## Footnote
Input: nums = [1,2,3,4,5]
Output: [1,2,4,5,3]
Explanation:
When i=1, nums[i] = 2, and the average of its neighbors is (1+4) / 2 = 2.5.
When i=2, nums[i] = 4, and the average of its neighbors is (2+5) / 2 = 3.5.
When i=3, nums[i] = 5, and the average of its neighbors is (4+3) / 2 = 3.5.
```
class Solution:
def rearrangeArray(self, nums: List[int]) -> List[int]:
#Greedy solution with 2 pointers
#To guarantee element is not equal to average of neighbors:
#Have current element be smaller than the neighbors
#Have current element be larger than neighbors
#Example: Input [1 2 3 4 5]
#[15243] #5 is greater than neighbors. 2 is smaller than neighbors
#To generate this, just alternate small and large values. [SLSLSLSLSL..]
nums.sort()
l, r = 0, len(nums) - 1
res = []
while l <= r:
res.append(nums[l])
l += 1
#l <= r because you can have [1 2]. In this case, want r to be added
#Can have [1]. After adding 1, l > r.
#no while loop. Only for loop to do once.
if l <= r:
res.append(nums[r])
r -= 1
return res
#O(n log n)
#O(n) #for res
```
109
# Check Completeness of a Binary Tree
Given the root of a binary tree, determine if it is a complete binary tree.
In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
## Footnote
Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.
```
# 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 isCompleteTree(self, root: Optional[TreeNode]) -> bool:
q = deque([root])
while q:
#Can't do the for _ in range(len(q)) because we have a while loop later
node = q.popleft()
if node:
#We need to append NULLS too!
q.append(node.left)
q.append(node.right)
else:
while q:
if q.popleft():
return False
return True
#Key insight. If complete, then after seeing first NULL, everything else after is a NULL. If encounter a non-null, it's not complete.
#O(N)
#O(N)
```
110
# Next Greater Element I
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
## Footnote
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
```
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1Idx = {n: i for i, n in enumerate(nums1)}
res = [-1] * len(nums1)
stack = []
for i in range(len(nums2)):
cur = nums2[i]
while stack and cur > stack[-1]:
val = stack.pop()
idx = nums1Idx[val]
res[idx] = cur
if cur in nums1Idx: #if val is in nums1, we need to find the next greater element of it. So therefore, we'll add to stack.
stack.append(cur)
return res
#O(n + m)
#O(n) #for the nums1Idx and stack for O(n)
#Monotonically decreasing stack: Example [2, 1]
```
111
# Find Duplicate Subtrees
Given the root of a binary tree, return all duplicate subtrees.
For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with the same node values.
## Footnote
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
```
# 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 findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
subtrees = defaultdict(list)
res = []
def dfs(node): #dfs returns the serialization.
if not node:
return "N"
#Serialize via preorder traversal
s = ",".join([str(node.val), dfs(node.left), dfs(node.right)])
if len(subtrees[s]) == 1: #if already exists, append to it.
res.append(node)
#Either way, add it to the list
subtrees[s].append(node)
return s
dfs(root)
return res
#Runtime: O(n) nodes, each serialization operation is length n -> O(n^2)
#Space: O(n^2) nodes. O(n) nodes, O(n) each serialization length space
```
112
# Game of Life
According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
Any live cell with fewer than two live neighbors dies as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.
## Footnote
Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
```
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
If Alive:
- 0 if <2 alive neighbors.
- 1 if 2 or 3alive
- 0 if >3 alive
If Dead:
- 1 if 3 alive neighbors
Summary:
1 - live if 2 or 3 else 0
0 - live if 3 else 0
Remaps:
OLD NEW REMAP
0 0 0
1 0 1 #count this as a 1
0 1 2
1 1 3 #If alive in next generation, count it as a 3
"""
ROWS, COLS = len(board), len(board[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
def countNeighbors(r, c):
count = 0
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
if (neiR >= 0 and neiR < ROWS and neiC >= 0 and neiC < COLS and board[neiR][neiC] in [1, 3]):
count += 1
return count
for r in range(ROWS):
for c in range(COLS):
neiCount = countNeighbors(r, c)
if board[r][c] == 1:
if neiCount in [2, 3]:
board[r][c] = 3
# else:
# board[r][c] = 1 #stays a 1
else:
if neiCount == 3:
board[r][c] = 2
#After this, we have to go through the whole board again and remap values correctly.
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == 1:
board[r][c] = 0
elif board[r][c] in [2, 3]:
board[r][c] = 1
return board
#Runtime: O(MN)
#Space: O(1) since we're modifying in place.
```
113
# Concatenation of Array
Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).
Specifically, ans is the concatenation of two nums arrays.
Return the array ans.
## Footnote
Input: nums = [1,3,2,1]
Output: [1,3,2,1,1,3,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
- ans = [1,3,2,1,1,3,2,1]
```
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
ans = []
for i in range(2): #can be k instead of just 2 that makes it generalizable.
for n in nums:
ans.append(n)
return ans
#O(n) #runtime for concat of these elts
#O(n) #for ans array
```
114
# Palindrome Number
Given an integer x, return true if x is a
palindrome
, and false otherwise.
## Footnote
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
```
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
div = 1 #
#1) Find the max divisor that can fit into x
while x >= div * 10:
div *= 10
#Continue while x is non-empty
while x:
right = x % 10 #Example: 501 mod 10 is 1
left = x // div #Example: 5001 div 1000 is 5.
if left != right:
return False
x = (x % div) // 10 #Example: 5201 % 1000 is 201. That chops left. dividing by 10 chops right. Example: 521 // 10 is 52.
#Then divisor should shift by cut by 100 since we chopped off 2 digits
div = div // 100
return True
#Runtime: O(N)
#Space: O(1)
```
115
# Removing Stars From a String
You are given a string s, which contains stars *.
In one operation, you can:
Choose a star in s.
Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note:
The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.
## Footnote
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".
```
class Solution:
def removeStars(self, s: str) -> str:
stack = []
for c in s:
if c == "*":
if stack:
stack.pop()
else:
stack.append(c)
return "".join(stack)
#O(n)
#O(n)
```
116
# Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
## Footnote
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
```
class Solution:
def mySqrt(self, x: int) -> int:
res = 1
l, r = 0, x
while l <= r:
m = l + (r - l) // 2
if m ** 2 > x:
r = m - 1
elif m ** 2 < x:
res = m
l = m + 1
else:
return m
return res
#O(log n)
#O(1)
```
117
# Find Peak Element
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
## Footnote
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
```
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = l + (r - l) // 2
#If left neighbor is greater than mid, go left
if m > 0 and nums[m - 1] > nums[m]:
r = m - 1
#If right neighbor is greater than mid, go right
elif m < len(nums) - 1 and nums[m] < nums[m + 1]:
l = m + 1
#We are at a peak
else:
return m
#O(log n)
#O(1)
```
118
# Number of Closed Islands
Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
## Footnote
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).
```
class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
res = 0
visit = set()
#1 if the island is closed, otherwise 0
def dfs(r, c):
#If was able to reach the border, it's not a closed island, so return 0. We were able to reach border through some route.
if r < 0 or r == ROWS or c < 0 or c == COLS:
return 0
#If able to reach water, or reach a piece of land we previously visited, that means we are a closed island (to our knowledge in that route)
if grid[r][c] == 1 or (r, c) in visit:
return 1
visit.add((r, c))
#If any of them are 0, we return 0. Otherwise if all 1s, we confirm it's a closed island.
#We do min instead of ANDs, because ANDs can terminate early and leave partially marked islands.
return min(dfs(r - 1, c), dfs(r + 1, c), dfs(r, c - 1), dfs(r, c + 1))
for r in range(ROWS):
for c in range(COLS):
if not grid[r][c] and (r, c) not in visit:
res += dfs(r, c)
return res
#O(MN)
#O(MN)
```
119
# Validate Stack Sequences
Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.
## Footnote
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
```
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
i = 0
for n in pushed:
stack.append(n)
while i < len(popped) and stack and stack[-1] == popped[i]:
stack.pop()
i += 1
return not stack
#O(n)
#O(n)
```
120
# Rotate Array
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
## Footnote
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
```
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
def reversePortion(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
reversePortion(0, len(nums) - 1)
reversePortion(0, k - 1)
reversePortion(k, len(nums) - 1)
return nums
#O(n)
#O(1)
```
121
# Check If a String Contains All Binary Codes of Size K
Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.
## Footnote
Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.
```
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
codeSet = set()
for i in range(len(s) - k + 1): #plus 1 for python exclusion
codeSet.add(s[i: i + k])
return len(codeSet) == 2 ** k
#O(n * k) #n characters in s, slice and add size k strings to set
#O(2^k) #the number of unique strings.
```
122
# Merge Strings Alternately
You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.
Return the merged string.
## Footnote
Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1: a b c
word2: p q r
merged: a p b q c r
```
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
i, j = 0, 0
res = [] #do this because strings are immutable.
while i < len(word1) and j < len(word2):
res.append(word1[i])
res.append(word2[j])
i += 1
j += 1
if i < len(word1):
res.append(word1[i:])
if j < len(word2):
res.append(word2[j:])
return "".join(res)
#O(word1 + word2)
#O(word1 + word2) for result
```
123
# Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence's length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
## Footnote
Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".
```
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
def longestCommonSubsequence(s1, s2):
dp = [[0] * (len(s2) + 1) for i in range(len(s1) + 1)]
for i in range(len(s1) - 1, -1, -1):
for j in range(len(s2) - 1, -1, -1):
if s1[i] == s2[j]:
dp[i][j] = 1 + dp[i + 1][j + 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
return dp[0][0]
return longestCommonSubsequence(s, s[::-1])
#O(n * n) the two strings are s and s[::-1]
#O(n * n) dp array
```
124
# Number of Zero-Filled Subarrays
Given an integer array nums, return the number of subarrays filled with 0.
A subarray is a contiguous non-empty sequence of elements within an array.
## Footnote
Input: nums = [0,0,0,2,0,0]
Output: 9
Explanation:
There are 5 occurrences of [0] as a subarray.
There are 3 occurrences of [0,0] as a subarray.
There is 1 occurrence of [0,0,0] as a subarray.
There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.
```
class Solution:
"""
0 -> 1 subarray
00 -> 3 subarrays. +2.
000 -> 6 subarrays +3
0000 -> 10 subarrays +4
"""
def zeroFilledSubarray(self, nums: List[int]) -> int:
res, zeroesStreakCount = 0, 0
for i in range(len(nums)):
if nums[i] == 0:
zeroesStreakCount += 1
res += zeroesStreakCount
else:
zeroesStreakCount = 0
return res
#O(n)
#O(1)
```
125
# Successful Pairs of Spells and Potions
You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.
You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.
Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.
## Footnote
Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful.
Thus, [2,0,2] is returned.
```
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
potions.sort() #potions isn't necessarily sorted for us.
res = []
for s in spells:
l, r = 0, len(potions) - 1
idx = len(potions) #initialize to this because, if no pairs form, then we want to append len(potions) - len(potions) = 0
while l <= r:
m = l + (r - l) // 2
if s * potions[m] >= success:
idx = m
r = m - 1
else:
l = m + 1
res.append(len(potions) - idx)
return res
#O(p log p + |s| * log (|p|))
#O(|s|)
```
126
# Grid Game
You are given a 0-indexed 2D array grid of size 2 x n, where grid[r][c] represents the number of points at position (r, c) on the matrix. Two robots are playing a game on this matrix.
Both robots initially start at (0, 0) and want to reach (1, n-1). Each robot may only move to the right ((r, c) to (r, c + 1)) or down ((r, c) to (r + 1, c)).
At the start of the game, the first robot moves from (0, 0) to (1, n-1), collecting all the points from the cells on its path. For all cells (r, c) traversed on the path, grid[r][c] is set to 0. Then, the second robot moves from (0, 0) to (1, n-1), collecting the points on its path. Note that their paths may intersect with one another.
The first robot wants to minimize the number of points collected by the second robot. In contrast, the second robot wants to maximize the number of points it collects. If both robots play optimally, return the number of points collected by the second robot.
## Footnote
Input: grid = [[2,5,4],[1,5,1]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 0 + 4 + 0 = 4 points.
```
class Solution:
def gridGame(self, grid: List[List[int]]) -> int:
N = len(grid[0])
row1 = grid[0].copy()
row2 = grid[1].copy()
#Prefix sums
for i in range(1, N):
row1[i] += row1[i - 1]
row2[i] += row2[i - 1]
res = float('inf')
#c: where the first robot turns
for c in range(N):
topRight = row1[-1] - row1[c]
bottomLeft = row2[c - 1] if c > 0 else 0
second = max(topRight, bottomLeft)
res = min(res, second)
return res
#O(n) to populate prefix sums. For calculation of turns and such also O(n) time. O(n) columns, O(1) to compute topRight and bottomLeft for each turn
#O(2 * n) -> O(n) for prefix sums
```
127
# Optimal Partition of String
Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.
Return the minimum number of substrings in such a partition.
Note that each character should belong to exactly one substring in a partition.
## Footnote
Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.
```
class Solution:
def partitionString(self, s: str) -> int:
res = 1 #initialized to 1 because.. if "abc", these are all in the set but res is still 0 and returned.
curSet = set()
for c in s:
if c in curSet:
res += 1
curSet = set()
curSet.add(c)
return res
#O(n)
#O(26) -> O(1)
```
128
# Minimum Score of a Path Between Two Cities
You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [ai, bi, distancei] indicates that there is a bidirectional road between cities ai and bi with a distance equal to distancei. The cities graph is not necessarily connected.
The score of a path between two cities is defined as the minimum distance of a road in this path.
Return the minimum possible score of a path between cities 1 and n.
Note:
A path is a sequence of roads between two cities.
It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
The test cases are generated such that there is at least one path between 1 and n
## Footnote
Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.
```
class Solution:
def minScore(self, n: int, roads: List[List[int]]) -> int:
visit = set()
res = float('inf')
adj = defaultdict(list)
for u, v, dist in roads:
adj[u].append((v, dist))
adj[v].append((u, dist)) #bidirectional
def dfs(u):
nonlocal res
if u in visit:
return
visit.add(u)
for nei, dist in adj[u]:
res = min(res, dist)
dfs(nei)
dfs(1)
return res
#O(V + E) for dfs
#O(V + E) #for adj, etc
```
129
# Number of Enclaves
You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.
A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.
Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.
## Footnote
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.
```
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visit = set()
def dfs(r, c):
if r < 0 or r == ROWS or c < 0 or c == COLS or not grid[r][c] or (r, c) in visit:
return 0
visit.add((r, c))
borderLand = 1 #at least will return 1 for this piece
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
borderLand += dfs(neiR, neiC)
return borderLand
total = 0
borderLand = 0
for r in range(ROWS):
for c in range(COLS):
total += grid[r][c ] #we add 1 or 0.
if (r, c) not in visit and grid[r][c] and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
borderLand += dfs(r, c)
return total - borderLand
#O(mn)
#O(mn)
```
130
# Maximum Width of Binary Tree
Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is guaranteed that the answer will in the range of a 32-bit signed integer.
## Footnote
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
```
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
prevLevel, leftMost = 0, 1 #for math to work out
#Assign prevLevel to 0 doesn't really matter
#Assign leftMost to 1. This is because if just a single node, we want
#1 - 1 + 1 = 1. In the very first root level, we don't execute the if and just
#Go into 1 - 1 + 1
res = 0
q = deque([(root, 1, 0)]) #node, num, level
while q:
for _ in range(len(q)):
node, num, level = q.popleft()
if level > prevLevel:
prevLevel = level
leftMost = num #at new level, we identify leftMost after transition
res = max(res, num - leftMost + 1)
if node.left:
q.append((node.left, 2 * num, level + 1))
if node.right:
q.append((node.right, 2 * num + 1, level + 1))
return res
#O(n)
#O(n)
```
131
# Minimize Maximum of Array
You are given a 0-indexed array nums comprising of n non-negative integers.
In one operation, you must:
Choose an integer i such that 1 <= i < n and nums[i] > 0.
Decrease nums[i] by 1.
Increase nums[i - 1] by 1.
Return the minimum possible value of the maximum integer of nums after performing any number of operations.
## Footnote
Input: nums = [3,7,1,6]
Output: 5
Explanation:
One set of optimal operations is as follows:
1. Choose i = 1, and nums becomes [4,6,1,6].
2. Choose i = 3, and nums becomes [4,6,2,5].
3. Choose i = 1, and nums becomes [5,5,2,5].
The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5.
Therefore, we return 5.
```
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
res = nums[0] #This value is the smallest the max can be. Can only increase from here!
total = nums[0]
for i in range(1, len(nums)):
total += nums[i]
#we try to evenly distribute the total, so...
#The number of elts is i + 1.
res = max(res, ceil(total / (i + 1)))
return res
#O(n)
#O(1)
```
132
# Check if Move is Legal
You are given a 0-indexed 8 x 8 grid board, where board[r][c] represents the cell (r, c) on a game board. On the board, free cells are represented by '.', white cells are represented by 'W', and black cells are represented by 'B'.
Each move in this game consists of choosing a free cell and changing it to the color you are playing as (either white or black). However, a move is only legal if, after changing it, the cell becomes the endpoint of a good line (horizontal, vertical, or diagonal).
A good line is a line of three or more cells (including the endpoints) where the endpoints of the line are one color, and the remaining cells in the middle are the opposite color (no cells in the line are free). You can find examples for good lines in the figure below. Given two integers rMove and cMove and a character color representing the color you are playing as (white or black), return true if changing cell (rMove, cMove) to color color is a legal move, or false if it is not legal.
## Footnote
Input: board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"
Output: true
Explanation: '.', 'W', and 'B' are represented by the colors blue, white, and black respectively, and cell (rMove, cMove) is marked with an 'X'.
The two good lines with the chosen cell as an endpoint are annotated above with the red rectangles.
```
class Solution:
def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
ROWS, COLS = len(board), len(board[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
board[rMove][cMove] = color
def legal(r, c, dir, color):
dr, dc = dir
r = r + dr #increment to start. Otherwise, we encounter board[r][c] == color condition below but it's the same cell so we erroneously return False too early.
c = c + dc
length = 2
while r >= 0 and r < ROWS and c >= 0 and c < COLS:
if board[r][c] == ".":
return False
if board[r][c] == color:
return length >= 3
r = r + dr
c = c + dc
length += 1
return False
for d in directions:
if legal(rMove, cMove, d, color):
return True
return False
#Runtime: O(8 * N) -> O(1) since 8 x 8 board
#Space: O(1)
```
133
# Find Bottom Left Tree Value
Given the root of a binary tree, return the leftmost value in the last row of the tree.
## Footnote
Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
if not root:
return None
q = deque([root])
bottomLeft = None
while q:
for _ in range(len(q)):
node = q.popleft()
bottomLeft = node
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
return bottomLeft.val
#O(n) for BFS
#O(n) for q
```
134
# Can Place Flowers
You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.
Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.
## Footnote
Input: flowerbed = [1,0,0,0,1], n = 2
Output: false
```
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
for i in range(len(flowerbed)):
#Because if at leftmost or rightmost, the check for "left of i" or "right of i" will evaluate to True automatically.
if (i == 0 or flowerbed[i - 1] == 0) and flowerbed[i] == 0 and (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0):
flowerbed[i] = 1
n -= 1
return n <= 0
#O(n)
#O(1)
```
135
# Find Score of an Array After Marking All Elements
You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:
Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
Add the value of the chosen integer to score.
Mark the chosen element and its two adjacent elements if they exist.
Repeat until all the array elements are marked.
Return the score you get after applying the above algorithm.
## Footnote
Input: nums = [2,3,5,1,3,2]
Output: 5
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,5,1,3,2].
- 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [2,3,5,1,3,2].
- 2 is the only remaining unmarked element, so we mark it: [2,3,5,1,3,2].
Our score is 1 + 2 + 2 = 5.
```
class Solution:
def findScore(self, nums: List[int]) -> int:
#Simulation Approach:
# seen = [0] * (len(nums) + 1) #+1 to avoid index out of bounds when we are at the final element.
# res = 0
# for n, i in sorted([n,i] for i,n in enumerate(nums)):
# if seen[i]: continue
# res += n
# seen[i] = seen[i - 1] = seen[i + 1] = 1
# return res
#O(n log n) for sort
#O(n) for seen
#MinHeap approach:
visited = set()
minHeap = [(n, i) for i, n in enumerate(nums)]
heapify(minHeap)
res = 0
while minHeap:
n, i = heappop(minHeap)
if i not in visited:
res += n
if i - 1 >= 0:
visited.add(i - 1)
if i + 1 < len(nums):
visited.add(i + 1)
visited.add(i)
return res
```
136
# Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
## Footnote
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
```
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
dp = [[float('inf')] * (COLS + 1) for r in range(ROWS + 1)]
#Arbitrarily set one of the values to zero
dp[ROWS - 1][COLS] = 0
for r in range(ROWS - 1, -1, -1):
for c in range(COLS - 1, -1, -1):
dp[r][c] = grid[r][c] + min(dp[r + 1][c], dp[r][c + 1])
return dp[0][0]
# Runtime: O(mn)
# Space: O(mn)
# ROWS, COLS = len(grid), len(grid[0])
# dp = [float('inf')] * (COLS + 1)
# dp[COLS - 1] = 0
# for r in range(ROWS - 1, -1, -1):
# for c in range(COLS - 1, -1, -1):
# dp[c] = grid[r][c] + min(dp[c], dp[c + 1])
# return dp[0]
#Runtime: O(mn)
#Space: O(n) #number of columns
```
137
# Minimum Number of Swaps to Make the String Balanced
You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.
A string is called balanced if and only if:
It is the empty string, or
It can be written as AB, where both A and B are balanced strings, or
It can be written as [C], where C is a balanced string.
You may swap the brackets at any two indices any number of times.
Return the minimum number of swaps to make s balanced.
## Footnote
Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".
```
class Solution:
def minSwaps(self, s: str) -> int:
extraClosed, maxClosed = 0, 0
for c in s:
if c == "]":
extraClosed += 1
else:
extraClosed -= 1
maxClosed = max(extraClosed, maxClosed)
#Each swap decrements the number of maxClosed by 2.
#Example: ]]] -> []] after a swap (3 -> 1)
#Therefore, the number of swaps needed is (maxClosed + 1) div by 2.
#To make math work out, add one (or math.ceil): if 3, then we want (3 + 1) // 2 -> 2
#if 4, (4 + 1) // 2 -> 2 still.
return (maxClosed + 1) // 2 #Or math.ceil(maxClose / 2)
#O(n)
#O(1)
```
138
# Number of Pairs of Interchangeable Rectangles
You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [widthi, heighti] denotes the width and height of the ith rectangle.
Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if widthi/heighti == widthj/heightj (using decimal division, not integer division).
Return the number of pairs of interchangeable rectangles in rectangles.
## Footnote
Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.
```
class Solution:
def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
ratios = {}
for w, h in rectangles:
ratio = w / h
ratios[ratio] = ratios.get(ratio, 0) + 1
total = 0
for count in ratios.values():
#n!/(n - k)!k!
#n!/(n - 2)! 2! -> n * (n - 1) / 2
total += count * (count - 1) // 2
return total
#O(n)
#O(n)
```
139
# Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
## Footnote
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
```
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
last = m + n - 1
#merge from the back, and greater elements.
while m > 0 and n > 0:
if nums1[m - 1] > nums2[n - 1]:
nums1[last] = nums1[m - 1]
m -= 1
else:
nums1[last] = nums2[n - 1]
n -= 1
last -= 1
while n > 0:
nums1[last] = nums2[n - 1]
n -= 1
last -= 1
return nums1
#O(m + n)
#O(1) -> no extra memory since nums1 can hold everything
```
140
# Flip Equivalent Binary Trees
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.
## Footnote
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.
```
# 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 flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if not root1 and not root2:
return True
if not root1 or not root2 or root1.val != root2.val:
return False
noFlip = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)
flip = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)
return noFlip or flip
#O(n + m)
#O(min(h1, h2))
```
141
# Minimum Number of Flips to Make the Binary String Alternating
You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:
Type-1: Remove the character at the start of the string s and append it to the end of the string.
Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.
Return the minimum number of type-2 operations you need to perform such that s becomes alternating.
The string is called alternating if no two adjacent characters are equal.
For example, the strings "010" and "1010" are alternating, while the string "0100" is not.
## Footnote
Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".
```
class Solution:
def minFlips(self, s: str) -> int:
"""
Example:
[111000] 111000 <- s duplicated
[010101] 010101 <- alt 1 (duplicated since it's length of 2 s)
[101010] 101010 <- alt 2 (duplicated since it's length of 2 s)
Now when we slide, we avoid duplicated work. We just "move the 1 prefix to the end" by sliding the window over, so only need to remove l from the window. The r computation is always done at the beginning of the loop.
1[11000 1]11000
0[10101 0]10101
1[01010 1]01010
"""
#Sliding window problem
n = len(s) #the original size of n
s = s + s
alt1, alt2 = "", ""
for i in range(len(s)):
alt1 += "0" if i % 2 else "1"
alt2 += "1" if i % 2 else "0"
l = 0
res = float('inf')
diff1, diff2 = 0, 0
for r in range(len(s)):
if s[r] != alt1[r]:
diff1 += 1
if s[r] != alt2[r]:
diff2 += 1
if (r - l + 1) > n:
if s[l] != alt1[l]:
diff1 -= 1
if s[l] != alt2[l]:
diff2 -= 1
l += 1
if (r - l + 1) == n: #only start calculating if the size is at least n.
res = min(res, diff1, diff2)
return res
#O(n) #avoid repeated work with sliding window
#O(n)
```
142
# Construct String from Binary Tree
Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)"
Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
```
# 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 tree2str(self, root: Optional[TreeNode]) -> str:
res = []
def preorder(node):
if not node:
return
res.append("(")
res.append(str(node.val))
#for the case when we have no left child and have a right child, we need to append () to avoid ambiguity
if not node.left and node.right:
res.append("()")
preorder(node.left)
preorder(node.right)
res.append(")")
preorder(root)
return "".join(res[1:-1]) #remove outermost parentheses
#O(n) to go through the whole tree
#O(n) for res
```
143
# Eliminate Maximum Number of Monsters
You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the ith monster from the city.
The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the ith monster in kilometers per minute.
You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge.The weapon is fully charged at the very start.
You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.
Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.
Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.
```
class Solution:
def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
minutesToReach = [ceil(d / s) for d, s in zip(dist, speed)]
minutesToReach.sort()
res = 0
#Each index m is the time.
for m in range(len(minutesToReach)):
if minutesToReach[m] <= m:
return res
res += 1
return res #if can eliminate all monsters
#O(n log n )
#O(n)
```
144
# Remove Covered Intervals
Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.
The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.
Return the number of remaining intervals.
Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.
```
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
#[1, 4], [1, 6], [2, 8]
#sort it so it's [1, 6], [1, 4], [2, 8]
intervals.sort(key = lambda x: (x[0], -x[1]))
res = [intervals[0]]
for start, end in intervals[1:]:
prevStart, prevEnd = res[-1]
if prevStart <= start and prevEnd >= end: #because it's covered
continue
res.append([start, end])
return len(res)
#O(n log n)
#O(n) res
```
145
# Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
or example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
```
class Solution:
def romanToInt(self, s: str) -> int:
res = 0
romanToInteger = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
for i in range(len(s)):
if i + 1 < len(s) and romanToInteger[s[i]] < romanToInteger[s[i + 1]]:
res -= romanToInteger[s[i]]
else:
res += romanToInteger[s[i]]
return res
#O(n)
#O(1) -> constant
```
146
# Integer to Roman
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.
Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
```
class Solution:
def intToRoman(self, num: int) -> str:
roman = [[1000, "M"], [900, "CM"], [500, "D"], [400, "CD"], [100, "C"], [90, "XC"], [50, "L"], [40, "XL"], [10, "X"], [9, "IX"], [5, "V"], [4, "IV"], [1, "I"]]
res = ""
for val, sym in roman:
if num // val:
count = num // val
res += count * sym
num = num % val
return res
#O(1) number of symbols constant
#O(1) number of symbols constant
```
147
# Non-decreasing Array
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
```
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
changed = False
for i in range(len(nums) - 1): #since we reference i - 1, i, i + 1
if nums[i] <= nums[i + 1]:
continue
#If here, it's decreasing. But if changed already, then it's impossible
if changed:
return False
#We want to decrease left element if possible. It's only possible if we are at least as large as the previous element
#i
# 2 4 3
#If on the left it's free.
if i == 0 or nums[i + 1] >= nums[i - 1]:
nums[i] = nums[i + 1]
else:
#Otherwise we're forced to increment
#Example: 3 4 2. We can't decrement 4 to 2 since 2 < 3. So we have to increment 2 to 4 instead.
nums[i + 1] = nums[i]
changed = True
return True
#O(n)
#O(1)
```
148
# Sort List
Given the head of a linked list, return the list after sorting it in ascending order.
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head #returns None, or if no elt after, just return head since already sorted
left = head
mid = self.getMid(head)
right = mid.next
mid.next = None #sever the connection here so that we have two lists.
leftList = self.sortList(left)
rightList = self.sortList(right)
return self.merge(leftList, rightList)
def getMid(self, head):
slow = head
fast = head.next
#2nd middle is head,head
#1st middle node is head,head.next
#This way, mid is the 1st middle node.
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def merge(self, l1, l2):
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
if l1:
tail.next = l1
if l2:
tail.next = l2
return dummy.next
#O(n)
#O(1)
```
149
# Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
Input: head = [1,2,3,4]
Output: [2,1,4,3]
```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
cur = head
while cur and cur.next:
nextPair = cur.next.next
second = cur.next
second.next = cur
cur.next = nextPair
prev.next = second
prev = cur #where cur was is now the new prev
cur = nextPair
return dummy.next
#O(n)
#O(1)
```
150
# Rotate List
Given the head of a linked list, rotate the list to the right by k places.
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,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 rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return None
tail = head
listLength = 1
while tail.next:
listLength += 1
tail = tail.next
k = k % listLength
if k == 0:
return head
cur = head
for i in range(listLength - k - 1):
cur = cur.next
newHead = cur.next
cur.next = None
tail.next = head
return newHead
#O(n)
#O(1)
```
151
# Reorganize String
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return "" if not possible.
Input: s = "aab"
Output: "aba"
Input: s = "aaab"
Output: ""
```
class Solution:
def reorganizeString(self, s: str) -> str:
counts = {}
for c in s:
counts[c] = counts.get(c, 0) + 1
maxHeap = [[-count, c] for c, count in counts.items()]
heapq.heapify(maxHeap)
res = ""
prev = None
while maxHeap or prev:
#Example aa. We have prev as "a", but we have nothing in heap
if prev and not maxHeap:
return ""
count, c = heapq.heappop(maxHeap)
count += 1
res += c
if prev:
heapq.heappush(maxHeap, prev)
prev = None #remember to set prev to None. This is because
#we might not update prev in this iteration if count ends up 0
if count != 0:
prev = [count, c]
return res
#O(n * log 26) -> O(n)
#O(26) -> O(1)
```
152
# Island Perimeter
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.
```
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
visit = set() #all the land tiles that we have visited already.
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(r, c):
if r < 0 or r == ROWS or c < 0 or c == COLS or grid[r][c] == 0:
return 1
#If you go out of bounds, it's the edge of island it's a 1.
#Also if you reach water, that's edge of island it's a 1.
if (r, c) in visit: #if is a piece of land already visited, return 0 since we visited that land already.
return 0
visit.add((r, c))
res = 0
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
res += dfs(neiR, neiC)
return res
for r in range(ROWS):
for c in range(COLS):
if grid[r][c]:
return dfs(r, c) #only one island so yeee.
#O(mn)
#O(mn)
```
153
# Two City Scheduling
A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.
Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.
Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
```
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
diffs = [] #difference, c1, c2
#differences represent how much more it would cost to send people to c2 than if we send people to c1
for c1, c2 in costs:
diffs.append([c2 - c1, c1, c2])
diffs.sort() #sort by this difference. Then we end it to c2 because it's cheapest
res = 0
for i in range(len(diffs)):
if i < len(diffs) // 2:
res += diffs[i][2] #send to city 2.
else:
res += diffs[i][1] #after that, send to city 1.
return res
#O(n log n)
#O(n)
```
154
# Verifying an Alien Dictionary
In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.
Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
```
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
orderMap = {c: i for i, c in enumerate(order)}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minLength = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:minLength] == w2[:minLength]:
return False
for j in range(minLength):
if w1[j] != w2[j]:
if orderMap[w1[j]] > orderMap[w2[j]]:
return False
break #because chars are different but it's lexo correct.
return True
#O(# characters across all words)
#O(26) -> O(1)
```
155
# Longest Happy String
A string s is called happy if it satisfies the following conditions:
s only contains the letters 'a', 'b', and 'c'.
s does not contain any of "aaa", "bbb", or "ccc" as a substring.
s contains at most a occurrences of the letter 'a'.
s contains at most b occurrences of the letter 'b'.
s contains at most c occurrences of the letter 'c'.
Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".
A substring is a contiguous sequence of characters within a string.
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.
```
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
maxHeap = []
for count, c in [[-a, "a"], [-b, "b"], [-c, "c"]]:
if count != 0:
heapq.heappush(maxHeap, [count, c])
res = [] #have it be a list
while maxHeap:
count1, char1 = heapq.heappop(maxHeap)
if len(res) >= 2 and char1 == res[-1] == res[-2]:
if not maxHeap:
break #we're done.
else:
count2, char2 = heapq.heappop(maxHeap)
count2 += 1
res.append(char2)
if count2 != 0:
heapq.heappush(maxHeap, [count2, char2])
else:
count1 += 1
res.append(char1)
if count1 != 0:
heapq.heappush(maxHeap, [count1, char1])
return "".join(res)
#Runtime: O(n * log 3) -> O(n) # a + b + c counts
#Space: O(3) -> O(1)
```
156
# Unique Length-3 Palindromic Subsequences
Given a string s, return the number of unique palindromes of length three that are a subsequence of s.
Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.
A palindrome is a string that reads the same forwards and backwards.
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.
For example, "ace" is a subsequence of "abcde"
Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")
```
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
left = set() # seen on the left
right = {} #maps the char to counts of everything on the right
for c in s:
right[c] = right.get(c, 0) + 1
res = set() #pair of (center, outer)
for c in s:
#it's now considered a center, so remove from the right list
right[c] -= 1
if right[c] == 0:
del right[c]
for i in range(26):
outer = chr(ord('a') + i)
if outer in left and outer in right: #we ensure right always has count at least 1.
res.add((c, outer))
left.add(c)
return len(res)
#O(n)
#O(26 * 26) -> O(1)
```
157
# Sign of the Product of an Array
There is a function signFunc(x) that returns:
1 if x is positive.
-1 if x is negative.
0 if x is equal to 0.
You are given an integer array nums. Let product be the product of all values in the array nums.
Return signFunc(product).
## Footnote
Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1
```
class Solution:
def arraySign(self, nums: List[int]) -> int:
neg = 0
for n in nums:
if n == 0:
return 0
neg += 1 if n < 0 else 0
return -1 if neg % 2 else 1
#O(n)
#O(1)
```
158
# Minimum Number of Days to Eat N Oranges
There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:
Eat one orange.
If the number of remaining oranges n is divisible by 2 then you can eat n / 2 oranges.
If the number of remaining oranges n is divisible by 3 then you can eat 2 * (n / 3) oranges.
You can only choose one of the actions per day.
Given the integer n, return the minimum number of days to eat n oranges.
## Footnote
Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange, 10 - 1 = 9.
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1.
Day 4: Eat the last orange 1 - 1 = 0.
You need at least 4 days to eat the 10 oranges.
```
class Solution:
def minDays(self, n: int) -> int:
dp = {0: 0, 1: 1} #0 days to eat 0 oranges, 1 day to eat 1 orange
def dfs(n): #
if n in dp: #if already in dp, return it
return dp[n]
#If not divisible by 2, we make it divisible by two with n % 2 days of eating.
#we spend one day to eat
#then number of days for n // 2
one = n % 2 + 1 + dfs(n // 2)
two = n % 3 + 1 + dfs(n // 3)
dp[n] = min(one, two)
return dp[n]
return dfs(n)
#O(log_2(n))
#Space: O(log_2(n))
```
159
# Combinations
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
## Footnote
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
```
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
curComb = []
res = []
def dfs(start):
if len(curComb) == k:
res.append(curComb.copy())
return
for i in range(start, n + 1):
curComb.append(i) #take this value as part of comb
dfs(i + 1)
curComb.pop()
dfs(1)
return res
#O(nCk * k) #length k
#O(k) for stack, or (nCk * k) for number of combs
```
160
# 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.
## Footnote
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:
#Example: length 7, subtract 3 = 4. This is our initial start
l, r = 0, len(cardPoints) - k
curSum = sum(cardPoints[r:])
res = curSum
while r < len(cardPoints):
curSum -= cardPoints[r]
curSum += cardPoints[l]
l += 1
r += 1
res = max(curSum, res)
return res
#O(n)
#O(1)
```
161
# Repeated DNA Sequences
The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.
For example, "ACGAATTCCG" is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
## Footnote
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]
```
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
seen, res = set(), set()
#this is like how for adjacent of size two, we go until length minus one.
for i in range(len(s) - 9):
seq = s[i: i + 10]
if seq in seen:
res.add(seq)
seen.add(seq)
return list(res)
#O(n)
#O(n)
```
162
# Find the Difference of Two Arrays
Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:
answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
answer[1] is a list of all distinct integers in nums2 which are not present in nums1.
Note that the integers in the lists may be returned in any order.
## Footnote
Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].
```
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
return [list(set(nums1) - set(nums2)), list(set(nums2) - set(nums1))]
#O(n + m)
#O(n + m)
```
163
# Maximum Number of Vowels in a Substring of Given Length
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.
## Footnote
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.
```
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowelCount = 0
vowels = {"a", "e", "i", "o", "u"}
l = 0
res = 0
for r in range(len(s)):
if s[r] in vowels:
vowelCount += 1
if r - l + 1 > k:
if s[l] in vowels:
vowelCount -= 1
l += 1
#Also fine to omit this conditional. Since if less than length k, then we have a small number of vowels that will be replaced later by a bigger window's result.
if r - l + 1 == k:
res = max(res, vowelCount)
return res
#O(n)
#O(1)
```
164
# Insert Delete GetRandom O(1)
Implement the RandomizedSet class:
RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
```
class RandomizedSet:
def __init__(self):
self.valMap = {} #maps val to idx inside valList
self.valList = []
def insert(self, val: int) -> bool:
res = val not in self.valMap
if res:
#Example: nothing inserted yet. We want to map at index 0
self.valMap[val] = len(self.valList)
self.valList.append(val)
return res
def remove(self, val: int) -> bool:
res = val in self.valMap
if res:
idx = self.valMap[val]
lastVal = self.valList[-1]
self.valList[idx] = lastVal #remember to replace the elt in the list
self.valMap[lastVal] = idx
self.valList.pop()
del self.valMap[val]
return res
def getRandom(self) -> int:
return random.choice(self.valList)
#O(1) each op
#O(n)
Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
```
165
# Convert BST to Greater Tree
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
## Footnote
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
```
# 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 convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
curSum = 0 #contains everything that is greater than the current value
#this dfs function doesn't return anything.
#It just increments the curSum, and performs the setting of the values
def dfs(root):
nonlocal curSum
if not root:
return
dfs(root.right) #within this call, we'll increment curSum.
#can't do curSum + dfs(root.right)
#root.val is set to itself + everything that is greater than current val. So we can just add curSum to it
#Need this variable since we are modifying root.val. We need to add to curSum the original value of root.
originalRootVal = root.val
root.val += curSum
curSum += originalRootVal
dfs(root.left)
dfs(root)
return root
#O(n)
#O(h)
```
166
# Combination Sum IV
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The test cases are generated so that the answer can fit in a 32-bit integer.
## Footnote
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
```
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = {0: 1} # targetValue, number of ways to get to that target
for t in range(1, target + 1): #forming the new target from 1 to target
dp[t] = 0
for n in nums:
dp[t] += dp.get(t - n, 0) #the current n is taken into account with t - n.
#Example: n = 2, t = 2. dp[0] returns 1, so 1 combination which is to take 2 itself.
return dp[target]
#Runtime: O(nm). Number of values in nums * the target
#Space: O(m) target
```
167
# Paint House
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color, and you need to cost the least. Return the minimum cost.
The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
Input: [[14,2,11],[11,14,5],[14,3,10]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.
```
def minCost(costs):
dp = [0, 0, 0] #i is house, j is color
#each dp row is for the ith house. each entry represents: for this ith house, what's the mincost if we painted this the jth color? (and have painted everything before it.)
for i in range(len(costs)):
dp0 = costs[i][0] + min(dp[1], dp[2])
dp1 = costs[i][1] + min(dp[0], dp[2])
dp2 = costs[i][2] + min(dp[0], dp[1])
dp = [dp0, dp1, dp2]
return min(dp)
#Runtime: O(3 * n) -> O(n)
#Space: O(3) -> O(1)
print(minCost([[17, 2, 17], [16,16,5], [14,3,19]]))
```
168
# Uncrossed Lines
You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.
We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:
nums1[i] == nums2[j], and
the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).
Return the maximum number of connecting lines we can draw in this way.
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.
```
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
#Same as the LCS problem
dp = [[0] * (len(nums2) + 1) for i in range(len(nums1) + 1)]
for i in range(len(nums1) - 1, -1, -1):
for j in range(len(nums2) - 1, -1, -1):
if nums1[i] == nums2[j]:
dp[i][j] = 1 + dp[i + 1][j + 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
return dp[0][0]
#Runtime: O(mn)
#Space: O(mn)
#Idea: finding max # of connecting lines is same as finding length of LCS.
#dp[i][j]: max LCS between nums1[i:] and nums2[j:]
```
169
# Swapping Nodes in a Linked List
You are given the head of a linked list, and an integer k.
Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).
## Footnote
Input: head = [1,2,3,4,5], k = 2
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 swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
cur = head
for i in range(k - 1):
cur = cur.next
kth = cur
left, right = head, cur
while right.next:
left = left.next
right = right.next
kth.val, left.val = left.val, kth.val
return head
#O(n)
#O(1)
```
170
# Solving Questions With Brainpower
You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].
The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you pointsi points but you will be unable to solve each of the next brainpoweri questions. If you skip question i, you get to make the decision on the next question.
For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.
Return the maximum points you can earn for the exam.
## Footnote
Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.
```
class Solution:
def mostPoints(self, questions: List[List[int]]) -> int:
# dp = {} #index: max points you can get
# dp[len(questions)] = 0
# for i in range(len(questions) - 1, -1, -1):
# curPoints, curBrain = questions[i]
# solve = curPoints + (dp[i + curBrain + 1] if i + curBrain + 1 <= len(questions) else 0)
# skip = dp[i + 1] #can take the max from i + 1 onwards
# dp[i] = max(solve, skip)
# return dp[0]
dp = {} #index: max points can get
for i in range(len(questions) - 1, -1, -1):
curPoints, curBrain = questions[i]
solve = curPoints + dp.get(i + curBrain + 1, 0)
skip = dp.get(i + 1, 0)
dp[i] = max(solve, skip)
return dp[0]
#O(n)
#O(n)
```
171
# Matrix Diagonal Sum
Given a square matrix mat, return the sum of the matrix diagonals.
Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.
## Footnote
Input: mat = [[1,2,3],
[4,5,6],
[7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.
```
class Solution:
def diagonalSum(self, mat: List[List[int]]) -> int:
n = len(mat)
res = 0
for i in range(n):
valOne = mat[i][i]
valTwo = mat[i][n - 1 - i]
res += valOne + valTwo
res -= mat[n // 2][n // 2] if n % 2 else 0
return res
#O(n) the number of rows
#O(1)
```
172
# Single-Threaded CPU
You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the ith task will be available to process at enqueueTimei and will take processingTimei to finish processing.
You have a single-threaded CPU that can process at most one task at a time and will act in the following way:
If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.
Return the order in which the CPU will process the tasks.
## Footnote
Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows:
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.
```
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
for i, t in enumerate(tasks): #enqueue, processing, index
t.append(i) #we want the index appended here too
tasks.sort() #sort by enqueue time.
res = []
time = tasks[0][0] #init as first task's time
i = 0
minHeap = [] #(processingTime, index)
while i < len(tasks) or minHeap:
while i < len(tasks) and tasks[i][0] <= time:
heapq.heappush(minHeap, (tasks[i][1], tasks[i][2]))
i += 1
if minHeap:
curProc, curIndex = heapq.heappop(minHeap)
res.append(curIndex)
time += curProc
else:
#fast forward to next available task's time, which is where i is.
time = tasks[i][0]
return res
#O(n log n) for sorting and for minHeap
#O(n) for tasks and minHeap
```
173
# Ones and Zeroes
You are given an array of binary strings strs and two integers m and n.
Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
## Footnote
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
```
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = {}
#Subproblem: considering str[i] and after, if we have allocation of m 0s and n 1s, what's the largest subset of strs?
def dfs(i, m, n):
if i == len(strs):
return 0
if (i, m, n) in dp:
return dp[i, m, n]
#Init to be result is NOT take this string.
dp[(i, m, n)] = dfs(i + 1, m, n)
mCount, nCount = strs[i].count("0"), strs[i].count("1")
if mCount <= m and nCount <= n:
#It's either max of not take this string, or you take it.
dp[(i, m, n)] = max(dp[(i, m, n)], 1 + dfs(i + 1, m - mCount, n - nCount))
return dp[(i, m, n)]
return dfs(0, m, n)
#Runtime: O(mns)
#Space: O(mns) #size of dp cache
```
174
# Count Ways To Build Good Strings
Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:
Append the character '0' zero times.
Append the character '1' one times.
This can be performed any number of times.
A good string is a string constructed by the above process having a length between low and high (inclusive).
Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 109 + 7.
## Footnote
Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation:
One possible valid good string is "011".
It can be constructed as follows: "" -> "0" -> "01" -> "011".
All binary strings from "000" to "111" are good strings in this example.
```
class Solution:
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
mod = 10 ** 9 + 7
dp = {}
#the dp[length] tracks the number of good strings we can form IF we start
#at this particular length.
def dfs(length):
if length > high:
return 0
if length in dp:
return dp[length]
#If it's in bounds of the range, the length is at least 1. Otherwise, it's
#too short for now so we'll have it be 0.
dp[length] = 1 if length >= low else 0
#Explore both branches and add those results.
dp[length] += dfs(length + zero) + dfs(length + one)
return dp[length] % mod
return dfs(0)
#Runtime: O(n) the size of the cache. 2^n became length n linked list with caching
#Space: O(n) the size of the cache
```
175
Maximum Alternating Subsequence Sum
The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices.
For example, the alternating sum of [4,2,5,3] is (4 + 5) - (2 + 3) = 4.
Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence).
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.
Input: nums = [4,2,5,3]
Output: 7
Explanation: It is optimal to choose the subsequence [4,2,5] with alternating sum (4 + 5) - 2 = 7.
```
class Solution:
def maxAlternatingSum(self, nums: List[int]) -> int:
dp = {} #(i, adding)
#adding is true if when we are on an elt, we can choose to add it.
def dfs(i, adding):
if i == len(nums):
return 0
if (i, adding) in dp:
return dp[(i, adding)]
total = nums[i] if adding else -nums[i]
dp[(i, adding)] = max(total + dfs(i + 1, not adding), dfs(i + 1, adding))
return dp[(i, adding)]
return dfs(0, True)
#Runtime: O(2 * n) -> O(n)
#Space: O(2 * n) -> O(n)
```
176
Dota2 Senate
In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:
Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.
Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".
Input: senate = "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in round 1.
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.
```
class Solution:
def predictPartyVictory(self, senate: str) -> str:
rQ = deque()
dQ = deque()
for i, c in enumerate(senate):
if c == "R":
rQ.append(i)
else:
dQ.append(i)
while rQ and dQ:
curR, curD = rQ.popleft(), dQ.popleft()
if curR < curD:
rQ.append(curR + len(senate))
else:
dQ.append(curD + len(senate))
return "Radiant" if rQ else "Dire"
#Runtime: O(n * #loops) -> think of it as O(n). technically we have log_2 (N) rounds like binary search since half of opponents gone.
#Space: O(N) #sum of rQ and dQ
```
177
# Minimum Number of Vertices to Reach All Nodes
Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.
Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.
Notice that you can return the vertices in any order.
## Footnote
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output: [0,3]
Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].
```
class Solution:
def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
res = []
incoming = defaultdict(list)
for u, v in edges:
incoming[v].append(u)
for i in range(n):
if i not in incoming:
res.append(i)
return res
#O(V + E)
#O(V + E) #for incoming
```
178
Is Graph Bipartite?
There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:
There are no self-edges (graph[u] does not contain u).
There are no parallel edges (graph[u] does not contain duplicate values).
If v is in graph[u], then u is in graph[v] (the graph is undirected).
The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.
A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
Return true if and only if it is bipartite.
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.
```
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
odd = [0] * n #1 if odd, -1 if even
def bfs(i):
if odd[i]: #means it's already visited
return True
q = deque([i])
odd[i] = -1 #When we do the BFS on this first node, we assume it's the first layer (0th layer, so that's how we mark as visited.
#this above is before we do our bfs.
while q:
for _ in range(len(q)):
cur = q.popleft()
for nei in graph[cur]:
#If in the same grouping
if odd[cur] == odd[nei]:
return False
elif odd[nei] == 0: #not visited. can also do "not odd[nei]"
q.append(nei)
odd[nei] = -1 * odd[cur]
return True
for i in range(n):
if not bfs(i):
return False
return True
#O(V + E)
#O(V + E)
```
179
# Find Unique Binary String
Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.
## Footnote
Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.
```
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
res = []
for i, n in enumerate(nums):
res.append("1" if n[i] == "0" else "0")
return "".join(res)
#https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
#O(n)
#O(n) for res
# strSet = set(nums)
# def dfs(curComb):
# if len(curComb) == len(nums):
# curStr = "".join(curComb)
# return curStr if curStr not in strSet else None
# for c in ["0", "1"]: #try both 0 or 1
# curComb.append(c)
# res = dfs(curComb)
# if res:
# return res
# curComb.pop()
# return dfs([])
# #Runtime: O(n ^ 2). O(n) is the height of the tree, then O(n) to perform the join of the array and check for inclusion
# #Space: O(n) for height of the tree
```
180
# Evaluate Division
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
```
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
adj = defaultdict(list)
for i, exp in enumerate(equations):
a, b = exp
adj[a].append([b, values[i]])
adj[b].append([a, 1 / values[i]])
def bfs(s, t):
if not adj[s] or not adj[t]:
return -1
q = deque()
q.append([s, 1])
visit = set()
visit.add(s)
while q:
for _ in range(len(q)):
curVar, curWeight = q.popleft()
if curVar == t:
return curWeight
for neiVar, neiWeight in adj[curVar]:
if neiVar not in visit:
q.append([neiVar, curWeight * neiWeight])
visit.add(neiVar)
return -1
return [bfs(q[0], q[1]) for q in queries]
#O(Q * (V + E))
#O(V + E)
```
181
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.
For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.
Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.
You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.
Return a boolean array answer, where answer[j] is the answer to the jth query.
Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.
```
class Solution:
def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
prereqs = defaultdict(list)
for pre, crs in prerequisites:
prereqs[crs].append(pre)
prereqMap = {} #maps a crs to all its indirect prerequisites (including itself)
def dfs(crs):
if crs not in prereqMap:
prereqMap[crs] = set()
for pre in prereqs[crs]:
#Set union
prereqMap[crs] = prereqMap[crs] | dfs(pre)
prereqMap[crs].add(crs)
return prereqMap[crs]
for i in range(numCourses):
dfs(i) #populate the prereqMap for indirects with the dfs call
res = []
for u, v in queries:
res.append(u in prereqMap[v])
return res
#O(V * (V + E)) #union operation of sets, times graph traversal
#O(V + E) for the graph
```
182
# Maximum Subarray Min-Product
The min-product of an array is equal to the minimum value in the array multiplied by the array's sum.
For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.
Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 109 + 7.
Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.
A subarray is a contiguous part of an array.
Input: nums = [1,2,3,2]
Output: 14
Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
2 * (2+3+2) = 2 * 7 = 14.
```
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
prefixSums = [0] #index i is the prefix sum up until but not including nums[i]
for i, n in enumerate(nums):
prefixSums.append(prefixSums[-1] + n)
res = 0
stack = [] #index, value
for i in range(len(nums)):
startIndex = i
while stack and stack[-1][1] > nums[i]:
stackIndex, stackVal = stack.pop()
stackSum = stackVal * (prefixSums[i] - prefixSums[stackIndex])
res = max(res, stackSum)
startIndex = stackIndex
stack.append((startIndex, nums[i]))
for i, n in stack:
res = max(res, n * (prefixSums[len(nums)] - prefixSums[i]))
return res % (10 ** 9 + 7)
#O(n) monotonic increasing stack.
#O(n) stack
```
183
Minimum Time to Collect All Apples in a Tree
Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.
The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
```
class Solution:
def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
def dfs(cur, par):
#base case is already handled by the time.
#Example: one node only. We just return 0 for time
#Example: two nodes 0 and 2. childTime(2) is 0. But 2 has an apple, so we return 2 for time.
time = 0
for child in adj[cur]:
if par == child:
continue
childTime = dfs(child, cur)
#If subtree has an apple. If not, does the direct child have an apple?
if childTime > 0 or hasApple[child]:
time += 2 + childTime
return time
return dfs(0, -1)
#O(V + E)
#O(V + E)
```
184
N-th Tribonacci Number
The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
```
class Solution:
def tribonacci(self, n: int) -> int:
trib = [0, 1, 1]
if n <= 2:
return trib[n]
for i in range(3, n + 1):
trib[0], trib[1], trib[2] = trib[1], trib[2], sum(trib) #sum of all 3
return trib[2]
#O(n)
#O(1)
```
185
Stone Game II
Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.
Alice and Bob take turns, with Alice starting first. Initially, M = 1.
On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).
The game continues until all the stones have been taken.
Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.
Input: piles = [2,7,9,4,4]
Output: 10
Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.
```
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
dp = {}
#Max that ALICE can get
def dfs(alice, i, M):
if i == len(piles):
return 0
if (alice, i, M) in dp:
return dp[(alice, i, M)]
res = 0 if alice else float('inf')
total = 0
for X in range(1, 2 * M + 1):
if i + X - 1 == len(piles):
break
total += piles[i + X - 1] #subtract 1 since we start at i.
if alice:
res = max(res, total + dfs(not alice, i + X, max(M, X)))
else: #if it's Bob's turn, then we minimize it
res = min(res, dfs(not alice, i + X, max(M, X)))
dp[(alice, i, M)] = res
return dp[(alice, i, M)]
return dfs(True, 0, 1)
#O(n ^ 3). O(n) indices, and M can be up to O(n). Each one has a for loop of O(n), so O(n^3) complexity.
#O(n ^ 2) for dp cache.
```
186
Maximum Subsequence Score
You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.
For chosen indices i0, i1, ..., ik - 1, your score is defined as:
The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).
Return the maximum possible score.
A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.
Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation:
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6.
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12.
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.
```
class Solution:
def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
pairs = [(n1, n2) for n1, n2 in zip(nums1, nums2)]
pairs.sort(key = lambda p: p[1], reverse = True) #descending order based on num2 values
minHeap = [] #the minimum of the values of nums1 will be what we try to remove.
curSum = 0
res = 0
#n2 is always the minimum since it's in descending order
for n1, n2 in pairs:
heapq.heappush(minHeap, n1)
curSum += n1
if len(minHeap) > k:
curSum -= heapq.heappop(minHeap)
if len(minHeap) == k:
res = max(res, curSum * n2)
return res
#O(n log n) for sort and O(n log k) for the minHeap -> O(n log n)
#O(n) for the pairs array
```
187
Minimum Fuel Cost to Report to the Capital
There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.
There is a meeting for the representatives of each city. The meeting is in the capital city.
There is a car in each city. You are given an integer seats that indicates the number of seats in each car.
A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.
Return the minimum number of liters of fuel to reach the capital city.
Input: roads = [[0,1],[0,2],[0,3]], seats = 5
Output: 3
Explanation:
- Representative1 goes directly to the capital with 1 liter of fuel.
- Representative2 goes directly to the capital with 1 liter of fuel.
- Representative3 goes directly to the capital with 1 liter of fuel.
It costs 3 liters of fuel at minimum.
It can be proven that 3 is the minimum number of liters of fuel needed.
```
class Solution:
def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
res = 0
adj = defaultdict(list)
for u, v in roads:
adj[u].append(v)
adj[v].append(u)
#returns the number of passengers that are coming from this node (including this node itself, and from its children)
def dfs(node, prev):
nonlocal res
passengers = 0
for child in adj[node]:
if child == prev:
continue
p = dfs(child, node)
#the number of passengers increment by p
#to travel from child to current node, calculate the res as seats/p.
passengers += p
res += int(ceil(p / seats)) #the number of cars needed, since each car takes one fuel, means it's the number of fuel needed.
return 1 + passengers #include 1 for current
dfs(0, -1)
return res
#O(V + E)
#O(H)
```
188
Minimum Cost to Cut a Stick
Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:
Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.
You should perform the cuts in order, you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.
Return the minimum total cost of the cuts.
Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:
The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
```
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
#Return the min cost to cut stick with endpoints l and r.
dp = {} #(l, r) -> minCost to cut rod of [l, r]
def dfs(l, r):
if r - l == 1:
return 0 #we can't cut a rod of length 1
if (l, r) in dp:
return dp[(l, r)]
res = float('inf')
for c in cuts:
if l < c < r:
res = min(res, r - l + dfs(l, c) + dfs(c, r))
dp[(l, r)] = res if res < float('inf') else 0
return dp[(l, r)]
return dfs(0, n)
#O(m^3) # we are mainly trying each possible cutting spot in cuts. so values of l and r are from cuts. Each iteration we have a loop for all cuts. Hence O(m^2) * m
#O(m^3) size of dp cache
```
189
Stone Game III
Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.
Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row.
The score of each player is the sum of the values of the stones taken. The score of each player is 0 initially.
The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.
Assume Alice and Bob play optimally.
Return "Alice" if Alice will win, "Bob" if Bob will win, or "Tie" if they will end the game with the same score.
Input: values = [1,2,3,-9]
Output: "Alice"
Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.
```
class Solution:
def stoneGameIII(self, stoneValue: List[int]) -> str:
#returns current player - other player
dp = {} #from s[i:] -> maximum current - other player
def dfs(i):
if i == len(stoneValue):
return 0
if i in dp:
return dp[i]
res = -float('inf')
for j in range(i, min(i + 3, len(stoneValue))):
total = sum(stoneValue[i: j + 1])
res = max(res, total - dfs(j + 1))
dp[i] = res
return dp[i]
res = dfs(0)
if res > 0:
return "Alice"
elif res < 0:
return "Bob"
else:
return "Tie"
#O(n): n values of i, each only takes O(3) ->O(1) for loop
#O(n) for dp cache
```
190
132 Pattern
Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
```
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
curMin = nums[0] #this is the curMin to the LEFT of the current elt.
stack = [] #2 values: current elt, and the curMin
#the stack contains elts from second element onwards.
for n in nums[1:]:
#we want the top element of the stack to always be greater than our current elt.
#The stack contains the "3", so we always want it to be larger
#Than our current elt. We want to maximize the value of this for a larger "3" for subsequent checks
while stack and n >= stack[-1][0]:
stack.pop()
if stack and n < stack[-1][0] and n > stack[-1][1]:
return True
#the stack contains the "3"
#The n is the "2"
#The curMin is the "1""
stack.append((n, curMin)) #append before updating curMin with n potnetially
curMin = min(curMin, n)
return False
#O(n)
#O(n)
```
191
Process Tasks Using Servers
You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the ith server, and tasks[j] is the time needed to process the jth task in seconds.
Tasks are assigned to the servers using a task queue. Initially, all servers are free, and the queue is empty.
At second j, the jth task is inserted into the queue (starting with the 0th task being inserted at second 0). As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the smallest weight, and in case of a tie, it is assigned to a free server with the smallest index.
If there are no free servers and the queue is not empty, we wait until a server becomes free and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned in order of insertion following the weight and index priorities above.
A server that is assigned task j at second t will be free again at second t + tasks[j].
Build an array ans of length m, where ans[j] is the index of the server the jth task will be assigned to.
Return the array ans.
Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]
Explanation: Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 2 until second 1.
- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
- At second 2, task 2 is added and processed using server 0 until second 5.
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.
```
class Solution:
def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
available = [(w, i) for i, w in enumerate(servers)] #(weight, serverIndex)]
heapq.heapify(available)
unavailable = [] #(timeBecomeFree, weight, serverIndex)
t = 0
res = [0] * len(tasks)
for i in range(len(tasks)):
#either increment t by 1, or keep t as is if advanced forward
t = max(i, t)
#If no available tasks, fast forward time.
if len(available) == 0:
t = unavailable[0][0]
#Add unavailable tasks that became available to the available heap.
while unavailable and unavailable[0][0] <= t:
time, weight, serverIndex = heapq.heappop(unavailable)
heapq.heappush(available, (weight, serverIndex))
#Process a task.
weight, serverIndex = heapq.heappop(available)
res[i] = serverIndex
#Push it to unavailable
procTime = tasks[i]
heapq.heappush(unavailable, (t + procTime, weight, serverIndex))
return res
#O(t log s) for heap operations. The size of both heaps is O(s), and we do t operations based on all the tasks.
#O(s + t). O(s) for heaps and O(t) for the res
```
192
Find Eventual Safe States
There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).
Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.
```
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
n = len(graph)
res = []
safe = {} #maps each node to whether it's safe
def dfs(i):
if i in safe:
return safe[i]
safe[i] = False #assume not safe to start
for nei in graph[i]: #graph[i] given to be all nodes adjacent to node i.
if not dfs(nei):
return False
safe[i] = True
return True
for i in range(n):
if dfs(i):
res.append(i)
return res
#O(V + E)
#O(V) for safe array
```
193
Design Parking System
Design a parking system for a parking lot. The parking lot has three kinds of parking spaces: big, medium, and small, with a fixed number of slots for each size.
Implement the ParkingSystem class:
ParkingSystem(int big, int medium, int small) Initializes object of the ParkingSystem class. The number of slots for each parking space are given as part of the constructor.
bool addCar(int carType) Checks whether there is a parking space of carType for the car that wants to get into the parking lot. carType can be of three kinds: big, medium, or small, which are represented by 1, 2, and 3 respectively. A car can only park in a parking space of its carType. If there is no space available, return false, else park the car in that size space and return true.
Input
["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
Output
[null, true, true, false, false]
Explanation
ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // return true because there is 1 available slot for a big car
parkingSystem.addCar(2); // return true because there is 1 available slot for a medium car
parkingSystem.addCar(3); // return false because there is no available slot for a small car
parkingSystem.addCar(1); // return false because there is no available slot for a big car. It is already occupied.
```
class ParkingSystem:
def __init__(self, big: int, medium: int, small: int):
self.lot = [big, medium, small]
def addCar(self, carType: int) -> bool:
if self.lot[carType - 1] > 0:
self.lot[carType - 1] -= 1
return True
return False
#O(1) for op
#O(3) -> O(1) space
Your ParkingSystem object will be instantiated and called as such:
# obj = ParkingSystem(big, medium, small)
# param_1 = obj.addCar(carType)
```
194
Find Missing Observations
You have observations of n + m 6-sided dice rolls with each face numbered from 1 to 6. n of the observations went missing, and you only have the observations of m rolls. Fortunately, you have also calculated the average value of the n + m rolls.
You are given an integer array rolls of length m where rolls[i] is the value of the ith observation. You are also given the two integers mean and n.
Return an array of length n containing the missing observations such that the average value of the n + m rolls is exactly mean. If there are multiple valid answers, return any of them. If no such array exists, return an empty array.
The average value of a set of k numbers is the sum of the numbers divided by k.
Note that mean is an integer, so the sum of the n + m rolls should be divisible by n + m.
Input: rolls = [3,2,4,3], mean = 4, n = 2
Output: [6,6]
Explanation: The mean of all n + m rolls is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.
```
class Solution:
def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
m = len(rolls)
nTotal = mean * (m + n) - sum(rolls)
if nTotal < n or nTotal > 6 * n:
return []
res = []
while nTotal > 0:
#Example: total is 14, 10 dice left. The max we can take is
# 5, so that we have nTotal = 9 and n = 9 remaining
roll = min(6, nTotal - n + 1)
res.append(roll)
nTotal -= roll
n -= 1 #remember to decrement for dice taken
return res
#O(nTotal)
#O(1) or O(n) for result
```
195
Maximum Product of the Length of Two Palindromic Subsequences
Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.
Return the maximum possible product of the lengths of the two palindromic subsequences.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.
Input: s = "leetcodecom"
Output: 9
Explanation: An optimal solution is to choose "ete" for the 1st subsequence and "cdc" for the 2nd subsequence.
The product of their lengths is: 3 * 3 = 9.
```
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
bitMap = {} #mask: length of palindromic
for mask in range(1, 1 << n): #1 << n == 2 ** n
subseq = ""
for i in range(n):
#If this AND operation is non-zero
#Example (0b10 AND 0b10 = 2.)
if mask & (1 << i):
subseq += s[i]
if subseq == subseq[::-1]:
bitMap[mask] = len(subseq)
res = 0
for mask1 in bitMap:
for mask2 in bitMap:
#If disjoint, the AND leads to 0.
if mask1 & mask2 == 0:
res = max(res, bitMap[mask1] * bitMap[mask2])
return res
#O(2^n ^ 2). 2^n possible bitMap strings, square them
#O(2^n) possible keys for bitMap.
```
196
Time Needed to Inform All Employees
A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.
Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also, it is guaranteed that the subordination relationships have a tree structure.
The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.
The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e., After informTime[i] minutes, all his direct subordinates can start spreading the news).
Return the number of minutes needed to inform all the employees about the urgent news.
Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.
```
class Solution:
def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
adj = defaultdict(list) #maps manager to employees
for i in range(len(manager)):
adj[manager[i]].append(i)
q = deque([(headID, 0)]) #node, time needed for this employee to hear the news
res = 0
while q:
for _ in range(len(q)):
curEmp, curTime = q.popleft()
res = max(res, curTime)
for nei in adj[curEmp]:
q.append((nei, curTime + informTime[curEmp]))
return res
#O(N) - Tree, visit all employees
#O(N) - Tree, add employees to queue.
```
197
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
The lock initially starts at '0000', a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".
```
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
def children(curComb):
res = []
for i in range(len(curComb)):
plusDigit = str((int(curComb[i]) + 1) % 10)
minusDigit = str(((int(curComb[i]) - 1) + 10) % 10)
res.append(curComb[:i] + plusDigit + curComb[i + 1:])
res.append(curComb[:i] + minusDigit + curComb[i + 1:])
return res
if "0000" in deadends:
return -1
visit = set(deadends)
q = deque([("0000", 0)]) #curComb, numTurns
while q:
for _ in range(len(q)):
curComb, numTurns = q.popleft()
if curComb == target:
return numTurns
for child in children(curComb):
if child not in visit:
visit.add(child)
q.append((child, numTurns + 1))
return -1
#O(10 ^ 4)
#O(10 ^ 4)
```
198
Design Underground System
An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.
Implement the UndergroundSystem class:
void checkIn(int id, string stationName, int t)
A customer with a card ID equal to id, checks in at the station stationName at time t.
A customer can only be checked into one place at a time.
void checkOut(int id, string stationName, int t)
A customer with a card ID equal to id, checks out from the station stationName at time t.
double getAverageTime(string startStation, string endStation)
Returns the average time it takes to travel from startStation to endStation.
The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.
You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.
Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]
Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15); // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20); // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38); // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12
```
class UndergroundSystem:
def __init__(self):
self.checkInMap = {} # cardId -> (startStation, checkInTime)
self.totalMap = {} #(start, end) -> [totalTime, count] #we just use array to have totalTime and count be mutable. We have totalTime and count so that we can easily compute avg, without having to sum up the length of array or something.
def checkIn(self, id: int, stationName: str, t: int) -> None:
self.checkInMap[id] = (stationName, t)
def checkOut(self, id: int, stationName: str, t: int) -> None:
startStation, checkInTime = self.checkInMap[id]
if (startStation, stationName) not in self.totalMap:
self.totalMap[(startStation, stationName)] = [0, 0]
self.totalMap[(startStation, stationName)][0] += t - checkInTime
self.totalMap[(startStation, stationName)][1] += 1
def getAverageTime(self, startStation: str, endStation: str) -> float:
curTotal, curCount = self.totalMap[(startStation, endStation)]
return curTotal / curCount
#O(1) per op
#O(n) for number of card ids (think of as O(1))
Your UndergroundSystem object will be instantiated and called as such:
# obj = UndergroundSystem()
# obj.checkIn(id,stationName,t)
# obj.checkOut(id,stationName,t)
# param_3 = obj.getAverageTime(startStation,endStation)
```
199
Reorder Routes to Make All Paths Lead to the City Zero
There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.
This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.
It's guaranteed that each city can reach city 0 after reorder.
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
```
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
edges = set()
for u, v in connections:
edges.add((u, v))
adj = defaultdict(list)
#see what all the neighbors possibly are (undirected)
for u, v in connections:
adj[u].append(v)
adj[v].append(u)
visit = set()
res = 0
#tries to reach city i (and recursively its neighbors).
#If needs to flip edge, adds to count.
def dfs(i):
nonlocal res
for nei in adj[i]:
if nei in visit:
continue #if able to reach the neighbor already, continue
if (nei, i) not in edges:
res += 1
visit.add(nei)
dfs(nei) #make sure able to reach the neighbor
visit.add(0)
dfs(0)
return res
#O(V + E)
#O(V + E)
```
200
You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.
The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range.
You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.
Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.
Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.
```
class Solution:
def maximumDetonation(self, bombs: List[List[int]]) -> int:
adj = defaultdict(list)
for i in range(len(bombs)):
x1, y1, r1 = bombs[i]
for j in range(i + 1, len(bombs)):
x2, y2, r2 = bombs[j]
d = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
if d <= r1:
adj[i].append(j)
if d <= r2:
adj[j].append(i)
#returns the number of bombs detonated, if we detonate bomb i, with
#the current visit set
def dfs(i, visit):
if i in visit:
return 0
res = 1
visit.add(i)
for nei in adj[i]:
res += dfs(nei, visit)
return res
res = 0
for i in range(len(bombs)):
res = max(res, dfs(i, set()))
return res
#O(V* (V + E))
#O(V + E)
```
201
Capacity To Ship Packages Within D Days
A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
```
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
def canShip(capacity):
count = 1 # at least one ship to start
curCap = capacity
for w in weights:
if curCap - w < 0:
count += 1
curCap = capacity
curCap -= w
return count <= days
l, r = max(weights), sum(weights)
res = r #at max, we need at least the max capacity
while l <= r:
m = l + (r - l) // 2
if canShip(m):
res = min(res, m)
r = m - 1
else:
l = m + 1
return res
#O(n * log m), where m is the max cap that's sum of weights
#O(1)
```
202
Given 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} #integer, max product
for num in range(2, n + 1):
#It's at least num if it's not n (otherwise 0 for n)
dp[num] = num if num != n else 0
for i in range(1, num): #break num into product of two
dp[num] = max(dp[i] * dp[num - i], dp[num])
return dp[n]
#O(n ^ 2): O(n) for num, O(n) for i
#O(n) for dp cache
```
203
Minimum Domino Rotations For Equal Row
In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)
We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.
Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.
If it cannot be done, return -1.
Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2
Explanation:
The first figure represents the dominoes as given by tops and bottoms: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
```
class Solution:
def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
targets = [tops[0], bottoms[0]]
for target in targets:
missTop, missBot = 0, 0
for i in range(len(tops)):
if not (tops[i] == target or bottoms[i] == target):
break
if tops[i] != target:
missTop += 1
if bottoms[i] != target:
missBot += 1
#If we were able to reach the end of the dominos, after the
#tops[i] and bots[i] check, we know all values are the same.
#Can then return minimum of number of missingT or missingB
#The outer loop is to check for validness of ANY solution -
#either match top or match bottom.
if i == len(tops) - 1:
return min(missTop, missBot)
return -1
#O(2 * n) -> O(n)
#O(1)
```
204
Number of Longest Increasing Subsequence
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
```
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
dp = {} #key = index, value = [length of LIS, count]
lenLIS, res = 0, 0 #length of LIS, count of LIS
#i = start of subseq
for i in range(len(nums) - 1, -1, -1):
#len, cnt of LIS starting from i
maxLen, maxCount = 1, 1
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]:
length, count = dp[j]
if length + 1 > maxLen:
maxLen = length + 1
maxCount = count
elif length + 1 == maxLen:
maxCount += count
if maxLen > lenLIS:
lenLIS, res = maxLen, maxCount
elif maxLen == lenLIS:
res += maxCount
dp[i] = [maxLen, maxCount]
return res
#O(n ** 2) #n values of i, n values of j
#O(n)
```
205
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
```
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
res = 1 #result is at least one point for one line.
for i in range(len(points)):
x1, y1 = points[i]
counts = defaultdict(int)
for j in range(i + 1, len(points)):
x2, y2 = points[j]
slope = None
if x1 == x2:
slope = float('inf')
else:
slope = (y2 - y1) / (x2 - x1)
counts[slope] += 1
#Plus one since we need to account for original p1
res = max(res, counts[slope] + 1)
return res
#This solution works - we don't worry about parallel lines
#This is because we calculate number of points with the same slope, ASSUMING p1 is on the longest line.
#O(n ^ 2)
#O(n) for all possible slopes
```
206
# Longest Substring Without Repeating Characters
Given a string s, find the length of the longest
substring
without repeating characters.
## Footnote
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l = 0
charSet = set()
res = 0
for r in range(len(s)):
while s[r] in charSet:
charSet.remove(s[l])
l += 1
charSet.add(s[r])
res = max(res, r - l + 1)
return res
#O(n)
#O(26) -> O(1)
#Sliding window
```
207
Zigzag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
```
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
increment = 2 * (numRows - 1)
res = []
for r in range(numRows):
for i in range(r, len(s), increment):
res.append(s[i])
if r > 0 and r < numRows - 1 and i + increment - 2 * r < len(s):
res.append(s[i + increment - 2 * r])
return "".join(res)
#O(n)
#O(1)
```
208
Construct Quad Tree
Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.
Return the root of the Quad-Tree representing grid.
A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:
val: True if the node represents a grid of 1's or False if the node represents a grid of 0's. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.
isLeaf: True if the node is a leaf node on the tree or False if the node has four children.
We can construct a Quad-Tree from a two-dimensional area using the following steps:
If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
Recurse for each of the children with the proper sub-grid.
Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.
```
"""
# Definition for a QuadTree node.
class Node:
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
"""
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
#(r, c) is the topLeft of a quadtree section.
def dfs(r, c, n):
allSame = True
for i in range(n):
for j in range(n):
if grid[r][c] != grid[r + i][c + j]:
allSame = False
break
if allSame:
#If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
root = Node(grid[r][c], True)
return root
else:
#If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
topLeft = dfs(r, c, n // 2)
bottomLeft = dfs(r + n // 2, c, n // 2)
topRight = dfs(r, c + n // 2, n // 2)
bottomRight = dfs(r + n // 2, c + n // 2, n // 2)
root = Node(0, False, topLeft, topRight, bottomLeft, bottomRight)
return root
return dfs(0, 0, len(grid))
#Runtime: O(n^2*log n). Log n subdivisions, each O(n^2) to check if all values same
#Space: O(log n) for call stack
```
209
Sum Root to Leaf Numbers
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, curPath):
if not node:
return 0
curPath = curPath * 10 + node.val
if not node.left and not node.right:
return curPath
return dfs(node.left, curPath) + dfs(node.right, curPath)
return dfs(root, 0)
#O(n)
#O(h)
```
210
IPO
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.
You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.
Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.
Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.
The answer is guaranteed to fit in a 32-bit signed integer.
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
```
class Solution:
def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
maxProfits = [] #maxHeap of valid profits that fall under the current capital w
minCapital = [(c, p) for c, p in zip(capital, profits)] #minHeap of (capital, profit) pairs.
heapq.heapify(minCapital)
#The idea is that we'll always pop from minCapitals while the capital is less than w and add to maxProfits. We then take from maxProfits
#We're taking k projects
for i in range(k):
while minCapital and minCapital[0][0] <= w:
#pop all valid capital profit pairs.
c, p = heapq.heappop(minCapital)
heapq.heappush(maxProfits, -p)
if not maxProfits:
break
w += -heapq.heappop(maxProfits)
return w
#Runtime: O(k * 2 * log n) -> O(k log n)
#Space: O(n)
```
211
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("@")
local = local.replace(".", "")
local = local.split('+')[0]
unique.add((local, domain))
return len(unique)
#O(n)
#O(n)
```
212
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
class Solution:
def validPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
skipLeft = s[l + 1: r + 1]
skipRight = s[l: r]
return skipLeft == skipLeft[::-1] or skipRight == skipRight[::-1]
l += 1
r -= 1
return True
#O(n)
213
# Count Sub Islands
You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.
An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.
Return the number of islands in grid2 that are considered sub-islands.
Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output: 3
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.
```
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
ROWS, COLS = len(grid1), len(grid1[0])
visit = set()
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
#Assume True
#Out of bounds is true
#if water is out of bounds
#If island land piece is visited then is also true
def dfs(r, c):
if r < 0 or r == ROWS or c < 0 or c == COLS or not grid2[r][c] or (r, c) in visit:
return True
visit.add((r, c))
res = True
if grid2[r][c] and not grid1[r][c]:
res = False
#Before we return, make sure to visit the rest of the subisland
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
res = dfs(neiR, neiC) and res
return res
res = 0
for r in range(ROWS):
for c in range(COLS):
if (r, c) not in visit and grid2[r][c] and dfs(r, c):
res += 1
return res
#O(mn)
#O(mn)
```
214
Data Stream as Disjoint Intervals
Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.
Implement the SummaryRanges class:
SummaryRanges() Initializes the object with an empty stream.
void addNum(int value) Adds the integer value to the stream.
int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi]. The answer should be sorted by starti.
Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1); // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3); // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7); // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2); // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]
```
from sortedcontainers import SortedDict
class SummaryRanges:
def __init__(self):
self.treeMap = SortedDict()
def addNum(self, value: int) -> None:
self.treeMap[value] = True #we're just using the first part of it
def getIntervals(self) -> List[List[int]]:
res = []
for n in self.treeMap:
if res and n == res[-1][1] + 1:
res[-1][1] = n
else:
res.append([n, n])
return res
#O(log n) for insert, O(n) for getIntervals
#O(n) for the treeMap.
Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(value)
# param_2 = obj.getIntervals()
```
215
# Restore IP Addresses
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
```
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
if len(s) > 12:
return []
res = []
def dfs(i, dots, curIP):
#For a base case, cover both the dots and the i condition.
if i == len(s) and dots == 4:
res.append(curIP[:-1])
return
if dots > 4 or i == len(s): #more than 4 dots, or not equal to 4 dots but i == len(s)
return
#Place a dot
for j in range(i, min(i + 3, len(s))):
if int(s[i: j + 1]) <= 255 and (i == j or (s[i] != "0")):
dfs(j + 1, dots + 1, curIP + s[i: j + 1] + ".")
dfs(0, 0, "")
return res
#O(3^n) for 3 choices of dot placements, but bounded -> O(1) #limited # of ip addresses
#O(1)
```
216
Palindrome Partitioning
Given a string s, partition s such that every
substring
of the partition is a
palindrome
. Return all possible palindrome partitioning of s.
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
```
class Solution:
def partition(self, s: str) -> List[List[str]]:
curPart = []
res = []
def dfs(i):
if i == len(s):
res.append(curPart.copy())
return
for j in range(i, len(s)):
#Take the first partition
if self.isPali(i, j, s):
curPart.append(s[i: j + 1]) #python exclusion
#Continue taking 2nd+ partitions onwards
dfs(j + 1)
curPart.pop() #Cleanup
dfs(0)
return res
def isPali(self, i, j, s):
l, r = i, j
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
#Runtime: O(2^N subproblems * N for the palindromecheck) -> O(2^N * N)
#Space: O(N) recursion stack
```
217
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
void add(key) Inserts the value key into the HashSet.
bool contains(key) Returns whether the value key exists in the HashSet or not.
void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.
Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]
Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // return False, (already removed)
```
# class ListNode:
# def __init__(self, val):
# self.val = val
# self.next = None
class MyHashSet:
def __init__(self):
self.hashSet = [ListNode(0) for i in range(10000)]
def add(self, key: int) -> None:
idx = key % 10000
cur = self.hashSet[idx]
while cur.next:
if cur.next.val == key: #check it on the next value
return
cur = cur.next
cur.next = ListNode(key)
def remove(self, key: int) -> None:
idx = key % 10000
cur = self.hashSet[idx]
while cur.next:
if cur.next.val == key:
cur.next = cur.next.next
return #stop once you're done!
cur = cur.next
def contains(self, key: int) -> bool:
idx = key % 10000
cur = self.hashSet[idx]
while cur.next:
if cur.next.val == key:
return True
cur = cur.next
return False
#O(1) with chaining and such
#O(10000)
Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
```
218
Number of Ways to Rearrange Sticks With K Sticks Visible
There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.
For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.
Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 109 + 7.
Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.
```
class Solution:
def rearrangeSticks(self, n: int, k: int) -> int:
dp = {} #(N, K)
def dfs(n, k):
if n == k:
return 1
if n == 0 or k == 0:
return 0
if (n, k) in dp:
return dp[(n, k)]
#put tallest stick in back is one option
#put any other stick in back. That one is not visible
#since the tallest one will always block it.
#There are n - 1 of these options.
#this modding here is just for leetcode.
dp[(n, k)] = (dfs(n - 1, k - 1) + (n - 1) * dfs(n - 1, k)) % (10 ** 9 + 7)
return dp[(n, k)]
return dfs(n, k) % (10 ** 9 + 7)
#O(nk)
#O(nk)
```
219
Maximum Performance of a Team
You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.
Choose at most k different engineers out of the n engineers to form a team with the maximum performance.
The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation:
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.
```
class Solution:
def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
#sort by decreasing efficiency.
pairs = []
for e, s in zip(efficiency, speed):
pairs.append((e, s))
pairs.sort(reverse = True)
minHeap = [] #minHeap of speeds
totalSpeed = 0
res = 0
for efficiency, speed in pairs:
#if the minHeap is size k now, we want to pop it now so we have room to add something to it.
if len(minHeap) == k:
minSpd = heapq.heappop(minHeap)
totalSpeed -= minSpd
totalSpeed += speed
heapq.heappush(minHeap, speed)
res = max(efficiency * totalSpeed, res)
return res % (10 ** 9 + 7)
#O(n log n + n log k)
#O(n) for pairs
```
