We can generate all rotations of the string by concatenating the two strings together and checking if the substring is present.

class Solution:
def rotateString(self, s: str, goal: str) -> bool:
all_rotations = s \* 2
return len(s) == len(goal) and goal in all_rotations

The important realization here is that each number's complement (target - number) is unique. Using this information, we can leverage the dictionary's uniqueness key property to store the complement and the index as a key value pair.

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:

      mapping = {}
      for idx, num in enumerate(nums):

          # We found the complement.
          if num in mapping:
              return [idx, mapping[num]]

          # Store the complement and its index.
          mapping[target - num] = idx

The most difficult part of this is ensuring that we sell after buying the sock (i.e, the peak must be after the trough). To do this, let's consider every potential day as a selling day and keep track of the minimum. This way, we guarantee that we've passed the minimum before we sell.

class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0

      # Initialize minimum to Infinity.
      minimum = math.inf

      for price in prices:
          minimum = min(price, minimum)
          max_profit = max(max_profit, price - minimum)
      return max_profit

We can keep track of the rows and columns to set to 0 by using a set. There is another solution which has constant space complexity, but for our exam purposes the below solution will be fine. Submissions will not be graded on efficiency for this exam.

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        rows = set()
        cols = set()

        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)

        def set_row(row, matrix):
            for j in range(len(matrix[row])):
                matrix[row][j] = 0

        def set_col(col, matrix):
            for i in range(len(matrix)):
                matrix[i][col] = 0

        for row in rows:
            set_row(row, matrix)

        for col in cols:
            set_col(col, matrix)

A palindrome is symmetrical. Knowing this, we can consider every potential starting midpoint for the palindrome and expand outwards to count the number of valid palindromes. We'll also need to handle an edge case for even-lengthed palindromes.

class Solution:
    def countSubstrings(self, s: str) -> int:

        size = len(s)

        def expand_outwards(s, left, right):

            count = 0

            # Expand outwards while left and right pointers are the same character.
            while (left >= 0 and right < len(s) and s[left] == s[right]):
                left -= 1
                right += 1
                count += 1

            return count

        total = 0
        for center in range(size):

            # For odd-lengthed palindromes.
            total += expand_outwards(s, center, center)

            # For even-lengthed palindromes.
            total += expand_outwards(s, center - 1, center)
        return total

There are many possible solutions to this problem. A brute force approach is completely acceptable. The below approach is a more optimized/clean solution. The main idea is to keep track of all 8 possible win conditions for each player (3 rows + 3 columns + 2 diagonals). The win conditions are kept track of using a counter. Whenever a counter reaches 3, that player has won.

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:

        # Keep track of all 8 possible win conditions for each
        # player.
        winner_a = [0] * 8
        winner_b = [0] * 8

        # Iterate through the moves.
        for idx, pair in enumerate(moves):

            # Determine who the current player is.
            arr = winner_a if idx % 2 == 0 else winner_b
            x, y = pair

            # Increment row 'win' counter.
            arr[x] += 1

            # Increment col 'win' counter.
            arr[y + 3] += 1

            # Increment diagonal 'win' counter.
            if x == y:
                arr[6] += 1

            # Increment anti-diagonal 'win' counter.
            if x == 2 - y:
                arr[7] += 1

        # Check all win conditions.
        for i in range(8):
            if winner_a[i] == 3:
                return "A"
            if winner_b[i] == 3:
                return "B"

        return "Draw" if len(moves) == 9 else "Pending"

Consider each stack of cubes as a standalone stack, and then subtract the sides that are covered by the surrounding stacks.

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:

        # Function for checking if in bounds.
        in_bounds = lambda r, c: 0 <= r < len(grid) and 0 <= c < len(grid[0])

        total = 0

        # Directions for left, up, right, and down.
        dirs = [
            (1, 0),
            (0, 1),
            (-1, 0),
            (0, -1)
        ]

        total = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):

                # Ignore if there is a hole here.
                if grid[i][j] == 0:
                    continue

                # 2 for the top-down faces, 4 for the lateral sides.
                sa = 2 + 4 * grid[i][j]

                for delta_x, delta_y in dirs:
                    r = i + delta_x
                    c = j + delta_y

                    if not in_bounds(r, c):
                        continue

                    # Subtract neighboring faces.
                    sa -= min(grid[r][c], grid[i][j])
                total += sa

        return total

Let's start at the simplest cases and see if we can find a pattern:

• n = 1, first player wins
• n = 2, first player wins
• n = 3, first player wins

For n = 4, let's consider all the cases:

• picks 1 => n = 3, second player wins by taking 3
• picks 2 => n = 2, second player wins by taking 2
• picks 3 => n = 1, second player wins by taking 1

We can see that for each move, we have a new problem with a different number of n and the player's positions swapping.

We might initially come up with a dynamic programming solution like this:

class Solution:
  def canWinNim(self, n: int) -> bool:
      # if n = 1, 2, 3, we can win immediately.
      if n < 4:
          return True

      # Invariant: if dp[i] is True, a player can win with i stones no matter what.
      # initialize from 0 to n, ignore the first 0.
      dp = [None for i in range(n + 1)]

      # base cases:
      for i in range(1, 4):
          dp[i] = True
      dp[4] = False

      # Consider all cases from 4 to n.
      for i in range(5, n + 1):
          # Loop back to consider cases for taking 1 - 3 stones
          for j in range(1, 4):
              # If we take j stones, the other player will have i - j stones.
              if not dp[i - j]:
                  # If there exists a j such that other player cannot winn, then this
                  # player can win.
                  dp[i] = True
                  break
          else:
              # for loop terminated without breaking, meaning it did not find a
              # possible win condition. It is impossible to win with i stones left.
              dp[i] = False

      return dp[n]

Can we do better? If you manually evaluted more points for n (or examined the contents of the dynamic programming array), you'll find something interesting. Every 4th element is false (meaning it's impossible for the first player to win).

We can shorten this to a simple check:

class Solution:
  def canWinNim(self, n: int) -> bool:
      return n % 4 != 0

Follow up: can you prove this using induction?

The problem specifications hints towards a binary search. However, since this a matrix, we must modify our approach. We can think of the matrix as a large array with the rows stacked on top of each other. Knowing this, we can set our low and high to the appropriate bounds: 0 and rows * columns - 1, respectively. To get the row, we can use mid // columns. To get the column we can use mid % columns.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        low = 0
        high = rows * cols - 1
        while low <= high:
            mid = low + (high - low) // 2
            row = mid // cols
            col = mid % cols
            val = matrix[row][col]
            if val == target:
                return True
            if val < target:
                low = mid + 1
            else:
                high = mid - 1
        return False

In a singly linked list, only the forward connections are stored in the node. To get the backwards connections (or the previous node), we can use recursion. The back/previous connections are stored implicitly on the stack.

In the solution below, the helper function returns two values every time it's called: the new next node for the previous node and the previous node's n-th position from the end.

On every function call, we update the current node's next. The current node's next is unchanged if the next node should not have been deleted.

The time complexity is O(n) because we do one full traversal of the linked list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
  def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

      def helper(node, place_to_remove):

          # reached the end, let the previous node
          # know that it's first
          if not node:
              return None, 1

          node_next, place = helper(node.next, place_to_remove)

          # update connection if necessary
          node.next = node_next

          # delete this node by returning this node's next to be updated
          updated_node = node.next if place == place_to_remove else node

          return updated_node, place + 1

      return helper(head, n)[0]

Again, with problems like this it is good to write out some manual cases and manually identify if they are valid (while doing this look for ways to formalize the patterns you observe into code):

• ((())) => OK
• ((((() => WRONG
• {(}) => WRONG
• (())()) => WRONG
• )() => WRONG

Some observations:

• Closing brackets must match with the opening brackets.
• Closing bracket pairs with the closest open bracket to its left.
• Each closing bracket must have an opening bracket to pair with.

Knowing this, we want to use a stack because we are concerned with the ordering of the open parantheses -- more specifically, the most recent open parantheses we've found before.

In our algorithm, whenever we come across an open parantheses, we add it to our stack of unclosed parantheses. Whenever we come across a closing parantheses, we want to check if the most recent open parantheses that we added matches it, if it does pop the open paranthese from the stack (it's no longer unclosed).

The string is valid if our stack is empty at the end. This means we've cloesd all of our unopened parantheses.

class Solution:
    def isValid(self, s: str) -> bool:


        stack = []
        close_to_open = { ')' : '(', ']' : '[', '}' : '{'}

        for char in s:
            # Must be an opening bracket
            if char not in close_to_open:
                stack.append(char)

            # Closing bracket
            else:
                # No opening bracket to match.
                if not stack:
                    return False

                # Opening bracket exists but doesn't match
                if close_to_open[char] != stack.pop():
                    return False

        return not stack

Create a mapping of the digits to all the possible letters. Iterate through all of them to consider all possibilities. Add to the auxiliary data structure, make the recursive call, then backtrack by popping.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        saved = {
            '1': [],
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']
        }

        # edge case
        if not digits:
            return []

        def helper(result, digits, index, acc):
            if index == len(digits):
                result.append(''.join(acc))
                return

            combos = saved[digits[index]]
            for combo in combos:
                acc.append(combo)
                helper(result, digits, index + 1, acc)
                acc.pop()

        builder = []
        helper(builder, digits, 0, [])
        return builder

At every index, we have two choices: Rob this house or don't. If we rob this house, we have a smaller subproblem that excludes the nearby houses. If we don't, we have a smaller subproblem that excludes the current house. At first, a brute force approach might seem appropriate, but let's see if we can optimize this even further with memoization.

Let's define DP[i] as the maxmimum money we can rob by considering all houses from indices 0 to i. Our recurrence can be something like: DP[i + 1] = max(DP[i], DP[i - 1] + money[i]). At index i + 1, we can either pick this house and add the optimal subproblem of i - 1 or we can exclude this house and pick the optimal subproblem of i.

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        dp = [0] * len(nums)

        # base cases
        dp[0] = nums[0]
        dp[1] = max(dp[0], nums[1])

        for i in range(2, len(nums)):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])

        # last index considers all the homes
        return dp[-1]

An important observation is that the path from the root to any node in the tree is unique (due to the fact that every node has exactly one parent). We can traverse the tree using DFS and build our path accordingly. We don't actually need to store the entire path since we are only concerned about the maximum along the path.

A possible recursive solution:

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def helper(node, maxi):
            """
                Returns the number of good nodes for the subtree at `node`.

                `node`: root of the subtree to evaluate
                `maxi`: the maximum value from the root to the parent of `node`
                        (inclusive).
            """
            # null node, return 0 for no good nodes.
            if not node:
                return 0

            count = 0

            # check if this node is good.
            maxi = max(maxi, node.val)
            if maxi == node.val:
                count += 1
            
            # add contributions from left and right.
            count += helper(node.left, maxi)
            count += helper(node.right, maxi)
            
            return count
        return helper(root, -math.inf)

A possible iterative solution (same algorithm):

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        
        count = 0
        stack = []
        
        stack.append((root, -math.inf))
        
        while stack:
            cur, maxi = stack.pop()
            
            if not cur:
                continue
            
            maxi = max(maxi, cur.val)
            if maxi == cur.val:
                count += 1
            
            stack.append((cur.left, maxi))
            stack.append((cur.right, maxi))
        
        return count

The problem is essentially asking if the graph is connected. Using DFS or BFS from the starting room (room 0), we can visit all the rooms reachable. Once we've completed our graph traversal, we can check if we've reached every room by comparing the length of the visited set to the number of rooms.

The deque class used here is a double-ended queue. We use this class for faster append and pop operations. popLeft() is equivalent to pop(0) in that they both pop the first element from the queue, however, pop(0) executes in N² runtime complexity due to the shifting of elements whereas popLeft() happens in constant time.

from collections import deque

class Solution:
  def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
      
      # use queue for breadth first search.
      queue = deque()
      queue.append(0)

      # keep track of visited rooms.
      visited = set()
      while queue:
          cur = queue.popleft()

          # already visited, ignore.
          if cur in visited:
              continue
          visited.add(cur)
          
          room = rooms[cur]

          # add rooms reachable from here.
          for key in room:
              queue.append(key)
      
      return len(visited) == len(rooms)

The brute force solution solves this in quadratic time (consider every single possible contiguous subarray). We can speed this up using dynamic programming/memoization: rather than recomputing the sums every time, we can store it on every iteration. Additionally, the problem is only asking for the maximum sum, so we don't need to store every sum for every possible pair of start/end indices.

Let's define DP[i] as the maximum subarray sum ending at index i (inclusive). When we consider the i + 1th index, we have two options:

1. Include the previous maximum sum (we can guarantee it is contiguous because it ends on the index before).
2. Don't include the previous maxmium sum, only include the current number.

Now we can find the maximum subarray sum in linear time.

A potential solution:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        dp = [0] * len(nums)
        
        best = -math.inf
        for i, num in enumerate(nums):
            if i == 0:
                dp[i] = num
            else:
                dp[i] = max(nums[i], dp[i - 1] + nums[i])
            best = max(dp[i], best)
        return best

This algorithm is known as Kadane's algorithm.

Follow-up: can you optimize this to be O(1) in space?

At a single node we have two options:

1. Rob the node, don't rob the children of the node.
2. Don't rob the node, consider robbing the children of the node.

For each node, we memoize the best/maxmium profit gained from each of the two conditions (with and without) and then utilize the recursive substructure of the tree to propogate the values up to the root.

The trickiest part is in the second case where we don't rob the code -- we need to consider all four combinations between the maximums including the left and the right and the maximums not including the left and the right. It is not always optimal to rob the children of the node in the second case.

See comments in the code for more information.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        
        def helper(node):
            if node is None:
                return 0, 0
            
            with_l, without_l = helper(node.left)
            with_r, without_r = helper(node.right)
            
            # if we rob this house, we have to pick the ones without.
            with_node = node.val + without_l + without_r
            
            # all possible combinations of with_l, without_l and with_r, without_r
            # these are all possible if we don't rob the current node.
            possibles = [x + y for x in [with_l, without_l] for y in [with_r, without_r]]
            
            return with_node, max(possibles)
        
        
        return max(helper(root))

We can model this problem like a graph. The nodes are the squares of the board. An edge exists between two nodes if a knight can jump from one node to another. We can use either DFS or BFS to determine if the target square is reachable. However, the problem stipulates that we need to find the minimum number of moves.

In order to find the minimum, we must use BFS. Remember that from a starting vertex, BFS finds the shortest unweighted path to every other connected vertex. To return the number of moves required, we can store the distance as part of the BFS state along with the node.

from collections import deque

# single integer
inp = lambda: int(input())

# string list
strl = lambda: list(input().strip())

# in bounds check for 2d array
in_bounds = lambda x, y, grid: x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])


def valid(coord, board):
    """ Checks if coordinate is valid. """
    return in_bounds(*coord, board) and board[coord[0]][coord[1]] != '#'

def solve(board):
    start = None

    # finding the start.
    for i, row in enumerate(board):
        for j, elem in enumerate(row):
            if elem == 'K':
                start = (i, j)

    
    assert start is not None

    queue = deque([(start, 0)])
    visited = set()

    # all different knight movements.
    movement = [
        (2, 1),
        (2, -1),
        (-2, 1),
        (-2, -1),
        (1, 2),
        (1, -2),
        (-1, 2),
        (-1, -2)
    ]

    # perform bfs.
    while queue:
        cur, dist = queue.popleft()

        # reached the target, return `dist` immediately.
        if cur[0] == 0 and cur[1] == 0:
            return dist

        # already visited or not a valid square.
        if cur in visited or not valid(cur, board):
            continue

        visited.add(cur)

        # add next possible moves.
        for move in movement:
            delta = (
                (cur[0] + move[0], cur[1] + move[1]),
                dist + 1
            )
            
            queue.append(delta)
    
    return -1

if __name__ == '__main__':
    
    n = inp()
    board = []
    
    for _ in range(n):
        board.append(strl())
    
    print(solve(board))

The first important observation is that the encoded numbers are at most two digits. That means for a given index i, we need to consider the single digit number (character at i) as well as the double digit number (substring i - 1 to i).

Once we've fixed a single number, we need to consider the number of ways to decode for the remaining substring. A possible recursive/brute force solution might add the following two numbers together for string s.

1. Fixed single digit number at i: decode_ways(s[:i])
2. Fixed double digit number [i-1:i+1]: decode_ways([s:i-1])

Notice that we are always recomputing the decode ways for the beginning of the string, we can use bottom-up memoization to speed up our algorithm.

class Solution:
    def numDecodings(self, s: str) -> int:
        
        # all valid encodings.
        valid_numbers = set([str(i) for i in range(1, 27)])
        
        # dp[i] stores number of ways to decode for substring up to index i
        dp = [0] * (len(s) + 1)
        
        # base cases
        dp[0] = 1        
        dp[1] = 1 if s[0] in valid_numbers else 0

        if len(s) == 1:
            return dp[1]
        
        for i in range(2, len(s) + 1):
            
            # separate index for string since i is exclusive
            str_idx = i - 1
            
            # consider the case where we fix a single digit number
            dp[i] += dp[i - 1] if s[str_idx] in valid_numbers else 0

            # consider the case where we fix a double digit number
            dp[i] += dp[i - 2] if s[str_idx-1:str_idx+1] in valid_numbers else 0
        
        return dp[len(s)]

An important binary search tree property is that the entire subtree of the right must be greater than the root node and the entire subtree of the left must be less than the root node. It's not enough to check the children in order to validate the BST.

When inserting a node into the BST, there is only one place where the node can be placed (according to our BST algorithm). Intuitively, each node acts as a range check for the node being inserted. We can use this same principle in order to validate the BST.

# 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 isValidBST(self, root: TreeNode) -> bool:
        return self.helper(root, -math.inf, math.inf)

    def helper(self, node: TreeNode, min_b: int, max_b: int) -> bool:
        if node is None:
            return True

        # falls within proper range
        ok = node.val >= min_b and node.val <= max_b
        
        # check left and right, left max is node.val - 1, right min is node.val + 1
        return ok and self.helper(node.left, min_b, node.val - 1) and self.helper(node.right, node.val + 1, max_b)