150

Question 1

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1’s not connected to any other 1’s. There are exactly two islands in grid.

You may change 0’s to 1’s to connect the two islands to form one island.

Return the smallest number of 0’s you must flip to connect the two islands.
Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Answer 1

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        visit = set()
        ROWS, COLS = len(grid), len(grid[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        #DFS is to populate visit set with 1s.
        def dfs(r, c):
            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))
            for dr, dc in directions:
                dfs(r + dr, c + dc)
        
        #Multisource BFS from one island to the other
        def bfs():
            q = deque(visit)
            res = 0
            while q:
                for _ in range(len(q)):
                    r, c = q.popleft()
                    for dr, dc in directions:
                        neiR, neiC = r + dr, c + dc
			#The out of bounds check is on neighbors, not on (r, c). We assume r c looks good before adding.
                        if neiR < 0 or neiR == ROWS or neiC < 0 or neiC == COLS or (neiR, neiC) in visit:
                            continue #do not check for grid[neiR][neiC] == 0, because we can flip 0s to 1s
                        if grid[neiR][neiC] == 1:
                            return res
                        q.append((neiR, neiC))
                        visit.add((neiR, neiC))
                res += 1
            return res
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    dfs(r, c)
                    return bfs()
        #O(nm)
        #O(nm)

Question 2

Copy List Random Pointer(self, head)

Answer 2

class Node:
    def \_\_init\_\_(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        oldToCopy = {None: None} #none maps to none.
        cur = head
        while cur:
            copyNode = Node(cur.val)
            oldToCopy[cur] = copyNode
            cur = cur.next
        
        cur = head
        while cur:
            copyNode = oldToCopy[cur]
            copyNode.next = oldToCopy[cur.next]
            copyNode.random = oldToCopy[cur.random]
            cur = cur.next
        return oldToCopy[head]
        #Runtime: O(n) to copy all the nodes, then O(n) to set pointers
        #Space: O(n) for the mapping of old to new nodes.

Question 3

Given a string s containing only three types of characters: ‘(‘, ‘)’ and ‘*’, return true if s is valid.

Answer 3

class Solution:
    def checkValidString(self, s: str) -> bool:
        leftMin, leftMax = 0, 0
        for c in s:
            if c == "(":
                leftMin, leftMax = leftMin + 1, leftMax + 1
            elif c == ")":
                leftMin, leftMax = leftMin - 1, leftMax - 1
            else: #wild card. Close min, and open max 
                leftMin, leftMax = leftMin - 1, leftMax + 1
            if leftMax < 0: #Example: ")" leftMax is negative.
                return False
            if leftMin < 0: #(*)( this is false, but if we don't reset leftMin to zero, will return True since leftMin is 0
                leftMin = 0
        return leftMin == 0
        #O(n)
        #O(1)
        #Greedy solution

Question 4

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Answer 4

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            if numbers[l] + numbers[r] < target:
                l += 1
            elif numbers[l] + numbers[r] > target:
                r -= 1
            else:
                #Due to answer wanting one-indexing
                return [l + 1, r + 1]
        #O(n)
        #O(1)

        

Question 5

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Answer 5

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        l, r = 0, len(height) - 1
        maxL, maxR = height[l], height[r]
        #We use the minimum of MAXIMUM heights to our left and right.
        res = 0
        while l < r:
            if maxL < maxR:
                l += 1
                #
                water = max(maxL - height[l], 0)
                res += water
                maxL = max(maxL, height[l])
            else:
                r -= 1
                water = max(maxR - height[r], 0)
                res += water
                maxR = max(maxR, height[r])
        return res
        #O(n)
        #O(1)
#We increment l and decrement r first BEFORE doing the computation, because:
# 1) the boundaries cannot contain any water
# 2) After incrementing, maxL and maxR hasn't been updated yet, so will properly reflect "left" and "right" of the current height tile.In other words... after pushing, we're at a state where maxL is to our left! This makes sense.. initially, zero water trapped at edges
# 3) Compute the water and add to result. It's possible the computation is negative, so max it with 0.
# 4) THEN we updated maxL and maxR. This is because now we have considered this tile of height as potentially max, so now new maxL and maxR will be used in computation. We use the max function here, BECAUSE the amount of water bounded is: we take the minimum of the
#maximum heights to the left and right.

        

Question 6

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

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

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

Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[”..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Answer 6

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        cols = set()
        posDiag = set() # r - c
        negDiag = set() # r + c
        board = [["."] * n for i in range(n)]
        res = []
        
        def backtrack(r):
            if r == n:
                boardCopy = ["".join(row) for row in board]
                res.append(boardCopy)
                return 
            
            for c in range(n):
                if c in cols or r - c in negDiag or r + c in posDiag:
                    continue
                
                #Place the queen
                board[r][c] = "Q"
                cols.add(c)
                negDiag.add(r - c)
                posDiag.add(r + c)

                backtrack(r + 1)
                
                #backtrack
                board[r][c] = "."
                cols.remove(c)
                negDiag.remove(r - c)
                posDiag.remove(r + c)
        backtrack(0)
        return res
        #Runtime: O(n!) #n queens for first slot, n - 1 fow next row, etc...
        #Space: O(n ^ 2) for the board

Question 7

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice’s hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Answer 7

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False
        counts = {}
        for n in hand:
            counts[n] = counts.get(n, 0) + 1
        minHeap = list(counts.keys())
        heapq.heapify(minHeap)
        while minHeap:
            first = minHeap[0]
            for card in range(first, first + groupSize):
                if card not in counts: #if the necessary card isn't in our counts, immediately return False
                    return False
                counts[card] -= 1
                if counts[card] == 0:
                    #if at any point we're trying to pop from the middle,
                    #return False since that means we have a smaller value 
                    #we can't make a straight from later on.
                    #Also we need minHeap[0] NOT first. This is because
                    #we can be making cards for a subsequent iteration where
                    #first is not the minHeap[0] at that time.
                    #Example: first = 2, but making cards for 3, 4
                    #which are both at count 1. We decrement 1 for card i = 3, 
                    #and then we see minHeap[0] == 3, so we pop from minHeap
                    #We don't compare it against FIRST!
                    if card != minHeap[0]:
                        return False
                    else:
                        heapq.heappop(minHeap)
        return True
        #O(n log n) #primarily heap operations to assemble heap and pop from it
        #O(n) for the heap

Question 8

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Input: board =
[[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]
,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]
,[”.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]
,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]
,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]
,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]
,[”.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]
,[”.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]
,[”.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
Output: true

Answer 8

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # rows = defaultdict(set) #r -> values in that r
        # cols = defaultdict(set) #c - > values in tha c
        # square = defaultdict(set) #(r // 3, c // 3) - > values in that square

        rows = {i: set() for i in range(9)}
        cols = {i: set() for i in range(9)}
        square = {(i, j): set() for i in range(3) for j in range(3)}

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if board[r][c] in rows[r] or board[r][c] in cols[c] or board[r][c] in square[(r // 3, c // 3)]:
                    return False
                rows[r].add(board[r][c])
                cols[c].add(board[r][c])
                square[(r // 3, c // 3)].add(board[r][c])
        return True
        #O(81) -> O(1)
        #O(81) -> O(1)

Question 9

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

Answer 9

class MinStack:

    def \_\_init\_\_(self):
        self.stack = []
        self.minStack = []
        

    def push(self, val: int) -> None:
        self.stack.append(val)
        curMin = min(val, self.minStack[-1]) if self.minStack else val
        self.minStack.append(curMin)
        

    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()
        

    def top(self) -> int:
        return self.stack[-1]
        

    def getMin(self) -> int:
        return self.minStack[-1]
    #O(1) per op
    #O(n) space for both
    
        

Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

Question 10

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Answer 10

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return -1
        #O(log n)
        #O(1)

Question 11

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/’.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Answer 11

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for c in tokens:
            if c == "+":
                stack.append(stack.pop() + stack.pop())
            elif c == "*":
                stack.append(stack.pop() * stack.pop())
            elif c == "-":
                second = stack.pop()
                first = stack.pop()
                stack.append(first - second)
            elif c == "/":
                second = stack.pop()
                first = stack.pop()
                stack.append(int(first / second))
            else:
                stack.append(int(c))
        return stack[0]
        #O(n)
        #O(n)
        

Question 12

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Answer 12

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        
        ROWS, COLS = len(grid), len(grid[0])
        q = deque()
        fresh = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    fresh += 1
                if grid[r][c] == 2:
                    q.append((r, c))
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        time = 0
        #Mistake here: Need AND instead of or. This is because if unreachable orange, this will be stuck 
        #in infinite loop
        #No need for visit set, because the number of reachable fresh oranges turning rotten will limit our queue and exit us.
        while q and fresh > 0: 
            for _ in range(len(q)):
                r, c = q.popleft()
                for dr, dc in directions:
                    neiR, neiC = r + dr, c + dc
                    if neiR < 0 or neiR == ROWS or neiC < 0 or neiC == COLS:
                        continue
                    if grid[neiR][neiC] == 1:
                        grid[neiR][neiC] = 2
                        fresh -= 1
                        q.append((neiR, neiC))
            time += 1
        return time if fresh == 0 else -1
        #O(mn) for prework init and BFS
        #O(mn) since we have a q

Question 13

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Answer 13

# Definition for singly-linked list.
# class ListNode:
#     def \_\_init\_\_(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        groupPrev = dummy
        while True:
            #Don't use cur. Use groupPrev so that you can probably move along!
            #1) Find the kth node.
            kth = self.getKth(groupPrev, k)
            if not kth:
                break
            #2) Reverse everything in the k group, and make sure the final node points to groupNext instead of None
            # So for example, dummy   2->1->3->4->5
            groupNext = kth.next
            prev, cur = kth.next, groupPrev.next
            #Instead of cur: (cur != None)
            while cur != groupNext: 
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            #The node to assign groupPrev to is groupPrev.next
            #NOT k.next. This is because k group can be of size more than 2... 
            #3) From dummy   2->1->3->4->5, we want to
            #Point grouPrev(dummy) to 2 (kth), leading to dummy->2->1->3->4->5
            #Have groupPrev be updated to 1. To get this, that was the original groupPrev.next
            tmp = groupPrev.next
            groupPrev.next = kth
            groupPrev = tmp
        return dummy.next

    def getKth(self, node, k):
        while node and k > 0:
            node = node.next
            k -= 1
        return node
    #O(n) 
    #O(1)

Question 14

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

Answer 14

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        stack = []
        res = []
        #Can add left if open < n
        #Can add closed if closed < open
        #Valid result if open == closed == n
        def backtrack(openCount, closedCount):
            if openCount == closedCount == n: 
             #no need to .copy() since we're OK with a global stack. We don't append the stack value, but instead the string, and that string won't change!! "".join(stack)
                res.append("".join(stack))
                return 
            if openCount < n:
                stack.append("(")
                backtrack(openCount + 1, closedCount)

                stack.pop()
            if closedCount < openCount:
                stack.append(")")
                backtrack(openCount, closedCount + 1)
                stack.pop()
        backtrack(0, 0)
        return res
        #Runtime: O(2^(2n) #2 choices of open or closed at each step of decision tree, and 2n steps -> O(4^n)
        #Space: O(2*n) for the height - the recursion stack

Question 15

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Answer 15

"""
# Definition for a Node.
class Node:
    def \_\_init\_\_(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        oldToCopy = {None: None}
        cur = head
        while cur:
            copyNode = Node(cur.val)
            oldToCopy[cur] = copyNode
            cur = cur.next
        
        cur = head
        while cur:
            copyNode = oldToCopy[cur]
            copyNode.next = oldToCopy[cur.next]
            copyNode.random = oldToCopy[cur.random]
            cur = cur.next
        return oldToCopy[head]
        #O(n) for pointer traversal and init of hashmap
        #O(n) for storage of all the nodes mapped to copies

Question 16

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Input: nums = [1,3,4,2,2]
Output: 2

Answer 16

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        #think of the values of the array as pointers to INDICES
        #of the array
        #So 2 showing pointing up twice means that index 2 is pointed to twice by index 3 and 4 respectively.
        #So the draw the graph: index i points to nums[i]
        #0->1, 1->3, 2->4, 3->2, 4->2

        #slow and fast are indices - find collision for Floyd
        while True: #this one, you can't do while fast and fast.next, so just do while True.
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow2 = 0
        while slow != slow2:
            slow = nums[slow]
            slow2 = nums[slow2]
        return slow
        #O(n) for pointers traversals 
        #O(1) no extra mem
        #This is a LL problem because nothing points back to 0
        #which is where we start, since everything is [1, n].
        #So a cycle exists and the first chunk is always not a cycle.

Question 17

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Input: piles = [3,6,7,11], h = 8
Output: 4

Answer 17

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        k = max(piles) #or inf
        while l <= r:
            mid = l + (r - l) // 2
            numHours = 0
            for p in piles:
                numHours += ceil(p / mid)
            #need to eat faster
            if numHours > h:
                l = mid + 1
            else:
                #Set the best k so far
                k = mid #can also do min(mid, k) but unneeded.
                r = mid - 1
        return k
        #O(# piles * log(max(piles))) for binary search
        #O(1) no additional pointers
        

Question 18

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Answer 18

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        q = deque([root])
        res = []
        while q:
            rightVal = None
            for _ in range(len(q)):
                cur = q.popleft()
                rightVal = cur.val
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            res.append(rightVal)
        return res
        #O(N) for bfs traversal number of nodes
        #O(N) space for the queue.
        

Question 19

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Answer 19

# 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 goodNodes(self, root: TreeNode) -> int:
        def dfs(root, maxSoFar):
            if not root:
                return 0
            curCount = 1 if root.val >= maxSoFar else 0
            maxVal = max(root.val, maxSoFar)
            leftCount = dfs(root.left, maxVal)
            rightCount = dfs(root.right, maxVal)
            return curCount + leftCount + rightCount
        return dfs(root, root.val) #Can just pass in root.val for maxSoFar. Ok to be >=
        #Runtime: O(N) -> DFS traverse all the nodes
        #Space: O(h) -> recursion stack to the bottom

        

Question 20

Given a binary tree, determine if it is
height-balanced
.

Output: true Input: root = [3,9,20,null,null,15,7]

Answer 20

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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        #This dfs returns the height and whether it is balanced
        def dfs(root):
            if not root:
                return [0, True]
            leftHeight, leftBalanced = dfs(root.left)
            rightHeight, rightBalanced = dfs(root.right)
            curHeight = 1 + max(leftHeight, rightHeight)
            curBalanced = leftBalanced and rightBalanced and abs(leftHeight - rightHeight) <= 1
            return [curHeight, curBalanced]
        return dfs(root)[1]
        #O(N) for dfs traversal and calculation of heights and balanced values
        #O(H) for the recursion stack to go down the tree

Question 21

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Answer 21

# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        #This problem is similar to binary tree max path sum, but this counts
        #number of edges instead of the sum of the node values
        #returns the number of edges up to the root, without splitting
        maxDiameter = [0]
        def dfs(root):
            if not root:
                return -1
            #Max diameter passing through this root is the sum of the edges 
            #from left -> root + right -> root (WITH SPLIT)
            #A node with only two children returns 0
            leftHeight, rightHeight = dfs(root.left), dfs(root.right)
            maxDiameter[0] = max(maxDiameter[0], 2 + leftHeight + rightHeight)
            #Only 1 edge to either left or right (no split)
            return 1 + max(leftHeight, rightHeight)
        dfs(root)
        return maxDiameter[0]
        #O(N) all nodes
        #O(H) for recursion stack
        

Question 22

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Answer 22

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [] #two values: index, curTemp
        res = [0] * len(temperatures)
        for i, curTemp in enumerate(temperatures):
            while stack and stack[-1][1] < curTemp:
                stackIdx, stackTemp = stack.pop()
                res[stackIdx] = i - stackIdx
            stack.append((i, curTemp))
        return res
        #O(n) traverse only once, push and pop stack only once
        #O(n) for the stack
        

Question 23

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Input
[“KthLargest”, “add”, “add”, “add”, “add”, “add”]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8

Answer 23

class KthLargest:

    def \_\_init\_\_(self, k: int, nums: List[int]):
        #minHeap of size k. Minimum is the kth largest element
        self.k = k
        self.minHeap = nums
        heapq.heapify(self.minHeap)
        while len(self.minHeap) > k:
            heapq.heappop(self.minHeap)
        

    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val)
        if len(self.minHeap) > self.k:
            heapq.heappop(self.minHeap)
        return self.minHeap[0]
    #Runtime: O(n) for init if call heapify, O(log n) every add operation
    #Space: O(n) for the minHeap
        

Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

Question 24

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 the heaviest two stones and smash them together. Suppose the heaviest two 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 weight of the last remaining stone. If there are no stones left, return 0.

Answer 24

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        maxHeap = [-s for s in stones]
        heapq.heapify(maxHeap)
        while len(maxHeap) > 1:
            heaviest = -heapq.heappop(maxHeap)
            secondHeaviest = -heapq.heappop(maxHeap)
            diff = heaviest - secondHeaviest
            if diff > 0:
                heapq.heappush(maxHeap, -diff)
        return -maxHeap[0] if maxHeap else 0
        #Runtime: O(n log n) - O(n) heap init, n pops of heap
        #Space: O(n) for heap

Question 25

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Answer 25

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        rank = [1] * (n + 1) #nodes go from 1 to n. 
        par = [i for i in range(n + 1)]

        def find(n1):
            p = par[n1]
            while p != par[p]:
                #Path compression
                par[p] = par[par[p]]
                p = par[p]
            return p
        def union(n1, n2):
            p1, p2 = find(n1), find(n2)
            if p1 == p2: #Already unioned, so this is a redundant edge
                return False
            if rank[p1] < rank[p2]:
                rank[p2] += rank[p1]
                par[p1] = p2
            else:
                rank[p1] += rank[p2]
                par[p2] = p1
            return True

        for u, v in edges:
            if not union(u, v):
                return (u, v)
        # O(E) same as O(V) in this problem.
        #Runtime: O(V + E*(inverse ackerman V)) -> O(V + E) -> O(V)
        #For init is O(V).  Then for each edge E, the find operation takes inverse ackermann
        #Space: O(V)
        

Question 26

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Input: board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]
Output: [[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]
Explanation: Notice that an ‘O’ should not be flipped if:
- It is on the border, or
- It is adjacent to an ‘O’ that should not be flipped.
The bottom ‘O’ is on the border, so it is not flipped.
The other three ‘O’ form a surrounded region, so they are flipped.

Answer 26

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        ROWS, COLS = len(board), len(board[0])
        #Key insight: Capture everything EXCEPT unsurrounded regions
        #No need for visit set, since exiting out is based on the values of the board
        #and you need to traverse this matrix multiple times.

        #Purpose of dfs: mark all unsurrounded regions with a "T"
        def dfs(r, c):
            if r < 0 or r == ROWS or c < 0 or c == COLS or board[r][c] != "O":
                return
            board[r][c] = "T"
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)
        
        #1) Mark all unsurrounded regions (connected to border) as "O" -> "T"
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
                    dfs(r, c)
        
        #2) Flip all Os into Xs
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"
        
        #3) Flip all Ts to Os.
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "T":
                    board[r][c] = "O"
    #Runtime: O(mn) for the dfs recursion, double for loops for marking etc
    #Space: O(mn) in theory for the recursion stack but actually much less than that in practice, since we're breaking out of cells early.

Question 27

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5], triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].
Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.

Answer 27

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        #represents which of the indices of target we have matched successfully. want 
        #this to be size 3
        haveIndices = set() 
        for t in triplets:
            if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
                continue
            for i, n in enumerate(t):
                if n == target[i]:
                    haveIndices.add(i)
        return len(haveIndices) == 3
        #O(n) runtime for all triplets
        #O(3) -> O(1) for the have indices set

Question 28

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.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Answer 28

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        visit = set()
        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 (r, c) in visit or grid[r][c] == 0:
                return 0
            #Add to visit set inside the DFS
            visit.add((r, c))
            curArea = 1
            for dr, dc in directions:
                curArea += dfs(r + dr, c + dc)
            return curArea
        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                #OK to not have any conditional here. This does help with eliminating unnecesasry dfs calls tho - see number of islands.
                if grid[r][c] == 1 and (r, c) not in visit:
                    res = max(res, dfs(r, c))
        return res
        #O(mn) for bfs traversal and double for loop
        #O(mn) for the recursion - let's say everything is an island.
        

Question 29

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 bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Answer 29

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        prereqMap = {i: set() for i in range(numCourses)}
        for crs, pre in prerequisites:
            prereqMap[crs].add(pre)
        visit, cycle = set(), set()
        res = []
        def dfs(c):
            if c in cycle:
                return False
            if c in visit:
                return True
            #currently adding this crs to the path
            cycle.add(c)
            for pre in prereqMap[c]:
                if not dfs(pre): #if any prereqs lead to cycles
                    return False
            cycle.remove(c)
            #Was successful in visiting prereqs, so add cur to result
            res.append(c)
            visit.add(c)
            return True
        
        for crs in range(numCourses):
            if not dfs(crs):
                return []
        return res
        #O(V + E) for traversal of all the nodes and edges and init of prereq map
        #O(V + E) for prereqMap init and traversal of all nodes and edges

Question 30

You are given an m x n grid rooms initialized with these three possible values.

-1 A wall or an obstacle.
0 A gate.
INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Answer 30

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        #Multisource BFS from all the gates. Starts at distance 0, increment per layer, fill out all the empty rooms with these level distances
        #And don't revisit cells, so we'll keep a visit set()
        ROWS, COLS = len(rooms), len(rooms[0])
        visit = set()
        q = deque([])
        #Initialize visit set and queue with the gates
        for r in range(ROWS):
            for c in range(COLS):
                if rooms[r][c] == 0:
                    visit.add((r, c))
                    q.append((r, c))
        
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        dist = 0 #initialize outside of queue, otherwise gets reset
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                rooms[r][c] = dist #just set the distance. (r, c) here is either
                #1) a gate which we don't care about, because we initialize with gates, we'll never visit gates again and overwritten their values or #2) an empty room which we do care about
                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 rooms[neiR][neiC] != -1: #is not a wall.
                        visit.add((neiR, neiC))
                        q.append((neiR, neiC))
            dist += 1
        return rooms
        #O(mn) for init with gates, BFS traversal
        #O(mn) for visit set and q

Question 31

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

Answer 31

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        digitToLetter = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno",
        "7": "pqrs", "8": "tuv", "9": "wxyz"}
        
        res = []
        
        def dfs(i, curComb):
            if i == len(digits):
                res.append(curComb)
                return

            for c in digitToLetter[digits[i]]:
                dfs(i + 1, curComb + c)
        dfs(0, "")
        return res
        #Runtime: O(4^n * n): maximally 4 letter options for each digit, and takes n time to build the string when do string addition for the curComb, where n is length of digits string
        #Space: O(4^n * n) for result, or O(n) for recursion stack 
            
        

Question 32

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Answer 32

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])
        top, bot = 0, ROWS - 1

        #Goal is to identify which row we need to be in!
        while top <= bot:
            midR = top + (bot - top) // 2
            if matrix[midR][0] <= target and target <= matrix[midR][-1]:
                break
            elif target > matrix[midR][-1]:
                top = midR + 1
            else:
                bot = midR - 1
        #Need this conditional check here. If pointers crossed and wasn't able to break out of the loop properly, means there is no valid row for which the target could possibly be in (still don't know if target exists yet tho)
        if not top <= bot:
            return False
        #See if target actually exists
        midR = top + (bot - top) // 2

        l, r = 0, COLS - 1
        while l <= r:
            mid = l + (r - l) // 2
            if matrix[midR][mid] == target:
                return True
            elif matrix[midR][mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return False
        #O(log m + log n) -> O(log (mn)) for 2 binary searches
        #O(1) only using 4 pointers

Question 33

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Answer 33

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for n in nums:
            res ^= n
        return res
        #O(n) #for all the nums
        #O(1) for single variable
        #0 XOR a = a
        #a XOR a = 0 (since 1 XOR 1 is 0)
        #So the pairs XOR each other to be 0, and so remaining one will be the answer.

Question 34

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Answer 34

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort() #sort so similar elts are next to each other
        curComb = []
        
        def dfs(i, curSum):
            if curSum == target:
                res.append(curComb.copy())
                return
            if i == len(candidates) or curSum > target:
                return
            #Include candidates[i]
            curComb.append(candidates[i])
            dfs(i + 1, curSum + candidates[i])
            curComb.pop()

            #Don't include ANY candidates[i]
            while i + 1 < len(candidates) and candidates[i + 1] == candidates[i]:
                i += 1
            #at this point, i is on the last elt in that chain. 
            #Don't include the above combination
            dfs(i + 1, curSum)
        dfs(0, 0)
        return res
        #O(Nlog N + 2^N * N) for each elt it's either part of comb or not. Then O(N) to do a curComb copy(). Can say 2^N if we ignore that
        #O(N) for recursion stack or O(2^N * N) for result 

Question 35

Given an integer array nums that may contain duplicates, return all possible
subsets
(the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Answer 35

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        curSub = []
        res = []
        def dfs(i):
            if i == len(nums):
                res.append(curSub.copy())
                return 
            
            #Take nums[i]
            curSub.append(nums[i])
            dfs(i + 1)
            curSub.pop()

            #Don't take any nums[i]
            while i + 1 < len(nums) and nums[i + 1] == nums[i]:
                i += 1
            dfs(i + 1)
        dfs(0)
        return res 
    #Runtime: O(n log n + 2^n * n) Sorting + decision to take or not take, then length n to copy each subset
    #Space: O(n) recursion stack, or (2^n * n)  for result

Question 36

Given an integer array nums of unique elements, return all possible
subsets
(the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Answer 36

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        curSub = []
        def dfs(i):
            if i == len(nums):
                res.append(curSub.copy())
                return
            #take nums[i]
            curSub.append(nums[i])
            dfs(i + 1)
            curSub.pop()

            #Don't take nums[i]
            #Since we're given everything is unique, no need for the while loop.
            dfs(i + 1)
        dfs(0)
        return res
        #Runtime: O(2 ^ n * n) - take or don't take, then length n for each since we have to copy
        #Space: O(n) recursion stack or O(2 ^ n * n) for res            

Question 37

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.

Input
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4

Answer 37

class Node:
    def \_\_init\_\_(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
class LRUCache:

    def \_\_init\_\_(self, capacity: int):
        self.cache = {} #maps a key to the actual node
        self.capacity = capacity
        self.left = Node(0, 0)
        self.right = Node(0, 0)
        self.left.next = self.right
        self.right.prev = self.left

    #Remove node from arbitrary position
    def remove(self, node):
        prevNode, nextNode = node.prev, node.next
        prevNode.next = nextNode
        nextNode.prev = prevNode

    #Insert node to the rightmost spot (most recently used)
    def insert(self, node):
        rightPrev = self.right.prev
        rightPrev.next = node
        self.right.prev = node

        node.next = self.right
        node.prev = rightPrev
        

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            #We don't delete it from the map since we're just gonna reinsert it at MRU spot
            self.remove(node)
            #reinsert at MRU spot
            self.insert(node)
            return node.val
        return -1

        

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            self.remove(node)
        #Just create a new node for this updated value (in case it's an update)
        node = Node(key, value)
        self.insert(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

    #Runtime: O(1) avg runtime for operations
    #Space: O(n) space for cache and LL
        

Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Question 38

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.

Input
[“TimeMap”, “set”, “get”, “get”, “set”, “get”, “get”]
[[], [“foo”, “bar”, 1], [“foo”, 1], [“foo”, 3], [“foo”, “bar2”, 4], [“foo”, 4], [“foo”, 5]]
Output
[null, null, “bar”, “bar”, null, “bar2”, “bar2”]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set(“foo”, “bar”, 1); // store the key “foo” and value “bar” along with timestamp = 1.
timeMap.get(“foo”, 1); // return “bar”
timeMap.get(“foo”, 3); // return “bar”, since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is “bar”.
timeMap.set(“foo”, “bar2”, 4); // store the key “foo” and value “bar2” along with timestamp = 4.
timeMap.get(“foo”, 4); // return “bar2”
timeMap.get(“foo”, 5); // return “bar2”

Answer 38

class TimeMap:

    def \_\_init\_\_(self):
        self.map = {} #maps key to list of (timestamp, value) pairs

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.map:
            self.map[key] = []
        self.map[key].append([timestamp, value])
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.map:
            return ""
        res = ""
        timestampAndVals = self.map[key]
        l, r = 0, len(timestampAndVals) - 1
        while l <= r:
            m = l + (r - l) // 2
            if timestampAndVals[m][0] == timestamp:
                return timestampAndVals[m][1]
            elif timestampAndVals[m][0] < timestamp:
                res = timestampAndVals[m][1]
                l = m + 1
            else:
                r = m - 1
        return res
    #Runtime: O(1) for init and set, O(log n) for get
    #Space: O(n) for time map

Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

Question 39

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Answer 39

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        #[..... costs[i - 2], costs[i - 1]]: the costs for these two 
        #final steps is exactly how much it costs to reach the top floor

        for i in range(len(cost) - 3, -1, -1):
            #we'll need to pay cost[i] no matter what. to reach the end,
            #we pay the minimum of i + 1 or i + 2, depending if we climb
            #one or two steps.
            cost[i] += min(cost[i + 1], cost[i + 2])
        return min(cost[0], cost[1])
        #O(n) #Runtime for computing costs in a dp fashion
        #O(1) since modify input cost array

Question 40

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Answer 40

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2:
            return False
        target = sum(nums) / 2
        dp = set()
        dp.add(0)
        #This solution works both forwards and backwards. Let's just do
        #backwards for consistency sake.
        for i in range(len(nums) -1, -1, -1):
            newDP = set()
            for elt in dp:
                if elt + nums[i] == target:
                    return True
                newDP.add(elt)
                newDP.add(elt + nums[i])
            dp = newDP
        return target in dp
        #Runtime: O(N * sum(nums) / 2) #Iterate through each element, and the number of unique values in our dp set is at most sum(nums) / 2.
        #Space: O(sum(nums)) for the dp set
        

Question 41

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Answer 41

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        k = len(nums) - k #this is the k we're looking for
        def quickSelect(l, r):
            #do l, nums[r] not 0, len(nums) - 1
            p, pivot = l, nums[r]
            for i in range(l, r): #r is excluded
                if nums[i] <= pivot:
                    nums[p], nums[i] = nums[i], nums[p]
                    p += 1
            #Remember to swap the pivot element into the p spot!
            nums[p], nums[r] = nums[r], nums[p]

            if p == k:
                return nums[p]
            elif p < k:
                return quickSelect(p + 1, r)
            else:
                return quickSelect(l, p - 1)
        return quickSelect(0, len(nums) - 1)
    #Runtime: O(n) avg runtime because it's n + n/2 + n/4+...., O(n^2) worst case 
    #Space: O(1) just using pointers

Question 42

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Answer 42

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2

        if len(B) < len(A):
            A, B = B, A
        l, r = 0, len(A) - 1
        while True:
            #Index in A that we're doing bin search
            i = l + (r - l) // 2 
            #Index in B that represesents the end of the B's left partition. We subtract 2 since both indices start at 0
            j = half - i - 2

            #Left represents the last elt of left partitions
            #Right represents the first elt of right partitions

            #If i out of bounds, i < 0
            Aleft = A[i] if i >= 0 else float('-inf')
            #If i + 1 is out of bounds, we want everything in A to be in left partition, so default is 'inf'
            Aright = A[i + 1] if i + 1 < len(A) else float('inf')

            #If j + 1 is out of bounds, we want everything in B to be in left partition, so default is 'inf'
            Bleft = B[j] if j >= 0 else float('-inf')
            Bright = B[j + 1] if j + 1 < len(B) else float('inf')

            #Left Partition is Correct
            if Aleft <= Bright and Bleft <= Aright:
                # odd
                if total % 2:
                    #If one is infinity, we'll return correctly with minimum. Only one will ever be infinity.
                    #We don't return Aleft Bleft for obvious reasons... it's part of left partition, not median calculation
                    return min(Aright, Bright)
                #even
                return (max(Aleft, Bleft) + min(Aright, Bright))/2
            elif Aleft > Bright: #too many elements from A
                r = i - 1
            else:
                l = i + 1
        #Runtime: O(log(min(n, m))) #binary search on minimum of the two.
        #Space: O(1) pointers]
        #Note: A[left] is same as A[i]
        #EXAMPLE 1 (odd length, correct partition)
        #B: 123 45678
        #A: 123 45
        #in this case, A[i] is at value 3, and B[j] is also at value 3
        #in this example, 3 <= 4 and 3 <= 4. Therefore partition is correct, and 
        #since this is odd length, we want to return min(4, 4) -> 4 as median

        #Example 2 (INCORRECT partition, even length)
        # B: 1234 5678
        # A: 12 34
        # A[i] is at value 2, B[j] is at value 4.
        #Here we check if 2 <= 5 but 4 NOT less than equal to 3.
        #Since incorrect partition, update left to i + 1
        
        #Example 3: (correct partition, even length)
        # B: 123 45678
        # A: 123 4
        # A[i] is at value 3, B[j] also value 3. 3 <= 4 and 3 <= 4
        # So to compute median, we need to take the (max(Aleft, Bleft) + min(Aright, Bright)) / 2
        # 11223 34 45678
                 

Question 43

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user’s news feed.

Implement the Twitter class:

Twitter() Initializes your twitter object.
void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.</Integer>

Input
[“Twitter”, “postTweet”, “getNewsFeed”, “follow”, “postTweet”, “getNewsFeed”, “unfollow”, “getNewsFeed”]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
Output
[null, null, [5], null, null, [6, 5], null, [5]]

Explanation
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1); // User 1’s news feed should return a list with 1 tweet id -> [5]. return [5]
twitter.follow(1, 2); // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1); // User 1’s news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2); // User 1 unfollows user 2.
twitter.getNewsFeed(1); // User 1’s news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Answer 43

class Twitter:

    def \_\_init\_\_(self):
        self.count = 0
        self.tweetMap = defaultdict(list) #maps userId to list of (count, tweetIds) #most recent is maximum count for maxheap
        self.followMap = defaultdict(set) #maps userId to set of followeeIds
        

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweetMap[userId].append((self.count, tweetId))
        self.count -= 1

    def getNewsFeed(self, userId: int) -> List[int]:
        self.followMap[userId].add(userId)
        maxHeap = []
        res = []
        for followeeId in self.followMap[userId]:
            if followeeId in self.tweetMap: #if there's a tweet
                #Grab the most recent tweet of this user
                index = len(self.tweetMap[followeeId]) - 1
                count, tweetId = self.tweetMap[followeeId][index]
                maxHeap.append((count, tweetId, followeeId, index - 1))
        heapq.heapify(maxHeap)
        while maxHeap and len(res) < 10:
            count, tweetId, followeeId, index = heapq.heappop(maxHeap)
            res.append(tweetId)
            if index >= 0:
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(maxHeap, (count, tweetId, followeeId, index - 1))
        return res
    #Runtime: O(10*log k). O(k) to heapify where k is the number of unique followeeIds with tweets. heap is size k, we push and pop k times. If n >> 10, O(nlogk) pretty good. O(1) every other operation
    #Space: O(V + E) #number of users and relationship edges for followeeIds..


        

    def follow(self, followerId: int, followeeId: int) -> None:
        self.followMap[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.followMap[followerId]:
            self.followMap[followerId].remove(followeeId)

# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

Question 44

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]

Answer 44

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        counts = {} 
        res = []
        curPerm = []
        #1: 2, 2: 1
        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:
                #The loop will handle the "take current element n" and "don't take ANY element n". Since n will advance to the subsequent calls!
                if counts[n] > 0:
                    counts[n] -= 1
                    curPerm.append(n)
                    dfs()

                    #Clean up
                    curPerm.pop()
                    counts[n] += 1
        dfs()
        return res
        #Runtime: O(n * n!) #n! results for permutation, n to copy each
        #Space: O(n) for recursion or O(n * n !) for results

Question 45

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Answer 45

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pairs = [(p, s) for p, s in zip(position, speed)]
        pairs.sort(reverse = True)
        stack = []
        for p, s in pairs: #iterate in reverse sorted order
            timeToDestination = (target - p) / s
            stack.append(timeToDestination)
            #If stack size at least two cars and car on top of stack reaches destination before the car in front of it..
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
                stack.pop() #pop the top of the stack because it's now a car fleet.
        return len(stack)
        #Runtime: O(n log n) + O(n) #for sorting based on pos, then O(n) for iterating
        #Space: O(n) for stack and pairs array.

Question 46

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Answer 46

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        res = 0
        # edges = collections.defaultdict(list)
        edges = {i:[] for i in range(1, n + 1)}
        for u, v, w in times:
            edges[u].append((v, w))
        minHeap = [(0, k)]
        visit = set()
        while minHeap:
            w1, n1 = heapq.heappop(minHeap)
            if n1 in visit:
                continue
            visit.add(n1)
            res = max(res, w1) #this is so we know what's the time needed to reach all nodes. Starts max(0, 0), but later on it'll be max(0, someweight)
            #Maybe not needed. In updated code, res = w1
            for n2, w2 in edges[n1]:
                if n2 not in visit:
                    heapq.heappush(minHeap, (w1 + w2, n2))
        return res if len(visit) == n else -1
        #O(E log V). We add E = V^2 nodes to heap, then pop E times
        #O(E) for adjacency list as well as the minHeap 

Question 47

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Answer 47

Modified djikstra to try minheight along the path (instead of total weight).

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N = len(grid)
        minHeap = [(grid[0][0], 0, 0)] #t, r, c
        visit = set()
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        while minHeap:
            t, r, c = heapq.heappop(minHeap)
            if (r, c) in visit:
                continue
            if r == N - 1 and c == N - 1:
                return t
            visit.add((r, c))
            for dr, dc in directions:
                neiR, neiC = r + dr, c + dc
                if neiR < 0 or neiR == N or neiC < 0 or neiC == N or (neiR, neiC) in visit:
                    continue
                #The height to reach a particular neighbor is max(prevheight along path, current neiHeight.) Example: 0 to 2. We take max(0, grid[neiR][neiC] = 2)
                heapq.heappush(minHeap, (max(t, grid[neiR][neiC]), neiR, neiC))
        #Runtime: O(ElogE) -> O(N^2 log N^2) -> O(N^2 log N)
        #Space: O(E) for minHeap -> O(N^2)
        #Notes: 
#The question is: What is the path from top left to bottom right such that the maximum height along that path is minimized? Since that maximum height along that path determines that t value. Find this t value.
# Modified djikstra to try minheight along the path (instead of total weight). 
#(max of own height and height before it, r, c)

Still use visit set! Despite potentially different weights arriving at same (r, c)

When we get to final coordinate, we only need to consider that coordinate ONCE. This is because we are greedy with Djikstra.

Question 48

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20

Answer 48

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        adj = {i: [] for i in range(len(points))} #maps idx pointA to a list of (weight, idx ptB) pairs
        #Compute the edges
        for i in range(len(points)):
            x1, y1 = points[i]
            for j in range(i + 1, len(points)):
                x2, y2 = points[j]
                dist = abs(x1 - x2) + abs(y1 - y2)
                adj[i].append((dist, j))
                adj[j].append((dist, i)) #remember these edges are undirected.
        #Prim's portion
        minHeap = [(0, 0)] #cost and node
        totalCost = 0
        visit = set()
        # while len(visit) < len(points):
        while len(visit) < len(points):
            curCost, node = heapq.heappop(minHeap)
            if node in visit:
                continue
            visit.add(node)
            totalCost += curCost
            for neiCost, neiNode in adj[node]:
                if neiNode not in visit:
                    heapq.heappush(minHeap, (neiCost, neiNode))
        return totalCost
        #Runtime: O(E) for adj + O(ElogE) -> O(N^2 log N^2) -> O(N^2 log N) for heap operations
        #Space: O(E) -> O(N^2) for heap

Question 49

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Answer 49

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        #Create minHeap of size n, then pop k times
        minHeap = [] #need distance and points probably
        for x, y in points:
            dist = x ** 2 + y ** 2
            minHeap.append((dist, x, y))
        heapq.heapify(minHeap)
        res = []
        for i in range(k):
            dist, x, y = heapq.heappop(minHeap)
            res.append([x, y])
        return res

        #Runtime: O(k log n)
        #Space: O(N) for minHeap

Question 50

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Input: x = 2.00000, n = 10
Output: 1024.00000

Answer 50

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def helper(x, n):
            if x == 0:
                return 0
            if n == 0:
                return 1
            res = helper(x, n // 2)
            res *= res
            return x * res if n % 2 else res

        res = helper(x, abs(n))
        return res if n >= 0 else 1 / res
        #Runtime: O(log n) since it's div and conquer on n
        #Space: O(1)
        

Question 51

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Answer 51

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        dp = {} #maps (r, c) to LIP from (r, c)
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        def dfs(r, c, prev):
            if r < 0 or r == ROWS or c < 0 or c == COLS or matrix[r][c] <= prev:
                return 0
            if (r, c) in dp:
                return dp[(r, c)]
            res = 1
            for dr, dc in directions:
                neiR, neiC = r + dr, c + dc
                res = max(res, 1 + dfs(neiR, neiC, matrix[r][c]))
            # res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
            # res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
            # res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
            # res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
            dp[(r, c)] = res
            return res
        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                res = max(res, dfs(r, c, -1)) #every value is >= 0
        return res   
        #O(mn) either full dfs or O(1) return since cached
        #O(mn) dp store
        
        

Question 52

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols ‘+’ and ‘-‘ before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a ‘+’ before 2 and a ‘-‘ before 1 and concatenate them to build the expression “+2-1”.
Return the number of different expressions that you can build, which evaluates to target

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Answer 52

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {} #(index, total) -> if we start from index i onwards, and have curTotal as total so far, how many ways can we get the target?
        #The dp is two dimensional: i and curTotal.
        def dfs(i, curTotal):
            if i == len(nums):
                return 1 if curTotal == target else 0
            if (i, curTotal) in dp:
                return dp[(i, curTotal)]
            plus = dfs(i + 1, curTotal + nums[i])
            minus = dfs(i + 1, curTotal - nums[i])
            res = plus + minus
            dp[(i, curTotal)] = res
            return res
        return dfs(0, 0)    
        #Runtime: O(n * 2*sum(nums array)) -> O(nS. for the dimensions of dp
        #Space: O(n*2*sum(nums array)) ->O(nS) dp cache

Question 53

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
————— —–
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

Answer 53

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque() 
        #indices. The vals associated with these indices are always monotonically decreasing
        #In addition, the value associated with the leftmost elt of the queue is the sliding window maximum.
        res = []
        l = 0
        for r in range(len(nums)):
            #Pop smaller values from the end of the queue
            while q and nums[r] > nums[q[-1]]:
                q.pop()
            
            #Append the current maximum to the queue
            q.append(r)
            
            #Remove from the front of the queue the index if it's no longer in the current window . This is indicated by if the index corresponding to the maximum on the left is no longer in bounds of l
            if q[0] < l:
                q.popleft()
            
            #Append the sliding window max to output, but only if the window is at least size k. Sliding window max is nums[q[0]] NOT nums[q[l]]
            if r - l + 1 >= k: #double equals also works
                res.append(nums[q[0]])
                l += 1 #need to slide the window over if window at least size k
        return res
        #O(n). Sliding window op is O(n). We push and pop each elt once
        #O(n) queue is O(n) space

Question 54

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Answer 54

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #returns the max profit can earn from the index i onwards, if the buying state is this.
        dp = {} #key: (i, buying) value: max_profit
        #if Buy -> i + 1
        #If sell -> i + 2
        def dfs(i, buying):
            if i >= len(prices):
                return 0 #0 money from the end
            if (i, buying) in dp:
                return dp[(i, buying)]
            #can move the cooldown lines here too.
            if buying:
                buy = -prices[i] + dfs(i + 1, not buying)
                cooldown = dfs(i + 1, buying)
                dp[(i, buying)] = max(buy, cooldown)
            else:
                sell = prices[i] + dfs(i + 2, not buying)
                cooldown = dfs(i + 1, buying)
                dp[(i, buying)] = max(sell, cooldown)
            return dp[(i, buying)]
        return dfs(0, True)
        #Runtime: O(n * 2) -> n prices, 2 states for each
        #Space: O(n * 2) -> the dp array
        

Question 55

Given two strings s and t, return the number of distinct
subsequences
of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

Input: s = “rabbbit”, t = “rabbit”
Output: 3
Explanation:
As shown below, there are 3 ways you can generate “rabbit” from s.
rabbbit
rabbbit
rabbbit

Answer 55

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = {} #Start at index i in s and index j in t, what's the number of distinct subseq of s which equals t?

        def dfs(i, j):
            # s = "a"  and t = "" OR s == "" and t == ""
            if j == len(t):
                return 1
            # s == "" and t == "a" 
            if i == len(s):
                return 0
            if (i, j) in dp:
                return dp[(i, j)]
            if s[i] == t[j]:
                #Perform the match
                #Despite matching up, we skip the match on string s
                dp[(i, j)] = dfs(i + 1, j + 1) + dfs(i + 1, j)
            else:
                dp[(i, j)] = dfs(i + 1, j)
            return dp[(i, j)]
        return dfs(0, 0)
        #Runtime: O(|s|*|t|) recursive calls and cached results returning
        #Space: O(|s|*|t|) cache

            
            

Question 56

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m
substrings
respectively, such that:

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + … or t1 + s1 + t2 + s2 + t3 + s3 + …
Note: a + b is the concatenation of strings a and b.

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = “aa” + “bc” + “c”, and s2 into s2 = “dbbc” + “a”.
Interleaving the two splits, we get “aa” + “dbbc” + “bc” + “a” + “c” = “aadbbcbcac”.
Since s3 can be obtained by interleaving s1 and s2, we return true.

Answer 56

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
        #If dp[i][j] is True, that means that we are able to interleave
        #s1[i:] and s2[j:] and match s3[i + j:]
        dp[len(s1)][len(s2)] = True #if both are empty, then s3 is a valid interleave. Since len(s3) is ALSO zero -> valid interleave
        # Example grid
        # target: aadbbcbcac
        #  dbbca"
        # a------
        # a------
        # b------
        # c------
        # c-----Y
        # "----XT
        #For cell X: can we form the character "c" using a? no, so False at X.
        #In the bottom double for loop, the first IF is i < len(s1) but doesn't 
        #evaluate to match s3[i + j] so still False. Second if doesn't trigger since
        # j == len(s2)
        #For cell Y: Can we form "c" using c? Yes. First if is skipped but second is triggered.
        for i in range(len(s1), -1, -1): #We go from the bottom right corner
            for j in range(len(s2), -1, -1):
                #Take the match from the s[i] AND able to match the rest from from s1 onwards 
                #These i < len(s1) and j < len(s2) checks needed since our double for loop
                #begins at len(s1) len(s2)
                if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
                    dp[i][j] = True
                if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
                    dp[i][j] = True
        print(dp)
        return dp[0][0]
        #Runtime: O(|s1|*|s2|) for the double for loop
        #Space: O(|s1|*|s2|) for the cache

Question 57

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)

Answer 57

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        #  ros"  
        #h
        #o
        #r
        #s
        #e
        #" 
        #last row: length of word2 basically
        #last col: length of word1 basically  
        dp = [[float('inf')] * (len(word2) + 1) for i in range(len(word1) + 1)]

        #Initialize last col
        for i in range(len(word1) + 1):
            dp[i][len(word2)] = len(word1) - i
        
        #Initialize last row
        for j in range(len(word2) + 1):
            dp[len(word1)][j] = len(word2) - j

        #We already computed the last row and columns
        for i in range(len(word1) - 1, -1, -1):
            for j in range(len(word2) -1, -1, -1):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i + 1][j + 1] #it's free!
                else: 
                    #insert
                    #[o]horse
                    #ors
                    #an insert matches something in word2, so advance it by one. i stays the same.
                    insert = 1 + dp[i][j + 1]
                    #delete
                    #hyorse
                    #ors
                    #can't move j yet since we don't know if by deleting from word1, we match yet
                    delete = 1 + dp[i + 1] [j]
                    #Definitely a match, but requires an op
                    replace = 1 + dp[i + 1][j + 1]
                    dp[i][j] = min(insert, delete, replace)
        return dp[0][0]
        #Runtime: O(mn) for init and double for loop etc
        #Space: O(mn) for the dp cache
        
        

        

Question 58

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Input: s = “ababcbacadefegdehijhklij”
Output: [9,7,8]
Explanation:
The partition is “ababcbaca”, “defegde”, “hijhklij”.
This is a partition so that each letter appears in at most one part.
A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits s into less parts.

Answer 58

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        #First, let's note down the end indices of each character
        #We know we can move on to the next partition if all chars in current partition have been taken care of (and no more in future)
        endIndex = {c: i for i, c in enumerate(s)}
        # {'a': 8, 'b': 5, 'c': 7, 'd': 14, 'e': 15, 'f': 11, 'g': 13, 'h': 19, 'i': 22, 'j': 23, 'k': 20, 'l': 21}
        res = []
        size = 0
        end = 0
        for i, c in enumerate(s):
            end = max(endIndex[c], end)
            size += 1
            if i == end: #If we ever reached a point the end index is same as current index, we've captured all the chars successfully.
                res.append(size)
                size = 0
        return res
        #O(n) for endIndex map init and traversal
        #O(26) -> O(1) for endIndex map

Question 59

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Answer 59

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        #  5 4 3 2 1 0
        # 1          1
        # 2          1 #One way to make 0 from 2:
        # 5          1 #One way to make 0 amount from 5: - don't take ANY coins. In coin change i, it's 0 coins to make 0 amount, that's why it's dp[0].

        #when we initialize dp initially, it's actual out of bounds at the bottom row
        #it's [000001]
        #newDP[a]: we take the sum of 1) If we didn't use curCoin, so only use coins after this one, so dp[a]. We sum with 2) If we did take this coin, how many combos? (nextDP). We don't sum 1. It's start part of same combination
        dp = [0] * (amount + 1)
        dp[0] = 1 #1 way to get 0 amount, which is take no coins.
        #Need to do coins outside, then a inside!
        for i in range(len(coins) - 1, -1, -1):
            newDP = [0] * (amount + 1)
            newDP[0] = 1
            for a in range(1, amount + 1):
                newDP[a] = dp[a] # number of ways without coins i
                if a - coins[i] >= 0:
                    newDP[a] += newDP[a - coins[i]] #number of ways WITH coin i
            dp = newDP
        return dp[amount] #returns 0 if impossible
        #Runtime: O(ac) #double for loop for amount * number of coins
        #Space: O(a) each dp array.
                

        

Question 60

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Answer 60

class Solution:
    def isHappy(self, n: int) -> bool:
        slow, fast = n, n
        #Similar to find the duplicate number.
        while True:
            slow = self.sumOfSquares(slow)
            fast = self.sumOfSquares(self.sumOfSquares(fast))
            if slow == fast:
                break
        return slow == fast == 1
        #Runtime: O(n) bounded by the number n for how it will traverse
        #Space: O(1)

    def sumOfSquares(self, n):
        res = 0
        while n:
            digit = n % 10
            res += digit ** 2
            n = n // 10
        return res

Question 61

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Answer 61

# Definition for singly-linked list.
# class ListNode:
#     def \_\_init\_\_(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        carry = 0
        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            val = val1 + val2 + carry

            digit = val % 10
            carry = val // 10
            cur.next = ListNode(digit)
            cur = cur.next

            l1 = l1.next if l1 else None 
            l2 = l2.next if l2 else None 
        return dummy.next
        #Edge cases:
        #1) if one list is shorter, we just have a zero
        #2) If we still have a carry at the very end, we consider it by having it in the while loop. While None or None or carry -> evaluate carry. Example: 7 + 8 = 5 (1 carry)
        #O(max(l1, l2))
        #O(1)

Question 62

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: 5
Explanation: One shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> cog”, which is 5 words long.

Answer 62

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        neighbors = collections.defaultdict(list) #maps patterns to all words that fit that pattern.
        wordList.append(beginWord) #we need to get the pattern from this too, since it's not in the wordList initially! Need to know how this maps around
        for w in wordList:
            for i in range(len(w)):
                pattern = w[:i] + '*' + w[i + 1:]
                neighbors[pattern].append(w)
        q = deque([beginWord])
        visit = set([beginWord])
        count = 1 #own word counts as 1
        while q:
            for _ in range(len(q)):
                curWord = q.popleft()
                if curWord == endWord:
                    return count
                for i in range(len(curWord)):
                    pattern = curWord[:i] + '*' + curWord[i + 1:]
                    for neiWord in neighbors[pattern]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            count += 1
        return 0
        #Runtime: O(m^2 n + n^2 * m) Time to build adjacency list (length m word, m patterns, n words total) + traverse all edges (n^2) for each word of length m
            #go through everyword n * m different patterns per word * m to add to list -> O(nm^2)
            #So OVERALL time complexity is O(n^2 * m) #number of edges, m length each edge.
        #Space: O(n^2 * m) - adjacency list: n^2 edges, length m words.

Question 63

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”]]

Answer 63

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        #   aab
        # a  aa aab
        #a ab b  
        #b  
        #8 nodes -> 2^3
        res = []
        curPart = []
        def dfs(i):
            if i == len(s):
                res.append(curPart.copy())
                return
            #Even tho for loop, this is a per element basis (per partition basis)
            for j in range(i, len(s)):
                if self.isPali(s, i, j):
                    #Include this partition
                    curPart.append(s[i: j + 1])
                    dfs(j + 1)
                    #Clean up the partition
                    curPart.pop()
        dfs(0)
        return res
    def isPali(self, s, i, j):
        l, r = i, j
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True
    #Runtime: O(2^N * N) : 2^N different substring partitions, check is pali in O(n) time
    #Space: O(N) for recursion stack or O(2^N * N) for result

        

Question 64

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Answer 64

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        #We need to prioritize the tasks that have higher counts first
        #How to get the one with max count? Use a max heap
        #Use queue to help track what's the next time we can readd to the heap.
        #we don't care about the task itself, just counts and idle times
#maxheap: -3 (becomes -2) 2 2
#queue  (-2, 2) #the (count, time next available to be ADDED back to the queue. This is at the VERY END.
#At each instance of t
#Take the most frequent heap value, change the counter, then add to queue
#Check if there's any values of front of queue we can add back to the heap
#Add back to heap
#We don't need to care about values!
        counts = {}
        for t in tasks:
            counts[t] = counts.get(t, 0) + 1
        maxHeap = [-count for count in counts.values()]
        heapq.heapify(maxHeap) #heap just contains the counts.
        q = deque() #(count in negative value, time we can ADD back to queue at the end)
        time = 0
        while maxHeap or q:
            time += 1
            if maxHeap:
                curCount = 1 + heapq.heappop(maxHeap)
                if curCount != 0:
                    q.append((curCount, time + n))
            if q and q[0][1] == time:
                heapq.heappush(maxHeap, q.popleft()[0])
        return time
        #Runtime: O(N * n * log 26) -> O(N * n) #idle time * number of tasks * log (26) for heap push pops
        #Space: O(26) -> O(1) for queue and heap ops.

Question 65

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Increment the large integer by one and return the resulting array of digits.

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Answer 65

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits = digits[::-1]
        carry = 1
        i = 0
        while carry:
            if i < len(digits):
                if digits[i] == 9:
                    digits[i] = 0
                else:
                    digits[i] += 1
                    carry = 0
            else: #we're out of bounds and still have a 1 value.
                digits.append(1)
                carry = 0 #reset carry to zero 
            i += 1
        return digits[::-1]
        #Runtime: O(n)
        #Space: O(n) for digits

Question 66

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Answer 66

class Solution:
    def jump(self, nums: List[int]) -> int:
        #l and r indicate the current window of the BFS level that we are currently in.
        l, r = 0, 0
        farthest = 0
        res = 0
        while r < len(nums) - 1: #minus one, because if we reach final position that's it!
            #We try to jump for our current window to the farthest we can get
            for i in range(l, r + 1):
                farthest = max(farthest, i + nums[i])
            l = r + 1
            r = farthest
            res += 1
        return res
        #O(n) #BFS-like linear traversal of all elts
        #O(1) #Just two pointers
        #Idea: [2 3 1 1 4]
        #      [-][--][--] These indicate the levels of our BFS that we can jump
        #          lr
        #       0  1   2 #number of levels
        #We update by setting: l = r + 1, r = farthest
    

Question 67

Given a string s containing only three types of characters: ‘(‘, ‘)’ and ‘*’, return true if s is valid.

The following rules define a valid string:

Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string “”.

Input: s = “(*)”
Output: true

Answer 67

class Solution:
    def checkValidString(self, s: str) -> bool:
        leftMin, leftMax = 0, 0
        for c in s:
            if c == "(":
                leftMin, leftMax = leftMin + 1, leftMax + 1
            elif c == ")":
                leftMin, leftMax = leftMin - 1, leftMax - 1
            else:
                leftMin, leftMax = leftMin - 1, leftMax + 1
            #Example: ): no matter what we try to do, leftMax is < 0
            if leftMax < 0:
                return False
            #Example: ( * ) (
            #When we get to the ), we are currently () ). If we don't 
            #reset, we'll have -1 + 1 = 0 in the end, which returns true even though INCORRECT.
            if leftMin < 0:
                leftMin = 0
        return leftMin == 0
        #O(n) single traversal
        #O(1) variables
        

Question 68

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Answer 68

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = [] #(start idx, height) #heights in stack have to be increasing or equal
        
        for i, h in enumerate(heights):
            start = i #our start is i initially
            #If top of stack is greater than current height, we can't extend the top of the stack anymore, so we HAVE to pop from top of the stack
            while stack and stack[-1][1] > h:
                stackIndex, stackHeight = stack.pop()

                #Compute max area we made so far with the elt we're about to pop
                maxArea = max(maxArea, (i - stackIndex) * stackHeight)
                
                #We can extend our current height back to where that elt was
                #Picture: 5 6 2. Extend 2 back to idx 1, then later back to idx 0 respectively.
                start = stackIndex
            
            stack.append((start, h))
        #Whatever remains can be extended all the way to the end, since monotonically increasing (or equal)
        for start, h in stack:
            #len(heights) instead of len(heights) - 1. Example: idx 4 and 5. We want the width to be 2.
            maxArea = max(maxArea, (len(heights) - start) * h)
        return maxArea

        #Runtime: O(n) run through each elt, push and pop to stack at most once
        #Space: O(n) for stack

Question 69

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Answer 69

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        total = 0
        res = 0
        for i in range(len(gas)):
            total += gas[i] - cost[i]
            if total < 0:
                #reset total back to 0
                total = 0
                #Potentially the next start will then be i + 1
                res = i + 1
        #By this point, total never dipped back below 0 again.
        #Since we established sum(gas) >= sum(cost) we have enough
        #gas to go all the way around, so done!
        return res
        #O(n) just iterate array once
        #O(1) no extra memory.

Question 70

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Answer 70

2 prices arrays:

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        prices = [float('inf')] * n
        prices[src] = 0
        for i in range(k + 1): #relax k + 1 times
            tmpPrices = prices.copy()
            for u, v, p in flights:
                if prices[u] == float('inf'): #can't get to u yet
                    continue
                #Basically.... for an edge u v, we  say that Tmpcost[v] = original cost to u so far + weight of uv.
                #we compare this to cost[v] that is in TMP. Because we might update tmp multiple times.
                if prices[u] + p < tmpPrices[v]:
                    tmpPrices[v] = prices[u] + p
            prices = tmpPrices
        return prices[dst] if prices[dst] != float('inf') else -1
        #Runtime: O((k + 1) * E) - > O(kE). Basically the number of iterations of BF, each iteration we relax the edge
        #Space: O(V) for the cities array for prices
# - original prices: before we did our edge relaxations/BFS
# - temp is after we did the iteration of edge relaxations/BFS
# Why temp array needed?
# - it'll bypass our k + 1 steps of relaxation and instead do it all in one step of relaxation!
# - Example: A -> B costs 100. Then B -> C it'll see costs 100 + 100 = 200, but all done in one step.. :(

Question 71

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Input: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
Output: [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]

Answer 71

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        tickets.sort() #We want lex. order so append to adj in that way
        adj = {u: collections.deque() for u, v in tickets} 

        for u, v in tickets:
            adj[u].append(v)

        res = ["JFK"]
        def dfs(src):
            if len(res) == len(tickets) + 1:
                return True
            #If no outgoing edges, that means we're stuck. 
            if src not in adj:
                return False
            #Can't iterate and modify from the same list...
            temp = adj[src].copy() 
            for nei in temp:
                adj[src].popleft()
                res.append(nei)
                if dfs(nei): return True

                #backtrack
                res.pop()
                #OK to just add at the end. Since we're only iterating over temp, which is properly in the sorted order - we won't reconsider this popped and pushed nei again.
                adj[src].append(nei)
            return False
        dfs("JFK") 
        return res
# Runtime: O(E^D)
# DFS is O(V + E), potentially backtrack D times for the maximum number of outgoing destinations
# - O(V + E)^D. V is approximately E is O(E^D)
# - Another way to see it: making combinations of |V1V2V3V4...Ve|. D choices for each for destinations -> E^D

Space: O(E) for adjacency list as well as recursion stack -> O(E) 
        
"""
We want to have adjacency list destinations be in sorted order, so that we can get lexiographically smaller elts first

To do this, we sort the input list. First by src then by dest. that is much easier than sorting each adjacency list value

When traversing an edge, we'll remove destination city temporarily from adj list
And add to result while doing this

How know visit all edges?
- Done when len(result) = len(tickets) + 1 <- 1 for JFK.

Runtime: O(E^D)
DFS is O(V + E), potentially backtrack D times for the maximum number of outgoing destinations
- O(V + E)^D. V is approximately D is O(E^D)
- Another way to see it: making combinations of |V1V2V3V4...Ve|. D choices for each for destinations -> E^D

Space: O(E) for adjacency list as well as recursion stack -> O(E) 
"""

Question 72

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Input: num1 = “2”, num2 = “3”
Output: “6”

Answer 72

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if "0" in [num1, num2]:
            return "0"
        res = [0] * (len(num1) + len(num2))
        num1, num2 = num1[::-1], num2[::-1]

        for i1 in range(len(num1)):
            for i2 in range(len(num2)):
                val = int(num1[i1]) * int(num2[i2])
                #Just add val directly to res at spot [i1 + i2] for now, even if val is 
                #2 digit or result sum is 2 digit
                res[i1 + i2] += val

                #Add any potential carries that arose to the next spot over.
                res[i1 + i2 + 1] += res[i1 + i2] // 10 #Add, not equal.

                #Correct the ones spot at [i1 + i2].
                res[i1 + i2] = res[i1 + i2] % 10
        
        res = res[::-1]
        #Remove any leading zeroes
        begin = 0
        while begin < len(res) and res[begin] == 0:
            begin += 1
        res = map(str, res[begin:])
        return "".join(res)

        #Runtime: O(n * m) for the multiplaying
        #Space: O(n + m) allocated array n + m, where n and m are number of digits in each.
"""
Where we put the next digit: consider sum of indices, that's where we'll put it.
We'll put the number directly at the digit.
max number of digits in result is n + m (n digits in first, m in second)

Iterate and build result in reverse order.

prebuild as array

O(n*m)
O(n + m)

8 + 2...= 10
- also see if res[i1 + i2] leads to modding and carry.

val. compute the value
add any potential carries that arise
just take the ones place after that.
"""

Question 73

You are given a stream of points on the X-Y plane. Design an algorithm that:

Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points.
Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the query point form an axis-aligned square with positive area.
An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis.

Implement the DetectSquares class:

DetectSquares() Initializes the object with an empty data structure.
void add(int[] point) Adds a new point point = [x, y] to the data structure.
int count(int[] point) Counts the number of ways to form axis-aligned squares with point point = [x, y] as described above.

Input
[“DetectSquares”, “add”, “add”, “add”, “count”, “count”, “add”, “count”]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
Output
[null, null, null, null, 1, 0, null, 2]

Answer 73

class DetectSquares:

    def \_\_init\_\_(self):
        self.ptCounts = defaultdict(int)
        

    def add(self, point: List[int]) -> None:
        self.ptCounts[tuple(point)] += 1

    def count(self, point: List[int]) -> int:
        res = 0
        px, py = point        
        #Consider all other points in the ptCounts map as possible diagonals
        #We capture a snapshot of self.ptCounts via a list. Otherwise, default dict will create entries for points that don't exist and be 0.
        for x, y in list(self.ptCounts):
            if abs(x - px) != abs(y - py) or x == px or y == py:
                continue
            #we multiply by (x, y) so that duplicate diagonal points are considered too.
            res += self.ptCounts[(x, py)] * self.ptCounts[(px, y)] * self.ptCounts[(x, y)]
        return res
    #Runtime: O(n) for initialization, and only consider O(n) diagonals. Checking for existence of the two other points of square is O(1) op
    #Space: O(n) for the points map
            

Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)

Question 74

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).

Answer 74

Identical to Find All Anagrams in a String basically.
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        #s1 is the smaller one
        s1Count = {}
        s2Count = {}
        #Start both of the windows the size of p1
        for i in range(len(s1)):
            s1Count[s1[i]] = s1Count.get(s1[i], 0) + 1
            s2Count[s2[i]] = s2Count.get(s2[i], 0) + 1
        #res = [0] if pCount == sCount else [] instead of this from the find all anagrams in string
        if s1Count == s2Count:
            return True
        #Otherwise, we need to do the sliding window
        l, r = 0, len(s1) #r is at an element that is not in our window yet
        while r < len(s2):
            #Slide one elt to the right
            s2Count[s2[r]] = s2Count.get(s2[r], 0) + 1
            #Subtract elt on the left
            s2Count[s2[l]] -= 1 
            
            #Have to delete. Otherwise even if equal, there's a lot of dead entries saying s1Count is not equal to s2Count
            if s2Count[s2[l]] == 0:
                del s2Count[s2[l]]
            
            if s1Count == s2Count:
                return True
            l += 1
            r += 1
        return False
        #O(26 * |s2|) -> O(|s2|) #the p is included in the 26 for the p
        #O(26) -> O(1)
        
        
        

Question 75

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

’.’ Matches any single character.​​​​
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Input: s = “aa”, p = “a”
Output: true
Explanation: ‘’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Answer 75

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = {} #maps (i, j) to whether it's a match.

        def dfs(i, j):
            #greater than or equal to since we increment by more than one potentially
            if i >= len(s) and j >= len(p): #reached the end of both
                return True
            #In this case, we ran out of characters in the pattern string p to try to match s with, but s is non-empty still :(
                    #Example: "aa", "a"
                    #           i      j
                    #Does not match
            #Explaining the other case. It might be ok with if s is non-empty and p is empty (e.g. "ab" "")
                    #Example: "a" "a*b*"
                                #i   j
                    #Because we can potentially negate the rest of p.
            #so j out of bounds. Definitely not a match
            #only i out of bounds. Maybe not a match, we're not sure yet at this point
            if j >= len(p):
                return False

            if (i, j) in dp:
                return dp[(i, j)]
            #We need the i < len(s) because if i is out of bounds, don't trip up an index out of bounds error.
            match = i < len(s) and (s[i] == p[j] or p[j] == ".")

            #If it's a star
            if j + 1 < len(p) and p[j + 1] == "*":
                #1) Can take the star only if it's a match!. Or 
                #2) Or if we don't take the star at all, then we skip it
                dp[(i, j)] = (match and dfs(i + 1, j)) or dfs(i, j + 2)
                return dp[(i, j)] #Have to return immediately, otherwise the dp[(i, j)] = False will cause issues.
            #If it's just a normal match (either a dot or a normal character match)
            elif match:         
                dp[(i, j)] = dfs(i + 1, j + 1)
                return dp[(i, j)] #Have to return immediately, otherwise the dp[(i, j)] = False will cause issues.

            #Otherwise it's not a match so HAVE to return to False
            dp[(i, j)]= False
            return dp[(i, j)]
        return dfs(0, 0)   
        #Runtime: O(sp) #two pointers for s and p, and if seen before just immediate return.
        #Space: O(sp) #size of our dp cache
        

Question 76

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 315 + 358 + 138 + 181 = 167

Answer 76

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        #pad with 1s in case we go out of bounds of array
        nums = [1] + nums + [1]
        dp = {} #maps the range (l, r) to the max coins we can get from popping balloons in that range.
        def dfs(l, r):
            if (l, r) in dp:
                return dp[(l, r)]
            if l > r:
                return 0
            dp[(l, r)] = 0
            #i is the balloon index that we pop LAST.
            for i in range(l, r + 1):
                #Because we pop balloon i LAST, balloons l to i - 1 and balloons i + 1 to r have ALREADY been popped. Therefore, the two balloons next to index i are actually balloon l - 1 and balloon r + 1, so compute the product
                curCoins = nums[i] * nums[l - 1] * nums[r + 1]
                #Because we have earned some amount of coins from popping those other balloons before i, calculate that as dfs(l, i - 1) + dfs(i + 1, r)
                curCoins += dfs(l, i - 1) + dfs(i + 1, r)
                dp[(l, r)] = max(dp[(l, r)], curCoins)
            return dp[(l, r)]
        return dfs(1, len(nums) - 2) #because the other indices are just padding
        #Runtime: O(n^2 * n) -> O(n^2) l, r pairs, O(n) to check each range
        #Space: O(n^2) for dp cache
        

Question 77

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Answer 77

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()
        res = {} #maps a query time to its minimum query size. We'll use this to list things back in sorted order.

        minHeap = [] #(intervalSize, intervalEndTime) #interval right
        i = 0
        for q in sorted(queries):
            #Add all possible intervals that can potentially fulfill this query
            while i < len(intervals) and intervals[i][0] <= q:
                l, r = intervals[i]
                heapq.heappush(minHeap, (r - l + 1, r))
                i += 1
            
            #Pop all intervals that are invalid. A right that is less than query
            while minHeap and minHeap[0][1] < q:
                heapq.heappop(minHeap)
            res[q] = minHeap[0][0] if minHeap else -1
        return [res[q] for q in queries]
        #Runtime: O(n log n + q log q + n log n) - sort intervals, then sort queries, and minHeap operations -> O(n log n)
        #Space: O(n + q) #O(n) for minHeap and queries in res
            

            
# Brute force: O(nq)
# Solution: O(n log n + q log q)
# - sort intervals, sort queries
# - After double sort, each query is close to the interval it belongs to.
# - minHeap for intervals.

for every query
# - iterate through each interval based on start time..
# 1) sort intervals, run through queries in sorted order. For queries, we'll need book-keeping to remap to original indices via hashmap.
# 2) Add all possible intervals that this query can belong to to the min heap. Start time of interval <= query time. 
#    - to the minHeap, we'll add (intervalSize, intervalEndTime) <- the right value of the interval is intervalEndTime
#    - reasoning: if mult intervals the same size, we want to pop the interval that's earlier. Since later intervals can be potentially used.
# 3) Before taking the interval with smallest size, pop all invalid intervals from our minHeap. Anything with a right value that is less than our query time. while r < query.
# 4) We'll take the interval with the smallest size, and append to result.
# 5) Continue on to next query, then repeat steps 2 - 5 until done

Question 78

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Input: x = -123
Output: -321

Answer 78

class Solution:
    def reverse(self, x: int) -> int:
        MIN = -2 ** 31
        MAX = 2**31 - 1
        res = 0
        while x:
            #Get the rightmost digit of x
            digit = int(math.fmod(x, 10)) #Need this because Python -1 % 10 = 9, not -1
            #Chop off the rightmost digit of x
            x = int(x / 10) #Need this because Python -1 // 10 = -1, not 0.

            #If everything up to last digit is greater than that of MAX, or if 
            #equal to that of max BUT the last digit is greater than last digit of max, overflow
            if (res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10)):
                return 0
            #If everything up to last digit is less than that of MIN, or if 
            #equal to that of min BUT the last digit is less than last digit of min, underflow
            if (res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10)):
                return 0
            #Do the reversing
            res = res * 10 + digit
        return res
        #O(n) - number of digits in x
        #O(1) - O(1) space, or O(n) if you count number of digits.
            
    

”””
reverse everything except the last digit.

Potential out of bounds candidates:
1) Comparing the last digit to the last digit of 2^31- 1
- we compare reverse’s everything up to but not including last digit, with 2 ^31 -1’s up to but not including last digit.
- then we compare final digit of each.

2) If everything up to but not including is larger than that of 2^31-1’s up to last digit, then also overflow -> return 0
“””

Question 79

math.fmod(-1, 10) = ?
int(math.fmod(-1, 10)) = ?
-1/10 = ?
int(-1 / 10) = ?
-1 % 10 = ?
-1 // 10 = ?

Answer 79

```
math.fmod(-1, 10) = -1.0
int(math.fmod(-1, 10)) = 0 #Think: format mod. -1 rounds to 0
-1/10 = -0.1
int(-1 / 10) = 0 #Rounds to -0.1 to zero
-1 % 10 = 9, not 0
-1 // 10 = -1. not 0
~~~