Templates for Data Structures and Algorithms

Exercise symbol legend

Symbol	Designation
✓	This is a problem from LeetCode's interview crash course.
✠	This is a problem stemming from work done through Interviewing IO.
★	A right-aligned ★ (one or more) indicates my own personal designation as to the problem's relevance, importance, priority in review, etc.

Backtracking

Remarks

TBD

def fn(curr, OTHER_ARGUMENTS...):
    if (BASE_CASE):
        # modify the answer
        return
    
    ans = 0
    for (ITERATE_OVER_INPUT):
        # modify the current state
        ans += fn(curr, OTHER_ARGUMENTS...)
        # undo the modification of the current state
    
    return ans

Examples

LC 46. Permutations (✓) ★★

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(curr):
            if len(curr) == len(nums):
                permutations.append(curr[:]) # note that we append a _copy_ of curr
                return
            
            for num in nums:
                if num not in curr:
                    curr.append(num)
                    backtrack(curr)
                    curr.pop()
            
        permutations = []
        backtrack([])
        
        return permutations

What actually is a permutation of nums? It's essentially all possible orderings of the elements of nums such that no element is duplicated. A backtracking strategy to generate all permutations sounds promising — what would the base case be? It would be when the current permutation being generated, say curr, has the same length as the input array nums: curr.length == nums.length (of course, this assumes we've done our due diligence and have prevented duplicates from being added to curr). The base case of curr.length == nums.length means we have completed the process of generating a permutation and we cannot go any further; specifically, if we look at the process of generating permutations as a tree, then completing the generation of a permutation means we have reached a leaf node, as illustrated in the following image for the input nums = [1, 2, 3]:

Building all permutations for this problem, where the input is an array of numbers, means we need all elements to make an appearance at the first index, all other elements to make an appearance at the second index, and so on. Hence, we should loop over all elements of nums for each call to our backtrack function, where we should always check to see if a number is already in curr before adding it to curr. Each call to backtrack is like visiting a node in the tree of candidates being generated. The leaves are the base cases/answers to the problem.

For the solution given above, if we simply add print(curr) after the line curr.append(num), then we can very clearly see how each call to backtrack is like visiting a node in the tree (it's like performing a DFS on an imaginary tree):

[1]
[1, 2]
[1, 2, 3]   # complete permutation (leaf node)
[1, 3]
[1, 3, 2]   # complete permutation (leaf node)
[2]
[2, 1]
[2, 1, 3]   # complete permutation (leaf node)
[2, 3]
[2, 3, 1]   # complete permutation (leaf node)
[3]
[3, 1]
[3, 1, 2]   # complete permutation (leaf node)
[3, 2]
[3, 2, 1]   # complete permutation (leaf node)

The entire list of complete permutations is then returned as the answer:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

The time complexity above effectively amounts to roughly $O(n^2\cdot n!)$ , because we iterate through all of nums for each call to backtrack, and membership to curr is a linear cost when curr is an array, and then we're guaranteed to make $n$ calls to backtrack, and each call to backtrack then results in $n - 1$ calls, and so forth. If we wanted to make a micro-optimization, then we could introduce a hash set to make the membership checks on curr $O(1)$ instead of $O(n)$ , but this change pales in comparison to the factorial cost of calling backtrack so many times:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(curr):
            if len(curr) == len(nums):
                permutations.append(curr[:])
                return
            
            for num in nums:
                if num not in lookup:
                    curr.append(num)
                    lookup.add(num)
                    backtrack(curr)
                    curr.pop()
                    lookup.remove(num)
        
        lookup = set()
        permutations = []
        backtrack([])
        
        return permutations

LC 78. Subsets (✓) ★★

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.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(curr, num_idx):
            subs.append(curr[:])
            
            if num_idx == len(nums):      # note that this base case is implied
                return                    # since `backtrack` is only called in the 
                                          # for loop when `num_idx < len(nums)`
            
            for i in range(num_idx, len(nums)):
                curr.append(nums[i])
                backtrack(curr, i + 1)
                curr.pop()
                
        subs = []
        backtrack([], 0)
        
        return subs

This problem is quite similar to LC 46. Permutations but with some very notable differences, namely container length and element order:

Length: A subset can have any length from 0 through n (where n is the size of the input array of distinct integers), inclusive, but a permutation has a fixed length of n.
Order: The containers [1, 2, 3] and [3, 2, 1] are considered to be different permutations but the same subset.

If we have a problem where containers like those above are considered to be duplicates and we do not want to consider duplicates (e.g., such as this problem concerned with finding subsets), then a common "trick" is to add a rule where each call of the backtrack function allows us to only consider elements that come after the previously processed element:

This is a very common method of avoiding duplicates in backtracking problems — have an integer argument that represents a starting point for iteration at each function call.

For example, in this problem, we start with the root being the empty container, []:

[]

With nums = [1, 2, 3], we can clearly consider each element as the beginning of its own subset:

     [ ]
  /   |   \
[1]  [2]  [3]

Now what? Remember that calling backtrack is like moving to another node; hence, to respect the strategy remarked on above, when we move to another node, that node should only involve elements that come after the one we have just processed. This means the tree of possibilities above should end up looking like the following:

         [ ]          # level subsets: []
    /     |     \
  [1]    [2]    [3]   # level subsets: [1], [2], [3]
  / \     |
[2] [3]  [3]          # level subsets: [1,2], [1,3], [2,3]
 |
[3]                   # level subsets: [1,2,3]

The actual order of subset generation from our solution code is not hard to anticipate in light of the strategy we've been discussing, where, again, we're basically doing a DFS on an imaginary tree, and once we hit the last indexed element (i.e., when index == len(nums)) we move back up the tree from child to parent:

[
  [],
  [1],
  [1,2],
  [1,2,3],
  [1,3],
  [2]
  [2,3]
  [3]
]

The order conjectured above is confirmed by the return value of our solution when nums = [1, 2, 3]:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

The process becomes even clearer if we add the print statement print(subs) after subs.append(curr[:]) as well as the print statement print('COMPLETED') after if num_idx == len(nums):. Making these modifications and running the solution code again on the input nums = [1,2,3] results in the following being printed to standard output:

[[]]
[[], [1]]
[[], [1], [1, 2]]
[[], [1], [1, 2], [1, 2, 3]]
COMPLETED
[[], [1], [1, 2], [1, 2, 3], [1, 3]]
COMPLETED
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]
COMPLETED
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
COMPLETED
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Note that the text 'COMPLETED' is only ever printed after an element/subset has been added to subs that ends with 3, which corresponds to the leaves of the tree shown earlier.

To summarize, when generating permutations, we had a length requirement, where we needed to use all of the elements in the input; hence, we only considered leaf nodes as part of the actual returned answer. With subsets, however, there is no length requirement; thus, every node should be in the returned answer, including the root node, which is why the very first line of the backtrack function is to add a copy of curr to the returned answer subs.

LC 77. Combinations (✓) ★★

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. You may return the answer in any order.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(curr, start_val):
            if len(curr) == k:
                combinations.append(curr[:])
                return
            
            for i in range(start_val, n + 1):
                curr.append(i)
                backtrack(curr, i + 1)
                curr.pop()
        
        combinations = []
        backtrack([], 1)
        
        return combinations

It can be very helpful to sketch out a tree of possibilities if we suspect backtracking may be an effective strategy for coming up with a solution (just like sketching out things for general tree problems, linked list problems, etc.).

The root of our tree would be [], the empty list. Unlike in LC 78. Subsets, there is an explicit length requirement in terms of the elements that can be added to the container we must ultimately return; hence, not all nodes in the tree of possibilities will represent entities that should be added to our answer array.

What is clear is that each entry added to the list we must return must have a length of k, and it must contain numbers from the list [1, ..., n], inclusive, where no number in the k-length list is duplicated. This means we should consider combining some of the strategy points we used in both LC 46. Permutations and LC 78. Subsets, namely using a length requirement as part of the base case as well as preventing duplicates from being considered, respectively.

The thinking goes something like the following: start with the empty list, [], as the root of the tree:

[]

Each k-length list can have a number from [1, ..., n], inclusive; thus, the root should have n children, namely nodes with values from 1 through n (the example below uses the values of n = 4, k = 2 from the first example on LeetCode):

         [ ]
[1]   [2]   [3]   [4]

Now what? A complete solution will be generated only when the path has length k, but each path right now has a length of 1 (but k = 2 for this example). To keep generating paths (i.e., possible solutions), we need to avoid considering duplicates, which means for each node value i, we only subsequently consider node values [i + 1, ..., n], which results in our overall tree looking like the following:

                      [ ]
    [1]          [2]       [3]   [4]
[2] [3] [4]    [3] [4]     [4]

Since the input specifies k = 2, the tree above suffices to report the following as the combinations list:

[
  [1,2],
  [1,3],
  [1,4],
  [2,3],
  [2,4],
  [3,4]
]

LC 797. All Paths From Source to Target (✓) ★

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def backtrack(curr_path, node):
            if node == len(graph) - 1:
                paths.append(curr_path[:])
                return
                
            for neighbor in graph[node]:
                curr_path.append(neighbor)
                backtrack(curr_path, neighbor)
                curr_path.pop()
                
        paths = []
        backtrack([0], 0)
        
        return paths

This is a great backtracking problem because backtracking is not necessarily the obvious first strategy of attack. Even if we do think of backtracking, how exactly should we proceed? This becomes much clearer (again!) once we start to sketch out the tree of possibilities. What would the root of our tree be? It has to be node 0 since our goal is to find all paths from node 0 to node n - 1. This also suggests something about our base case: we should terminate path generation whenever node n - 1 is reached. We don't have to worry about cycles or anything like that since we're told the graph is a DAG. Additionally, the graph is already provided as an adjacency list which makes traversing each node's neighbors quite easy.

So what's the strategy? Let's start with our root node (which needs to be part of every solution):

Now what? Each neighbor of node 0 needs to be considered (we're trying to get to node n - 1 from node 0 in whatever way is possible, which means exploring all possible paths). Let's use the input of the second example on LeetCode for a concrete illustration: graph = [[4,3,1],[3,2,4],[3],[4],[]]. This graphs looks like the following:

As stated above, from 0 we need to consider each of its neighbors:

     0
   / | \
  1  3  4

The tree above makes it clear [0,4] will be one possible path, but what are the other possible paths? It looks like leaf nodes will be the complete solutions that need to be added to our answer that we ultimately return. For each node that is not 4 (i.e., n - 1 == 4 in this case), we need to consider each possible neighbor (this will not be endless because we're told the graph is a DAG). Considering the neighbors for each node means our tree of possibilities ultimately ends up looking as follows:

             0
       /     |     \
      1      3      4
    / | \    |
   2  3  4   4
   |  |
   3  4
   |
   4

Hence, the set of possible paths is as expected:

[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

LC 17. Letter Combinations of a Phone Number (✓) ★★

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        keypad = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        
        def backtrack(curr, start_idx):
            if len(curr) == len(digits):
                combinations.append("".join(curr))
                return
            
            for i in range(start_idx, len(digits)):
                digit = digits[i]
                for letter in keypad[digit]:
                    curr.append(letter)
                    backtrack(curr, i + 1)
                    curr.pop()
            
        combinations = []
        backtrack([], 0)
        
        return combinations

As with most other backtracking problems, it helps if we start by sketching out the tree of possibilities, where we can imagine the root being an empty string:

''

Now let's consider the input digits = "23", the input for the first example on LeetCode. The desired output is ["ad","ae","af","bd","be","bf","cd","ce","cf"]. How can this be achieved? The first digit is 2, which means 'a', 'b', and 'c' are valid starting letters for combinations:

      ' '
   /   |   \
 'a'  'b'  'c'

We do not want to add duplicates of these letters for subsequent possible combinations but instead consider the potential letters arising from the next digit (i.e., we want to prevent processing duplicates by only ever processing digits after the current digit). The next digit in this case is 3 which corresponds to possible letters 'd', 'e', and 'f'. Our tree now looks like the following:

                   ' '
        /           |           \
      'a'          'b'          'c'
    /  |  \      /  |  \      /  |  \
  'd' 'e' 'f'  'd' 'e' 'f'  'd' 'e' 'f'

The tree of possibilities above makes it clear the letter combinations we should return are as follows, as expected:

[
  'ad',
  'ae',
  'af',
  'bd',
  'be',
  'bf',
  'cd',
  'ce',
  'cf',
]

LC 39. Combination Sum (✓) ★

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(path, path_sum, next_path_node_idx):
            if path_sum == target:
                paths.append(path[:])
                return
            
            for i in range(next_path_node_idx, len(candidates)):
                candidate = candidates[i]
                if path_sum + candidate <= target:
                    path.append(candidate)
                    backtrack(path, path_sum + candidate, i)
                    path.pop()
        
        paths = []
        backtrack([], 0, 0)
        
        return paths

This problem is similar to LC 77. Combinations, but now we are taksed with generating all combinations of candidates such that each candidate number is allowed however many times we want, but the sum of the numbers for each combination/mixture of candidates has to equal the given target.

Start by drawing a tree!

[]

Each number in candidates may be part of a path sum we want to return, where the sum of the elements in the path equates to target. Let's use the input provided in the first example on LeetCode: candidates = [2,3,6,7], target = 7:

     [ ]
  /  / \  \
 2  3   6  7 

The problem description indicates any number may be reused however many times we desire, but we still don't want to generate duplicates such as [2,2,3], [2,3,2], etc. How can we avoid doing this? We can use the same strategy that many other backtracking problems use (i.e., ensure we only begin processing elements that are either the current element itself or elements that come after the current element):

                   [ ]
      /         /       \        \
     2         3         6        7 
  / / \ \     /|\       / \       |
 2 3   6 7   3 6 7     6   7      7
 ..................................

When do we stop the process of generating paths? Since all possible values in candidates are positive, this necessarily means a path is no longer valid if its path sum exceeds the given target value.

Note that the following lines in the solution above are important:

# ...
for i in range(next_path_node_idx, len(candidates)):
    candidate = candidates[i]
    if path_sum + candidate <= target:
        path.append(candidate)
# ...

It might be tempting to modify path_sum with the candidate value before entering the if block, but this would be a mistake. Why? Because the list of candidates is not necessarily ordered; hence, if we made the update path_sum += candidate and the new path_sum exceeded target, then we would no longer consider that path, but this would also prevent us from exploring other branches using candidates of a possibly lesser value where path_sum + candidate did not exceed target.

LC 79. Word Search (✓) ★★★

Given an m x n board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n
        
        def backtrack(row, col, word_idx, seen):
            if word_idx == len(word):
                return True
            
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                if valid(next_row, next_col) and (next_row, next_col) not in seen:
                    next_char = board[next_row][next_col]
                    if next_char == word[word_idx]:
                        seen.add((next_row, next_col))
                        if backtrack(next_row, next_col, word_idx + 1, seen):
                            return True
                        seen.remove((next_row, next_col))
            
            return False
        
        m = len(board)
        n = len(board[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        
        for row in range(m):
            for col in range(n):
                if board[row][col] == word[0] and backtrack(row, col, 1, {(row, col)}):
                    return True
                
        return False

This problem has a very DFS feel to it, but what makes this a backtracking problem and not a strict DFS problem is because we may visit a square multiple times on the same initial function call. For example, suppose we're looking for the word CAMERA in the following grid:

CAM
ARE
MPS

We may start exploring as follows (each | represents the path taken):

C  A  M
|
A  R  E
|
M  P  S

The M-letter above does not have E as a neighbor so we remove the M from consideration and move back up to A, which also does not have an M-neighbor except the one we just visited, which we know leads to nothing. So we remove A as well and we're back at C, and we note C does have another A-neighbor it can visit. And we end up seeing the following as a valid path:

C -> A -> M
          |
A <- R <- E

M    P    S

This path visits the A under C again in order to come up with a valid path. Thus, while we may not be allowed to use a square more than once for the answer, there are possibly multiple ways to use a square to form different candidates, as illustrated above.

We should still use a set seen like we would normally do with DFS solutions so as to avoid using the same letter in the same path. Unlike in DFS solutions, however, we will remove from the set seen when backtracking and it's been determined that a path solution is no longer possible — we should only ever traverse an edge in the graph if we know that the resultant path could lead to an answer. Thus, we can also pass an index variable word_idx that indicates we are currently looking for word[word_idx], and then only move to (next_row, next_col) if word[word_idx] is the correct letter.

Since the answer could start from any square whose letter matches word[0], we need to systematically start our backtracking approach from any square with word[0] as its letter. If we exhaust all such squares and never find word, then we should return false. Of course, if we do find word in the midst of one of our backtracking approaches, then we return true immediately.

LC 52. N-Queens II (✓) ★★★

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

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row, cols, diagonals, anti_diagonals):
            # base case: n queens have been placed
            if row == n:
                return 1
            
            solution = 0
            for col in range(n):
                diagonal = row - col
                anti_diagonal = row + col
                
                # queen is not placeable, move to considering next column
                if (col in cols or diagonal in diagonals or anti_diagonal in anti_diagonals):
                    continue
                
                # add the queen to the board
                cols.add(col)
                diagonals.add(diagonal)
                anti_diagonals.add(anti_diagonal)
                
                # move to next row with the updated board state
                solution += backtrack(row + 1, cols, diagonals, anti_diagonals)
                
                # remove the queen from the board since we have
                # explored all valid paths using the above backtrack function call
                cols.remove(col)
                diagonals.remove(diagonal)
                anti_diagonals.remove(anti_diagonal)
                
            return solution
            
        return backtrack(0, set(), set(), set())

This problem is difficult. And it's often used to explain backtracking at various learning levels (e.g., university and college classes). The solution to this problem is informative, especially in regards to how we might want to go about modeling backtracking solutions to other problems.

Whenver we make a call to backtrack, we're doing so by describing the state of whatever it is that is important for consideration in solving the problem at hand. For some problems, maybe that state involves a string and the number of used left and right parentheses (e.g., LC 22. Generate Parentheses), maybe the state involves the row and column of a grid under consideration along with the cells already seen and the index of a word that represents a character for which we are searching (e.g., LC 79. Word Search). And maybe, as in this problem, the state needs to involve a chessboard!

What state should we consider tracking? We need to somehow keep track of rows and columns in some way. The trickier part about this problem involves the diagonals. Even though we have a board in this problem, this is not like a graph problem where we need to conduct a DFS or BFS — fundamentally, our job at each step is to place a queen on the board so that it is not under attack. This is the backtracking part where we narrow down the range of possibilities we consider — the brute force approach would involve generating all board possibilities with queens and then narrow down which solutions actually work, but that would involve placing queens on the board in positions that are being attacked, which means the rest of the generation of possibilities is useless. We want to place queens in positions where they are not being attacked and where whatever subsequent positions we consider can actually lead to a solution. Only once we find a solution do we start to undo queen placement and try other queen placements, but the key is that every placement must be one that could potentially lead to success.

With everything in mind above, how should we proceed? First, it's helpful to just think about how queens move on a chessboard: unlimited moves vertically, horizontally, diagonally (top left to bottom right), and anti-diagonally (top right to bottom left). If we are given n queens on an n x n chessboard, then it's clear that, at the end of the board configuration, each row must have a queen and each column must have a queen. The trickiest part is managing the diagonals effectively.

But we can start by working with the insight above about rows and columns. Each time backtrack is called should result in the placement of a queen on a new row; that is, we'll pass row as an argument to backtrack, and when we have finally reached row == n (i.e., rows 0 through n - 1 have been filled with queens), then we will know we have found a valid solution. Finding a workable position on any given row means processing all column positions on that row until we have found a position that is not under attack.

What about columns? As noted above, for each row being processed, we will iterate through all row positions (i.e., across all columns) until we find a column position that is not under attack. The row we are processing is definitely not under attack due to how we're processing rows, but how do we know whether or not each column is under attack? If another queen is on any column we're considering for a current row, then that column position is invalid because that other queen's line of attack runs through the current position we're considering. We need to consider the next column position. To keep track of which columns are already occupied by queens (i.e., which columns would be considered to be under attack when we're trying to add a new queen), whenever we add a queen to the board, we should add the column position of the queen to a set cols that we can use when we're trying to add subsequent queens.

Cool! We consider rows sequentially so it's guaranteed each row we're considering is not under attack. We have a set cols that shows which columns are occupied. It seems like we need a similar "strategy" for diagonals and anti-diagonals that we currently have for columns; that is, whenever we add a queen to the board, we should also note which diagonal and anti-diagonal just became occupied. But how do we effectively apply a singular label or marker to a diagonal or anti-diagonal that spans multiple positions on the board?

This seems really tricky to do at first until we make note of a brilliant observation concerning diagonal and anti-diagonal movement (R and C below represent row and column position, respectively):

diagonal movement (top left to bottom right): If we start at any cell (R, C) and move one position up, then we will be at cell (R - 1, C - 1). If we move one position down, then we will be at (R + 1, C + 1). In general, if we let dr and dc represent the change in row or column value, respectively, then we will find ourselves always moving from cell (R, C) to (R + dr, C + dc) on a given diagonal. Importantly, note that dr == dc since a change in any direction effects each value in the same way (e.g., moving 4 spaces up means dr == dc == -4 since the row and column values both decrease by 4).

But how does any of this help in service of creating a unique label for a diagonal? The insight lies in how the row and column values relate to each other. Let (R, C) be the coordinates of a cell on a diagonal, and let's label the cell as having value R - C. Then what happens whenever we move from cell (R, C) to cell (R + dr, C + dc)? Since dr == dc, we have (R + dr) - (C + dc) = R + dr - C - dr = R - C; that is, the label for any cell on a diagonal is the same:

Hence, we should label visited diagonals by adding row - col values to a diagonals set.
anti-diagonal movement (top right to bottom left): We can make a similar argument to the one above about effectively labeling anti-diagonals. Let (R, C) represent any given cell on an anti-diagonal. Then moving up a cell would take us to cell (R - 1, C + 1) while moving down a cell would take us to cell (R + 1, C - 1); that is, the row and column values of a cell change at the same rate in an inversely proportional manner. We essentially have dr == dc again, but there needs to be a sign difference in how we represent a movement from (R, C) to another cell: (R + dr, C - dc). Then (R + dr) + (C - dc) = R + dr + C - dr = R + C:

Hence, we should label visited anti-diagonals by adding row + col values to an anti-diagonals set.

LC 22. Generate Parentheses (✓) ★★★

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

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def backtrack(curr_str, left_count, right_count):
            if len(curr_str) == 2 * n:
                valid_parens.append("".join(curr_str))
                return
                
            if left_count < n:
                curr_str.append('(')
                backtrack(curr_str, left_count + 1, right_count)
                curr_str.pop()
            
            if left_count > right_count:
                curr_str.append(')')
                backtrack(curr_str, left_count, right_count + 1)
                curr_str.pop()
        
        valid_parens = []
        backtrack([], 0, 0)
        
        return valid_parens

The editorial for this solution on LeetCode is quite good. The key insights (with the first being somewhat minor but the second one being critical):

We should append the string we're building whenever its length is 2n because the string we're building, when taking a backtracking approach anyway, must have the potential to be valid and a complete solution at every point. Hence, once/if the candidate string reaches a length of 2n, then we know the string satisfies the constraints of the problem and is a complete solution.
As a starting point, we can add as many left-parentheses as we want without fear of producing an invalid string (so long as the number of left parentheses we add doesn't exceed n). We then need to start adding right parentheses. But how can we add right parentheses in general? We should only ever consider adding a right parenthesis when the total number of left parentheses exceeds the number of right parentheses. That way when we add a right parenthesis there's a chance the subsequent string could be a well-formed parenthetical string of length 2n, as desired.

The LeetCode editorial linked above shows how sketching out a tree of possibilities is very useful for this problem, where the following illustration is for the beginning of the case where n = 2:

We can start to see how the logic of the solution above makes sense. For the sake of completeness and concreteness, consider the input of the first example on LeetCode, n = 3, and the corresponding desired output:

["((()))","(()())","(())()","()(())","()()()"]

We can make our own diagram that shows how each solution is built (the x indicates that potential solution path is longer pursued since further work on that path cannot possibly lead to a correct answer):

                                                                                 _____________________________________________________"
                                                                                /                                                      \
                              _________________________________________________(________________________________________________        x
                             /                                                                                                  \
     _______________________((_______________________                                                     _______________________()
    /                                                \                                                   /                         \
  (((___                            _________________(()________________              _________________()(________________          x
 /      \                          /                                    \            /                                    \
x       ((()____                 (()(____                      _________(())       ()((____                      _________()()
       /        \               /        \                    /             \     /        \                    /             \
      x        ((())__         x        (()()__            (())(__           x   x        ()(()__            ()()(__           x
              /       \                /       \          /       \                      /       \          /       \
             x       ((()))           x       (()())     x       (())()                 x       ()(())     x       ()()()

As a note of reference, the tree above was generated using the binarytree package:

from binarytree import build2
my_tree = build2([
    '"',
    "(", 'x',
    "((", "()", None, None,
    "(((", "(()", "()(", "x",
    "x", "((()", "(()(", "(())", "()((", "()()", None, None,
    None, None, "x", "((())", "x", "(()()", "(())(", "x", "x", "()(()", "()()(", "x",
    None, None, "x", "((()))", None, None, "x", "(()())", "x", "(())()", None, None, None, None, "x", "()(())", "x", "()()()"
])

root = my_tree.levelorder[0]
print(root)

LC 967. Numbers With Same Consecutive Differences (✓) ★★

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        def digits_to_int(digits):
            ans = digits[0]
            for i in range(1, len(digits)):
                ans = (ans * 10) + digits[i]
            return ans
        
        def backtrack(digit_arr):
            if len(digit_arr) == n:
                res.append(digits_to_int(digit_arr))
                return
            
            for num in range(10):
                if abs(digit_arr[-1] - num) == k:
                    digit_arr.append(num)
                    backtrack(digit_arr)
                    digit_arr.pop()
                    
        res = []
        for start_digit in range(1, 10):
            backtrack([start_digit])
            
        return res

The impossibility of leading zeros can complicate things if we're not careful. We still need to consider the digit 0 as part of potential constraint-satisfying integers. An easy way to handle this is to completely prevent 0 from being a possible leading digit at the outset. Execute the backtrack function for digit arrays that begin with each number 1 through 9, inclusive, and append complete solutions to an overall results array, res, that we ultimately return. It's easiest to manage the digits if we build each integer using a digits array and then return the actual integer once the digits array represents a constraint-satisfying integer.

LC 216. Combination Sum III (✓) ★

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtrack(nums_arr, curr_sum, next_num):
            if len(nums_arr) == k and curr_sum == n:
                res.append(nums_arr[:])
                return
            
            for num in range(next_num, 10):
                if curr_sum + num <= n:
                    nums_arr.append(num)
                    backtrack(nums_arr, curr_sum + num, num + 1)
                    nums_arr.pop()
            
        res = []
        backtrack([], 0, 1)
        
        return res

The valid combinations can only involve positive integers, which means the sum we're building can only get bigger. Hence, we should only consider as possibilities combinations of integers for which the sum does not exceed n. Also, the numbers used as part of the combination need to be unique. Which means whenever we start with a certain number we should only ever consider subsequent integer values.

Binary search

Find first target index (if it exists)

Remarks

This template will return the first index where target is encountered. If duplicates are present, then the index returned is effectively random (i.e., the target matched/identified by means of the search could be neither the leftmost occurrence nor the rightmost occurrence but somewhere in between). If no match is found, then the return value, left, will point to the insertion point where target would need to be inserted in order to maintain the sorted property of arr.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if target < arr[mid]:
            right = mid - 1
        elif target > arr[mid]:
            left = mid + 1
        else:
            return mid

    return left

Examples

LC 704. Binary Search

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.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if target < nums[mid]:    # target in left half, move right boundary
                right = mid - 1
            elif target > nums[mid]:  # target in right half, move left boundary
                left = mid + 1
            else:
                return mid            # target at current mid position, return
        
        return -1

The code above is the template for a basic binary search. We're guaranteed that the numbers in nums are unique, which means target, if it exists, will be found and the first index at which it occurs (and only index) will be returned.

LC 74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        
        left = 0
        right = m * n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            val = matrix[mid // n][mid % n]
            if target < val:
                right = mid - 1
            elif target > val:
                left = mid + 1
            else:
                return True
            
        return False

This problem is very similar to the following classic binary search problem: LC 704. Binary Search. The main difference is that in this problem we basically need to view the 2D array matrix as virtually flattened into a 1D array with index values idx bounded by 0 <= idx <= m * n - 1. The key part of the solution above is, of course, the following line: val = matrix[mid // n][mid % n]. This lets us seamlessly find a cell value in the virtually flattened matrix by converting a given index value to the appropriate row and column in the original input matrix. We could make this more explicit by abstracting away the logic in the line above into its own function:

def index_to_cell_val(idx):
    row = idx // n
    col = idx % n
    return matrix[row][col]

The idea is that we can binary search on the virtually flattened 1D array.

LC 35. Search Insert Position (✓)

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if target < nums[mid]:
                right = mid - 1
            elif target > nums[mid]:
                left = mid + 1
            else:
                return mid
            
        return left

Distinctness of the input integers in nums ensures returning mid will be the index of target if it's found; otherwise, we return left, which will be the index where we should insert target in order to keep a sorted array.

LC 633. Sum of Square Numbers★

Given a non-negative integer c, decide whether there're two integers a and b such that a² + b² = c.

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        def binary_search(left, right, target):
            while left <= right:
                b = left + (right - left) // 2
                if target < b * b:
                    right = b - 1
                elif target > b * b:
                    left = b + 1
                else:
                    return True
            return False
        
        a = 0
        while a * a <= c:
            b_squared = c - a * a
            if binary_search(0, b_squared, b_squared):
                return True
            a += 1
        
        return False

Binary search can crop up in all sorts of unexpected places. This is one of them. The idea is that we iteratively search the space [0, c - a^2] for a value of b such that b^2 == c - a^2 that way a^2 + b^2 == c, as desired. The funkier part of the binary search solution is what the usual mid denotes in the binary search itself, namely the b-value we're looking for such that b^2 == target, where target == c - a^2. Hence, when we make adjustments to the left or right endpoints, we're actually comparing the target value against b * b where b takes the role of the normal mid value. If it's ever the case that the target is neither less than b * b nor greater than b * b, then we've found an integer b-value that satisfies the equation (and we've done so using binary search!).

Find leftmost target index (or insertion point)

Remarks

This template ensures we find the leftmost occurrence (i.e., minimum index value) of target (if it exists). If target does not exist in the input array, arr, then this template will return the index at which target should be inserted to maintain the ordered property of arr.

How does this work? What happens if it's ever the case that arr[mid] == target in the template function above? It's the right half that gets collapsed, by means of right = mid, thus pushing the search space as far left as possible.

Computing total number of elements within input array less than target value

The left value returned by the function in the template above is also the number of elements in arr that are less than target.

This should make sense upon some reflection — if the function in our template returns the left-most occurrence of the target value as well as the insertion point of target to keep the sorted property of arr, then it must be the case that all values to the left of the returned value are less than target. The fact that arrays are 0-indexed helps here; for example, if our template function returns 3, then this means the three elements at index 0, 1, and 2 are all less than target.

def binary_search_leftmost(arr, target):
    left = 0
    right = len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if target <= arr[mid]:
            right = mid
        else:
            left = mid + 1

    return left

Examples

LC 2300. Successful Pairs of Spells and Potions

You are given two positive integer arrays spells and potions, of length n and m, respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        def successful_potions(spell_strength):
            # need spell * potion >= success (i.e., potion >= threshold)
            threshold = success / spell_strength
            
            left = 0
            right = len(potions)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if threshold <= potions[mid]:
                    right = mid
                else:
                    left = mid + 1
                    
            return len(potions) - left
        
        potions.sort()
        return [ successful_potions(spell) for spell in spells ]

For any potion to actually be successful, it must be greater than or equal to success / spell for any given spell. Since we process potions for each spell in spells, this suggests we should pre-process potions by sorting. Then we can conduct a binary search (where the target is equal to success / spell for a given spell) to determine the where the insertion point would need to be in order for a new potion to be successful. We want everything to the right of that point. Hence, if len(potions) is the length of the potions array and we determine that the leftmost insertion point should occur at i, then we want everything from [i, len(potions) - 1]; that is, (len(potions) - 1) - i + 1 == len(potions) - i, where the first + 1 reflects inclusivity of i. An example will make this clear.

Let's say we sort potions and have potions = [1, 2, 3, 4, 5], and success = 7. We have a spell with a strength of 3. To form a successful pair, we need a potion with a strength of at least 7 / 3 = 2.3333. If we do a binary search for this value on potions, we will find an insertion index of 2. Every potion on this index and to the right can form a successful pair. There are 3 indices in total (the potions with strength 3, 4, 5). In general, if there are m potions, the final index is m - 1. If the insertion index is i, then the range [i, m - 1] has a size of (m - 1) - i + 1 = m - i.

Find rightmost target index

Remarks

This template ensures we find the rightmost occurrence (i.e., maximum index value) of target (if it exists). If target does not exist in the input array, arr, then this template will return the index before which target should be inserted to maintain the ordered property of arr (i.e., left will return the proper insertion point as opposed to left - 1).

How does this work? What happens if it's ever the case that arr[mid] == target in the template function above? It's the left half that gets collapsed, by means of left = mid + 1, thus pushing the search space as far right as possible.

Computing total number of elements within input array greater than target value (as well as insertion point)

Consider the following sorted array: [4, 6, 8, 8, 8, 10, 12, 13]. If we applied the function in the template above to this array with a target value of 8, then the index returned would be 4, the index of the right-most target value 8 in the input array. This simple example illustrates two noteworthy observations:

Insertion point: Add a value of 1 to the return value of the template function to find the appropriate insertion point — this assumes the desired insertion point is meant to keep the input array sorted as well as for the inserted element to be as far-right as possible.

In the context of the simple example, this means the insertion point for another 8 would be 4 + 1 = 5. What if the element to be added is not present? If we wanted to add 9, then our template function would return 4. Again, adding 1 to this result gives us our desired insertion point: 4 + 1 = 5. The correct insertion point will always be the returned value plus 1.
Number of elements greater than target: If x is the return value of our template function, then computing len(arr) - x + 1 will give us the total number of elements in the input array that are greater than the target.

In the context of the simple example, how many elements are greater than 8? There are three such elements, namely 10, 12, and 13; hence, the answer we want is 3. How can we reliably find the value we desire for all sorted input arrays and target values?

If our template function returns the right-most index of the target element if it exists or where it would need to be inserted if it doesn't exist, then this means all elements in the input array to the right of this index are greater than the target value. How can we reliably calculate this number? Well, if you're tasked with reading pages 23-27, inclusive, then how many pages are you tasked with reading? It's not 27 - 23 = 4. You have to read pages 23, 24, 25, 26, and 27 or simply 27 - 23 + 1 = 5. The same reasoning, albeit slightly nuanced, applies here: If index x is the index returned by our function, then how many elements exist from the right of this element to the end of the array, inclusive? The last element in the array has an index of len(arr) - 1 and the element to the right of the returned value has an index of x + 1. Hence, the total number of values shakes out to be
```
(len(arr) - 1) - (x + 1) + 1 = len(arr) - x + 1
```

def binary_search_rightmost(arr, target):
    left = 0
    right = len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if target < arr[mid]:
            right = mid
        else:
            left = mid + 1

    return left - 1

Examples

LC 2389. Longest Subsequence With Limited Sum (✓) ★

You are given an integer array nums of length n, and an integer array queries of length m.

Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        def binary_search(query):
            left = 0
            right = len(nums)
            
            while left < right:
                mid = left + (right - left) // 2
                if query < nums[mid]:
                    right = mid
                else:
                    left = mid + 1
            
            return left
        
        nums.sort()
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        
        return [ binary_search(query) for query in queries ]

This problem invites us to dust off our knowledge of prefix sums — because that's really what we need to effectively answer this problem. We need to sort the input nums, create a prefix sum (either mutate the input directly, as above, or create a new array), and then conduct a binary search on the prefix sum where each time we try to find what would need to be the rightmost insertion point if we were to add query to the prefix sum array.

Why does this work. Suppose we had the prefix sum [0, 1, 3, 5, 5, 7, 9], and the query value we were given was 5. Where would we need to insert 5 in the prefix sum above to maintain sorted order so that 5 was as far right as possible? It would need to be at index i == 5 (right after the other two 5 values). This means the original numbers in nums responsible for the [0, 1, 3, 5, 5] part of the preifx sum can all be removed so that the sum is less than or equal to the query value 5. That is why the solution above works.

Greedy (looking for minimum)

Temporary remarks for greedy-based binary searches on solution spaces

As noted in the editorial on binary search on solution spaces, we need a few conditions to be met in order to effectively conduct our search:

Possibility/condition/check/feasible function can execute in $O(n)$ time -- we can quickly, in $O(n)$ or better, verify if the task is possible for a given threshold value threshold; that is, we define a function, possible(threshold), that returns a boolean that indicates if the given task is possible or impossible when given the specifc threshold value.
Max/min characteristic when task is possible given the specific threshold value -- if the task is possible for a number threshold and we are looking for

a maximum, then it is also possible for all numbers less than threshold.
a minimum, then it is also possible for all numbers greater than threshold.

Max/min characteristic when task is impossible given the specific threshold value -- if the task is impossible for a number threshold and we are looking for

a maximum, then it is also impossible for all numbers greater than threshold.
a minimum, then it is also impossible for all numbers less than threshold.

The above depictions can be somewhat difficult to envision at first so it can be helpful to draw out a very simple outline as if we're on a number line from 0 to infinity, left to right, as demonstrated below.

Looking for a maximum threshold:

Example use case (illegal parking): Maximize time spent parked illegally without getting a ticket. Under various conditions (e.g., parking enforcers, location, etc.), we can imagine this being possible for a certain amount of time before it becomes impossible. We'd like to maximize the POSSIBLE amount of time we do not have to worry about getting a ticket before it becomes IMPOSSIBLE to avoid getting a ticket:

Problem is asking for a maximum
 -----------------------
| Possible | Impossible |
 -----------------------
 0         ^       ...inf
      (threshold binary searched for)

As can be seen above, given a threshold amount of time, our task of going undetected when parked illegally is

possible for all numbers less than threshold
impossible for all numbers greater than threshold

Looking for a minimum threshold:

Example use case (mandatory online trainings): Minimize time spent on a manadotry online trainin page before clicking to continue without arousing suspicion. Many online training requirements are modules that are "click-through" in nature, where an employee must complete the module but should not "click to continue" until a sufficient amount of time has elapsed to indicate the employee has possibly consumed all of the information on the page. The goal is to minimize the amount of time spent on any given page. We can imagine this being impossible for a certain amount of time before it becomes possible. We'd like to minimize the POSSIBLE amount of time we are required to be on any given training page where it is IMPOSSIBLE to avoid doing so until a certain amount of time has elapsed:

Problem is asking for a minimum
 -----------------------
| Impossible | Possible |
 -----------------------
 0           ^     ...inf
        (threshold binary searched for)

As can be seen above, given a threshold amount of time, our task of having to remain on a given training page before being allowed to continue making progress through the training is

impossible for all numbers less than threshold
possible for all numbers greater than threshold

TAKEAWAY: For minimums, we're basically trying to find the leftmost insertion point for threshold within the possible solution space. Our solution space should be closed: [left, right]. That is, the left bound should be as minimal as possible as well as inclusive. The right bound should be as maximal as possible as well as inclusive (this differs from the normal way we would try to find the leftmost insertion point when we're binary searching on a solution space that may contain duplicates ... the idea is that a solution/threshold that satisfies the problem requirement should exist within the original left/right bounds of the problem).

Here's a template:

def binary_search_on_solution_space_MINIMUM(arr):
    def possible(threshold):
        # this function is implemented depending on the problem
        return BOOLEAN

    left = MINIMUM_POSSIBLE_ANSWER
    right = MAXIMUM_POSSIBLE_ANSWER # solution space being binary searched is [left, right];
                                    # we are trying to find the leftmost insertion point for `threshold`
                                    # in the possible segment
    while left < right:
        mid = left + (right - left) // 2
        if possible(mid):
            right = mid # squeeze `left` as far left as possible in the possible segment
        else:
            left = mid + 1
    
    return left

Finding a maximum for a threshold is a bit different. It's similar to binary searching on an array of values and trying to find the position right before whatever the rightmost insertion point would need to be for the inserted value to maintain order. It's probably easier to visualize if we think of the simple diagram above for problems where we're being asked to find a maximum:

 -----------------------
| Possible | Impossible |
 -----------------------

We basically want to find the leftmost insertion point where we're satisfying the impossible condition, where the maximum value will then be whatever smaller position lies to the left (usually an integer value of 1) to make the value the rightmost value in the possible segment (i.e., the maximum possible value).

This requires a small adjustment to the template, most notably the solution space being [left, right), where the right bound is extended just slightly to ensure we actually capture the maximum value. And instead of returning left, which would give us the leftmost insertion position of the impossible segment, we return left - 1, which gives us the first value in the possible segment before the impossible segment (i.e., the maximal value in the possible segment):

def binary_search_on_solution_space_MAXIMUM(arr):
    def possible(threshold):
        # this function is implemented depending on the problem
        return BOOLEAN

    left = MINIMUM_POSSIBLE_ANSWER
    right = MAXIMUM_POSSIBLE_ANSWER + 1 # solution space being binary searched is [left, right) as opposed to [left, right];
                                        # we are trying to find the leftmost insertion point for `threshold`
                                        # in the impossible segment so we can report the position immediately to its left,
                                        # the last position in the possible segment before the impossible segment
                                        # (i.e., the maximum possible value)
    while left < right:
        mid = left + (right - left) // 2
        if not possible(mid):
            right = mid # squeeze `left` as far left as possible in the impossible segment
        else:
            left = mid + 1
    
    return left - 1

DIVIDING CHOCOLATE: This is a good problem for seeing how things work in regards to trying to find a maximum. Here's one potential solution:

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def possible(threshold):
            total_pieces = 0
            piece_sweetness = 0
            for chunk in sweetness:
                piece_sweetness += chunk
                if piece_sweetness >= threshold:
                    piece_sweetness = 0
                    total_pieces += 1
                    if total_pieces == k + 1:
                        return True
            return False
        
        left = min(sweetness)
        right = sum(sweetness) + 1
        
        while left < right:
            mid = left + (right - left) // 2
            if not possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left - 1

Consider the following simple test case:

sweetness = [5,5]
k = 0

Since we have k = 0, this means we are not going to share the chocolate with anyone else so we should just maximize the sweetness for our own enjoyment. The value returned should be 10, the entire sum of the values in sweetness. But what happens if we change the line right = sum(sweetness) + 1 to right = sum(sweetness)? Then the while loop will terminate when left == right, which will now happen when left and right both equal 10, but the value returned, left - 1, will be 9, which results in an off-by-one error.

This simple example illustrates the importance of binary searching the solution space represented by the half-open interval [left, right) when looking for a maximum; otherwise, we might end up with an off-by-one error.

Remarks

TBD

def binary_search_on_solution_space_MINIMUM(arr):
    def possible(threshold):
        # this function is implemented depending on the problem
        return BOOLEAN

    left = MINIMUM_POSSIBLE_ANSWER
    right = MAXIMUM_POSSIBLE_ANSWER # solution space being binary searched is [left, right];
                                    # we are trying to find the leftmost insertion point for `threshold`
                                    # in the possible segment
    while left < right:
        mid = left + (right - left) // 2
        if possible(mid):
            right = mid # squeeze `left` as far left as possible in the possible segment
        else:
            left = mid + 1
    
    return left

Examples

LC 875. Koko Eating Bananas (✓) ★

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.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def possible(speed):
            hours_spent = 0
            for banana in piles:
                hours_spent += -(banana // -speed)
                if hours_spent > h:
                    return False
            return True
        
        left = 1
        right = max(piles)
        
        while left < right:
            mid = left + (right - left) // 2
            if possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left

The idea is for Koko to go as slowly as possible while still being able to eat all bananas within h hours. Our goal is to find the speed at which Koko can eat all bananas but as soon as we decrease the speed it becomes impossible (that will give us the minimized speed for which eating all bananas is possible).

Hence, we can binary search on the solution space where the solution space is comprised of speeds in the range [min_possible_speed, max_possible_speed], inclusive. What would make sense as a minimum possible speed? The speed needs to be an integer and it clearly can't be 0; hence, the minimum possible speed is 0 so we set left = 0. What about the maximum possible speed? Each pile can be consumed within a single hour if the speed is the size of the pile with the greatest number of bananas; hence, the maximum possible speed we should account for is max(piles) so we set right = max(piles).

All that is left to do now is to greedily search for the leftmost value in the solution space that satisfies the possible constraint.

LC 1631. Path With Minimum Effort (✓) ★★

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n
        
        def possible(route_max_abs_diff):
            seen = {(0,0)}
            def dfs(row, col):
                if row == m - 1 and col == n - 1:
                    return True
                
                for dr, dc in dirs:
                    next_row, next_col = row + dr, col + dc
                    if valid(next_row, next_col) and (next_row, next_col) not in seen:
                        cell_val = heights[row][col]
                        adjacent_cell_val = heights[next_row][next_col]
                        if abs(adjacent_cell_val - cell_val) <= route_max_abs_diff:
                            seen.add((next_row, next_col))
                            if dfs(next_row, next_col):
                                return True
                            
                return False
            
            return dfs(0, 0)
        
        m = len(heights)
        n = len(heights[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        
        left = 0
        right = max([element for row in heights for element in row]) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            if possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left

This is a great problem for a variety of reasons. It can be somewhat tricky at first though. The idea is that if we can find a path from the top left to the bottom right using a certain amount of effort, then we can certainly find a path that works for any greater amount of effort (i.e., effort + 1, effort + 2, etc.). But can we find a valid path using less effort? That's the real question.

If we let our solution space be the amount of effort required for a valid path, then we can binary search from the minimum possible amount of effort to the maximum possible amount of effort, inclusive. The goal is to find the effort amount for a valid path where any effort less than that would not result in a valid path.

What are the min/max effort bounds? The minimum possible effort is 0 because all of the numbers in the path could be the same. What about the maximum possible effort? That would be the max amount in the matrix minus the smallest amount:

max([element for row in heights for element in row]) - 1

We could also observe the constraint 1 <= heights[i][j] <= 10^6, which means either of the following options would be valid for the problem at hand:

# option 1
left = 0
right = max([element for row in heights for element in row]) - 1

# option 2
left = 0
right = 10 ** 6 - 1

The first option is obviously more costly in some respects, but the second option could result in a maximum boundary that is much larger than what we need. Since binary search is so fast, the second option is really not an issue though.

Finally, it should be noted that a stack-based DFS is also quite effective here to avoid the space overhead required by the call stack to deal with recursion:

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n
        
        def possible(route_max_abs_diff):
            seen = {(0,0)}
            def dfs(start_row, start_col):
                stack = [(start_row, start_col)]
                while stack:
                    row, col = stack.pop()
                    if row == m - 1 and col == n - 1:
                        return True
                    
                    for dr, dc in dirs:
                        next_row, next_col = row + dr, col + dc
                        if valid(next_row, next_col) and (next_row, next_col) not in seen:
                            cell_val = heights[row][col]
                            next_cell_val = heights[next_row][next_col]
                            if abs(next_cell_val - cell_val) <= route_max_abs_diff:
                                seen.add((next_row, next_col))
                                stack.append((next_row, next_col))
                            
                return False
            
            return dfs(0, 0)
        
        m = len(heights)
        n = len(heights[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        
        left = 0
        right = max([element for row in heights for element in row]) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            if possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left

LC 1870. Minimum Speed to Arrive on Time (✓) ★

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the ith train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

For example, if the 1st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2nd train ride at the 2 hour mark.

Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 10⁷ and hour will have at most two digits after the decimal point.

class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        if len(dist) > -(hour // -1):
            return -1
        
        def possible(speed):
            hours_spent = 0
            for i in range(len(dist) - 1):
                distance = dist[i]
                hours_spent += -(distance // -speed)
                if hours_spent > hour:
                    return False
                
            hours_spent += dist[-1] / speed
            return hours_spent <= hour
        
        left = 1
        right = 10 ** 7
        
        while left < right:
            mid = left + (right - left) // 2
            if possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left

This one is a bit wonky to reason about at first. In part because of how the time elapsed is evaluated. It's similar to LC 875. Koko Eating Bananas in that we always take the ceiling of time evaluations, but here the time spent on the last train is not rounded up (we rounded up the time spent on all piles for the Koko eating bananas problem).

When will it be impossible to reach the office on time? It's not when len(dist) > hour, as LeetCode's second example with input dist = [1,3,2], hour = 2.7 shows. However, it will be impossible if len(dist) > ceil(hour). The third example, with input dist = [1,3,2], hour = 1.9 illustrates this, where the earliest the third train cen depart is at the 2 hour mark.

The idea is to conduct a binary search on the range of speeds [min_speed_possible, max_speed_possible] for which we'll be able to make the trip on time (i.e., where the total number of hours spent is less than or equal to hour), where we want to minimize the speed required to make the trip on time. If we can make the trip on time for a given speed, then we can definitely make the trip on time if we increase the speed to speed + 1. We want to determine when making it on time is possible for speed but impossible for any valid speed value less than this. Binary search it is!

What's the minimum possible speed? We're told the speed reported must be a positive integer so we set left = 1. What about the maximum possible speed? We're told that the answer will not exceed 10 ** 7; hence, we set right = 10 ** 7.

LC 1283. Find the Smallest Divisor Given a Threshold (✓)

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor, divide all the array by it, and sum the division's result. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def possible(divisor):
            running_sum = 0
            for num in nums:
                running_sum += -(num // -divisor)
                if running_sum > threshold:
                    return False
            return True
        
        left = 1
        right = max(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            if possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left

This problem is quite similar to LC 875. Koko Eating Bananas. Our solution space is a range of possible divisors, and our goal is to minimize the divisor so that the running sum obtained by dividing each number in nums by divisor (and perforing the subsequent rounding up to the nearest integer) never exceeds threshold.

If we can achieve this task for divisor, then we can definitely achieve the same task by increasing the value of divisor (e.g., divisor + 1). Our goal, then, is to find a divisor such that the task is possible but as soon as we decrease the value of divisor the task becomes impossible.

What would the minimum divisor be for our solution space? We're told it must be a positive integer; hence, we set left = 1. What about the maximum divisor? Since each division result gets rounded up to the nearest integer, the smallest the running sum could be would occur if we chose the divisor to be the maximum value in nums. Then no division would result in a value greater than 1, and since we're told nums.length <= threshold <= 10^6, we let right = max(nums).

LC 410. Split Array Largest Sum (✓) ★★★

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def possible(max_sum):
            num_subarrays = 0
            subarray_sum = 0
            idx = 0
            
            while idx < len(nums):
                if nums[idx] > max_sum:
                    return False
                
                subarray_sum += nums[idx]
                if subarray_sum > max_sum:
                    subarray_sum = nums[idx]
                    num_subarrays += 1
                    if num_subarrays > k:
                        return False
                
                idx += 1
                
            return (num_subarrays + 1) <= k
                
        left = 0
        right = sum(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            if possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left

This problem is excellent and somewhat similar to LC 1231. Divide Chocolate in nature. The tip off that the problem may involve binary searching on a solution space is given by the fact if a subarray sum subarray_sum works as a solution to the problem then increasing the value of subarray_sum will certainly work as well. Our goal is to find a subarray sum that, when decreased at all, results in not being able to fulfill the requirements of the problem. All of this implies we should be able to conduct a binary search on the solution space of minimum subarray sum values.

What would the smallest possible subarray sum value be? Since values of 0 are allowed in nums, we should set left = 0. What about the largest possible subarray sum value? No subarray can have a larger sum than the entire array; hence, we set right = sum(nums).

The harder part for this problem is designing the possible function effectively. The intuition is that we construct the k subarray sums in a greedy fashion, where we keep adding to one of the k subarrays until the given max_sum has been exceeded, at which point we move on to constructing the next subarray sum. If the number of subarrays we must use to accomplish this ever exceeds k, then we issue an early return of false. If, however, we process all values and the total number of subarrays used is less than or equal to k, then we return true because k will always be less than or equal to nums.length per the constraint 1 <= k <= min(50, nums.length); that is, if somehow we've processed all values in nums and have never exceeded max_sum for a subarray sum and the number of subarrays used is much smaller than k, then we can simply distribute the values in the subarrays to fill up the remaining empty subarrays until the total number of subarrays equals k (the sum of the subarrays from which values are borrowed can only decrease due to the constraint 0 <= nums[i] <= 10^6).

LC 1482. Minimum Number of Days to Make m Bouquets★★

Given an integer array bloomDay, an integer m and an integer k.

We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def possible(days):
            bouquets_formed = flower_count = 0
            
            for flower in bloomDay:
                if flower <= days:
                    flower_count += 1
                else:
                    flower_count = 0
                    
                if flower_count == k:
                    bouquets_formed += 1
                    flower_count = 0
                    if bouquets_formed == m:
                        return True

            return False

        # not enough flowers for required number of bouquets        
        if len(bloomDay) < (m * k):
            return -1
        
        left = min(bloomDay)
        right = max(bloomDay)
        while left < right:
            mid = left + (right - left) // 2
            if possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left

As usual, the primary difficulty in this problem is identifying it as having a nice binary search solution. The idea is to binary search on the solution space where the solution space is identified as being binary searchable as follows: if I can form m bouquets in d days, then I can definitely form m bouquets in > d days. We want to find the minimum number for d such that trying to form m bouquets in any fewer days is impossible. We can binary search for that number of days, as shown above.

Greedy (looking for maximum)

Remarks

TBD

def binary_search_on_solution_space_MAXIMUM(arr):
    def possible(threshold):
        # this function is implemented depending on the problem
        return BOOLEAN

    left = MINIMUM_POSSIBLE_ANSWER
    right = MAXIMUM_POSSIBLE_ANSWER + 1 # solution space being binary searched is [left, right) as opposed to [left, right];
                                        # we are trying to find the leftmost insertion point for `threshold`
                                        # in the impossible segment so we can report the position immediately to its left,
                                        # the last position in the possible segment before the impossible segment
                                        # (i.e., the maximum possible value)
    while left < right:
        mid = left + (right - left) // 2
        if not possible(mid):
            right = mid # squeeze `left` as far left as possible in the impossible segment
        else:
            left = mid + 1
    
    return left - 1

Examples

LC 1231. Divide Chocolate (✓) ★★★

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.

You want to share the chocolate with your K friends so you start cutting the chocolate bar into K+1 pieces using K cuts, each piece consists of some consecutive chunks.

Being generous, you will eat the piece with the 8* and give the other pieces to your friends.

Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def possible(min_sweetness):
            pieces = 0
            piece_sweetness = 0
            for chunk_sweetness in sweetness:
                piece_sweetness += chunk_sweetness
                if piece_sweetness >= min_sweetness:
                    pieces += 1
                    piece_sweetness = 0
                    if pieces == k + 1:
                        return True
            return False
        
        left = 1
        right = sum(sweetness) + 1
        
        while left < right:
            mid = left + (right - left) // 2
            if not possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left - 1

This is such a fantastic problem, but it is quite difficult. As usual (for binary search problems on solution spaces anyway), constructing the possible function is where much of the difficulty lies. Our goal is to ensure we can actually come up with k + 1 pieces of chocolate to distribute where each piece meets or exceeds the required min_sweetness threshold. If we can do that, then we're in business. But, of course, as the problem indicates, we want to maximize the minimum sweetness of our own piece of chocolate (since all other pieces distributed must have the same or more sweetness compared to our own).

Hence, we need to binary search on a range of possible minimum sweetness values. What would the smallest possible sweetness be? We're told from the constraint that every chunk of the chocolate has a sweetness of at least 1; hence, we set left = 1. What about the largest possible sweetness? Note that k == 0 is possible, which means there's a possibility where we need to share the chocolate bar with no one — in such a case, we would want to consume all of the sweetness, sum(sweetness). But since we're binary searching a solution space for a maximum value, we need to set right = sum(sweetness) + 1 as opposed to right = sum(sweetness). Why? Because we might miss the maximum value in an off-by-one error otherwise; for example, consider the input sweetness = [5,5], k = 0. The while loop terminates once left == right and right == sum(sweetness), but we return left - 1, which is equal to 10 - 1 == 9 instead of the obviously correct answer of 10.

LC 1552. Magnetic Force Between Two Balls★★

In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def possible(min_mag_force):
            balls_placed = 1
            prev_ball_pos = position[0]
            
            for idx in range(1, len(position)):
                curr_ball_pos = position[idx]
                if curr_ball_pos - prev_ball_pos >= min_mag_force:
                    balls_placed += 1
                    prev_ball_pos = curr_ball_pos
                
                if balls_placed == m:
                    return True
            
            return False
        
        position.sort()
        
        left = 1
        right = (position[-1] - position[0]) + 1
        while left < right:
            mid = left + (right - left) // 2
            if not possible(mid):
                right = mid
            else:
                left = mid + 1
                
        return left - 1

The problem description is one of the hardest things about this problem. But after fighting to understand it, our thinking will gradually start to resemble what's included in the hints and point us to binary search on the solution space as a good strategy:

Hint 1: If you can place balls such that the answer is x,
        then you can do it for y where y < x.

Hint 2: Similarly, if you cannot place balls such that 
        the answer is x then you can do it for y where y > x.

Hint 3: Binary search on the answer and greedily see if it is possible.

This problem is quite similar to LC 1231. Divide Chocolate in many ways, but instead of trying to maximize the sweetness of our least sweet piece of chocolate amongst k friends, we are trying to maximize the magnetic force between the least magnetically attracted pair of balls. The idea is to binary search on possible answer values for the minimum magnetic force required and to maximize that value as much as possible.

Hence, our first task is to build a possible function to determine whether or not the task at hand is possible for some given magnetic force, and we greedily try to determine the possibility; that is, we place a ball whenever the magnetic force provided has been met or exceeded (this ensures the magnetic force provided is, indeed, minimum). All balls placed must have at least min_mag_force magnetic force between them. Our goal is to maximize that value.

The smallest possible magnetic force would be when we have n positions and m == n balls, where the positions are all spaced a single unit apart. That would give us a magnetic force of 1, meaning we should set left = 1. The largest possible magnetic force would be the last position value minus the first position value (assuming the position array to be sorted at that point). Since the right endpoint needs to be included and we're always returning left - 1, we should set right = (position[-1] - position[0]) + 1.

Dynamic programming

Memoization (top-down)

Remarks

TBD

def fn(arr):
    # 1. define a function that will compute/contain
    #   the answer to the problem for any given state
    def dp(STATE):
        # 3. use base cases to make the recurrence relation useful
        if BASE_CASE:
            return 0
        
        if STATE in memo:
            return memo[STATE]
        
        # 2. define a recurrence relation to transition between states
        ans = RECURRENCE_RELATION(STATE)
        memo[STATE] = ans
        return ans

    memo = {}
    return dp(STATE_FOR_WHOLE_INPUT)

Examples

LC 746. Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of i^th 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.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        def dp(step):
            if step in memo:
                return memo[step]
            
            step_cost = min(dp(step - 1) + cost[step - 1], dp(step - 2) + cost[step - 2])
            memo[step] = step_cost
            
            return step_cost
        
        memo = {}
        memo[0] = memo[1] = 0
        return dp(len(cost)) 

Tabulation (bottom-up)

Remarks

TBD

def fn(arr):
    # 1. initialize a table (array, list, etc.) 
    #   to store solutions of subproblems.
    dp_table = INITIALIZE_TABLE()

    # 2. fill the base cases into the table.
    dp_table = FILL_BASE_CASES(dp_table)

    # 3. iterate over the table in a specific order 
    #   to fill in the solutions of larger subproblems.
    for STATE in ORDER_OF_STATES:
        dp_table[STATE] = CALCULATE_STATE_FROM_PREVIOUS_STATES(dp_table, STATE)

    # 4. the answer to the whole problem is now in the table, 
    #   typically at the last entry or a specific position.
    return dp_table[FINAL_STATE_OR_POSITION]

# example usage
arr = [INPUT_DATA]
result = fn(arr)

Examples

TBD

Graphs

DFS (recursive)

Remarks

Assume the nodes are numbered from 0 to n - 1 and the graph is given as an adjacency list. Depending on the problem, you may need to convert the input into an equivalent adjacency list before using the templates.

def fn(graph):
    def dfs(node):
        ans = 0
        # do some logic
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                ans += dfs(neighbor)
        
        return ans

    seen = {START_NODE}
    return dfs(START_NODE)

Examples

LC 547. Number of Provinces (✓)

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the i^th city and the j^th city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def build_adj_list(adj_mat):
            graph = defaultdict(list)
            n = len(adj_mat)
            for node in range(n):
                for neighbor in range(node + 1, n):
                    if isConnected[node][neighbor] == 1:
                        graph[node].append(neighbor)
                        graph[neighbor].append(node)
            return graph
        
        def dfs(node):
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    dfs(neighbor)
        
        graph = build_adj_list(isConnected)
        seen = set()
        provinces = 0
        
        for city in range(len(isConnected)):
            if city not in seen:
                provinces += 1
                seen.add(city)
                dfs(city)
                    
        return provinces

Cities are nodes, connected cities are provinces (i.e., connected components). The idea here is to explore all provinces by starting with each city and seeing how many cities we can explore from that city — every time we have to start a search again from a new city, we increment the number of overall provinces encountered thus far.

LC 200. Number of Islands (✓)

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and grid[row][col] == '1'
        
        def dfs(row, col):
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                neighbor = (next_row, next_col)
                if neighbor not in seen and valid(*neighbor):
                    seen.add(neighbor)
                    dfs(*neighbor)
        
        m = len(grid)
        n = len(grid[0])
        dirs = [(-1,0),(1,0),(0,-1),(0,1)]
        seen = set()
        islands = 0
        
        for i in range(m):
            for j in range(n):
                node = (i, j)
                if node not in seen and grid[i][j] == '1':
                    islands += 1
                    seen.add(node)
                    dfs(*node)
                    
        return islands

Each "island" is a connected component — our job is to count the total number of connected components. The traversal is a fairly standard DFS traversal on a grid-like graph.

LC 1466. Reorder Routes to Make All Paths Lead to the City Zero (✓)

There are n cities numbered from 0 to n-1 and n-1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [a, b] represents a road from city a to b.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It's guaranteed that each city can reach the city 0 after reorder.

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        roads = set()
        def build_adj_list(edge_arr):
            graph = defaultdict(list)
            for node, neighbor in edge_arr:
                roads.add((node, neighbor))
                graph[node].append(neighbor)
                graph[neighbor].append(node)
            return graph
        
        def dfs(node):
            ans = 0
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    if (node, neighbor) in roads:
                        ans += 1
                    ans += dfs(neighbor)
            return ans
                
        graph = build_adj_list(connections)
        seen = {0}
        return dfs(0)

This is a tough one to come up with if you haven't seen it before. The solution approach above is quite clever. The idea is to build an undirected graph in the form of an adjacency list and then to conduct a DFS from node 0, which means every edge we encounter is necessarily leading away from 0; hence, if that edge appeared in the original road configuration, roads, then we know that road's direction must be changed so that it faces toward node 0 instead of away.

LC 841. Keys and Rooms (✓)

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(node):
            for neighbor in rooms[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    dfs(neighbor)
    
        seen = {0}
        dfs(0)
        return len(seen) == len(rooms)

It's quite nice that the given input, rooms, is already in the form of an adjacency list (as an index array). The key insight is to realize that we can use our seen set to determine whether or not all rooms have been visited after conducting a DFS from node 0 (i.e., room 0); that is, if seen is the same length as rooms after the DFS from node 0, then we can say it's possible to visit all rooms (otherwise it's not).

LC 1971. Find if Path Exists in Graph (✓)

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [u_i, v_i] denotes a bi-directional edge between vertex u_i and vertex v_i. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex start to vertex end.

Given edges and the integers n, start, and end, return true if there is a valid path from start to end, or false otherwise.

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        def build_adj_list(edge_arr):
            graph = defaultdict(list)
            for node, neighbor in edge_arr:
                graph[node].append(neighbor)
                graph[neighbor].append(node)
            return graph
        
        def dfs(node):
            if node == destination:
                return True
            
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    if dfs(neighbor):
                        return True
            return False
        
        graph = build_adj_list(edges)
        seen = {source}
        return dfs(source)

The solution above is a direct application of a DFS traversal. The hardest part is arguably coming up with an effective way of writing the dfs function. It's better not to rely on a nonlocal variable unless we really need to. The idea is that we should stop searching if we encounter a node whose value is equal to the destination. If that is not the case, then we try to explore further. If our DFS comes up empty, then we return False, and that will propagate back up the recursion chain.

LC 323. Number of Connected Components in an Undirected Graph (✓)

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [a_i, b_i] indicates that there is an edge between a_i and b_i in the graph.

Return the number of connected components in the graph.

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        def build_adj_list(edge_arr):
            graph = defaultdict(list)
            for node, neighbor in edge_arr:
                graph[node].append(neighbor)
                graph[neighbor].append(node)
            return graph
        
        def dfs(node):
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    dfs(neighbor)

        graph = build_adj_list(edges)
        seen = set()
        cc = 0
        
        for node in range(n):
            if node not in seen:
                cc += 1
                seen.add(node)
                dfs(node)
        
        return cc

Counting the number of connected components in a graph via DFS traversal is a very common task. Sometimes the nature of the connected components may be obfuscated at first (i.e., we have to come up with a way to first model the connections and then determine the number of connected components), but that is not the case here.

One thing worth noting in the solution above is how we deftly take care of the case where a node is not represented in the original edge list we're provided. We simply increment the count of the number of connected components, cc, as soon as we encounter a node we have not seen before, and we do this for all n nodes. For nodes that are not connected to any other nodes, are dfs function effectively does not execute.

LC 695. Max Area of Island (✓)

Given a non-empty 2D array grid of 0's and 1's, 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.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and grid[row][col] == 1
        
        def dfs(row, col):
            connected_area = 0
            
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                next_node = (next_row, next_col)
                if valid(*next_node) and next_node not in seen:
                    seen.add(next_node)
                    connected_area += 1 + dfs(*next_node)
            
            return connected_area
                
        
        m = len(grid)
        n = len(grid[0])
        dirs = [(-1,0),(1,0),(0,1),(0,-1)]
        seen = set()
        max_area = 0
        
        for i in range(m):
            for j in range(n):
                if (i, j) not in seen and grid[i][j] == 1:
                    seen.add((i, j))
                    max_area = max(max_area, 1 + dfs(i, j))
                    
        return max_area

The idea here is to basically find the largest connected component.

LC 2368. Reachable Nodes With Restrictions (✓)

There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

You are given a 2D integer array edges of length n - 1 where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree. You are also given an integer array restricted which represents restricted nodes.

Return the maximum number of nodes you can reach from node 0 without visiting a restricted node.

Note that node 0 will not be a restricted node.

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        restricted = set(restricted)
        def build_adj_list(edge_arr):
            graph = defaultdict(list)
            for node, neighbor in edge_arr:
                if node not in restricted and neighbor not in restricted:
                    graph[node].append(neighbor)
                    graph[neighbor].append(node)
            return graph
        
        def dfs(node):
            for neighbor in graph[node]:
                if neighbor not in seen and neighbor not in restricted:
                    seen.add(neighbor)
                    dfs(neighbor)
            
        graph = build_adj_list(edges)
        seen = {0}
        dfs(0)
        return len(seen)

The idea behind the solution above is to start by ensuring our graph only has valid nodes. This means getting rid of all edges that contain one (or both) nodes from the restricted list, which we start by "setifying" in order to make it possible to have $O(1)$ lookups.

It's worth reflecting on why it behooves us to get rid of an edge when one of its nodes is from the restricted set. If the node in the restricted is the source, then there's no way to get to its destination. If the restricted node is the destination, then we will not go there from the source. Whatever the case, it is a waste of time and space to consider edges that have one (or both) nodes from the restricted set.

At the end, the number of nodes reached from 0 is the length of the set seen, which is why we return len(seen). We could just as well kept track of the number of visited nodes by just using the dfs function itself:

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        restricted = set(restricted)
        def build_adj_list(edge_arr):
            graph = defaultdict(list)
            for node, neighbor in edge_arr:
                if node not in restricted and neighbor not in restricted:
                    graph[node].append(neighbor)
                    graph[neighbor].append(node)
            return graph
        
        def dfs(node):
            ans = 0
            
            for neighbor in graph[node]:
                if neighbor not in seen and neighbor not in restricted:
                    seen.add(neighbor)
                    ans +=  1 + dfs(neighbor)
                    
            return ans
            
        graph = build_adj_list(edges)
        seen = {0}
        return dfs(0) + 1

LC 1020. Number of Enclaves (✓) ★★★

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and grid[row][col] == 1
        
        def process_perimeter(mat):
            first_row = 0
            last_row = m - 1
            first_col = 0
            last_col = n - 1
            boundary_lands = set()
            
            for row in [ first_row, last_row ]:
                for col in range(n):
                    if mat[row][col] == 1:
                        boundary_lands.add((row, col))
                        
            for col in [ first_col, last_col ]:
                for row in range(1, m - 1):
                    if mat[row][col] == 1:
                        boundary_lands.add((row, col))
            
            return boundary_lands
                    
        def dfs(row, col):
            ans = 0
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                if valid(next_row, next_col) and (next_row, next_col) not in seen:
                    seen.add((next_row, next_col))
                    ans += 1 + dfs(next_row, next_col)
            return ans
            
        m = len(grid)
        n = len(grid[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        seen = set()
        enclaves = 0
        boundary_lands = process_perimeter(grid)
        
        for boundary_land in boundary_lands:
            seen.add(boundary_land)
            dfs(*boundary_land)
            
        for i in range(m):
            for j in range(n):
                if (i, j) not in seen and grid[i][j] == 1:
                    seen.add((i, j))
                    enclaves += 1 + dfs(i, j)
        
        return enclaves

The solution above could almost certainly be improved, but it captures the core idea for almost any effective solution to this problem — we need to pre-process to identify all land cells that reside on the boundary. A DFS from each of those cells should be used to identify invalid land cells. There are a few ways of doing this — we could mutate the input grid by letting our DFS mark all boundary land cells and invalid connected land cells with 0 or some other value. Then we simply need to count the number of cells with 1 in them. The following solution is much more optimized for this kind of approach:

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and grid[row][col] == 1
        
        def process_perimeter(mat):
            first_row = 0
            last_row = m - 1
            first_col = 0
            last_col = n - 1
            
            for row in [ first_row, last_row ]:
                for col in range(n):
                    if mat[row][col] == 1:
                        dfs(row, col)
                        
            for col in [ first_col, last_col ]:
                for row in range(1, m - 1):
                    if mat[row][col] == 1:
                        dfs(row, col)
            
        def dfs(row, col):
            grid[row][col] = 0
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                if valid(next_row, next_col):
                    dfs(next_row, next_col)
            
        m = len(grid)
        n = len(grid[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        process_perimeter(grid)
        enclaves = 0
            
        for i in range(m):
            for j in range(n):
                enclaves += grid[i][j]
                
        return enclaves

LC 2192. All Ancestors of a Node in a Directed Acyclic Graph (✓)

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [from_i, to_i] denotes that there is a unidirectional edge from from_i to to_i in the graph.

Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        def build_rev_adj_list(edge_arr):
            graph = defaultdict(list)
            for node, neighbor in edge_arr:
                graph[neighbor].append(node)
            return graph
        
        def dfs(node, visited):
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    dfs(neighbor, visited)
            return visited
        
        graph = build_rev_adj_list(edges)
        return [ sorted(list(dfs(node, set()))) for node in range(n) ]

This is a fun one. The key idea is to invert or reverse the edge directions and then perform a DFS from each node, 0 through n - 1, inclusive, to determine what the ancestors are for each node. Why does this work? Because the ancestors of a target node are whatever nodes have edges that lead to the target node; hence, executing a DFS from the target node once edges have been inverted gives us all ancestral nodes for the target node.

LC 990. Satisfiability of Equality Equations (✓) ★★★

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        def build_graph(edges):
            graph = defaultdict(list)
            for equation in edges:
                if equation[1] == '=':
                    node = equation[0]
                    neighbor = equation[3]
                    graph[node].append(neighbor)
                    graph[neighbor].append(node)
            return graph
        
        def dfs(node, label):
            if label_lookup[node] == -1:
                label_lookup[node] = label
                for neighbor in graph[node]:
                    dfs(neighbor, label)
            
        graph = build_graph(equations)
        label_lookup = { chr(i): -1 for i in range(97, 122 + 1) }
        for char in 'abcdefghijklmnopqrstuvwxyz':
            dfs(char, ord(char))
            
        for equation in equations:
            if equation[1] == '!':
                if label_lookup[equation[0]] == label_lookup[equation[3]]:
                    return False
                
        return True

Equation problems that require being interpreted as graphs are never very intuitive and always require some creativity. The solution editorial for this problem is quite good and highlights one slick way of approach this problem with DFS as the underlying mechanism for driving the solution logic.

The key idea is to treat each possible variable (a through z) as a node and then to use the provided equations where == is the comparison to essentially label all equal variables in the same way (i.e., it's like we're assigning a number or color to each node in a connected component). Once this has been done, we process all equations where != is the comparison operator — if the nodes that cannot be equal are in separate components (i.e., they have different labels), then we are fine; if, however, two nodes cannot be equal but they share the same label, then this means they must also be equal to other (a contradiction).

DFS (iterative)

Remarks

def fn(graph):
    stack = [START_NODE]
    seen = {START_NODE}
    ans = 0

    while stack:
        node = stack.pop()
        # do some logic
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                stack.append(neighbor)
    
    return ans

Examples

TBD

BFS

Remarks

from collections import deque

def fn(graph):
    queue = deque([START_NODE])
    seen = {START_NODE}
    ans = 0

    while queue:
        node = queue.popleft()
        # do some logic
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    
    return ans

Examples

LC 1091. Shortest Path in Binary Matrix (✓)

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        def valid(row, col):
            return 0 <= row < n and 0 <= col < n and grid[row][col] == 0
        
        dirs = [(1,0),(1,1),(1,-1),(-1,0),(-1,1),(-1,-1),(0,-1),(0,1)]
        n = len(grid)
        seen = {(0,0)}
        
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            return -1
        
        queue = deque([(0,0,1)])
        while queue:
            row, col, path_length = queue.popleft()
            if row == n - 1 and col == n - 1:
                return path_length
            
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                next_node = (next_row, next_col)
                if valid(*next_node) and next_node not in seen:
                    queue.append((*next_node, path_length + 1))
                    seen.add(next_node)
                    
        return -1

It's fairly conventional in BFS solutions for graphs to encode with each node additional information like the current level for that node or some other kind of stateful data. We do not need to encode anything other than each node's position in the seen set because whenever we encounter a node it will be in the fewest steps possible (i.e., the trademark of BFS solutions ... finding shortest paths).

LC 863. All Nodes Distance K in Binary Tree (✓)

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        def build_parent_lookup(node, parent = None):
            if not node:
                return
            
            parent_lookup[node] = parent
            build_parent_lookup(node.left, node)
            build_parent_lookup(node.right, node)
            
        parent_lookup = dict()
        build_parent_lookup(root)
        seen = {target}
        
        queue = deque([target])
        for _ in range(k):
            num_nodes_this_level = len(queue)
            for _ in range(num_nodes_this_level):
                node = queue.popleft()
                for neighbor in [node.left, node.right, parent_lookup[node]]:
                    if neighbor and neighbor not in seen:
                        seen.add(neighbor)
                        queue.append(neighbor)
        
        return [ node.val for node in queue ]

The key in the solution above is to recognize that a BFS traversal will give us exactly what we want if we have some way to reference each node's parent node. The build_parent_lookup function, which uses DFS to build a hashmap lookup for each node's parent node, gives us this. Much of the rest of the problem then becomes a standard BFS traversal.

LC 542. 01 Matrix (✓)

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and mat[row][col] == 1
        
        m = len(mat)
        n = len(mat[0])
        res = [[0] * n for _ in range(m)]
        dirs = [(-1,0),(1,0),(0,1),(0,-1)]
        seen = set()
        queue = deque()
        
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    seen.add((i, j))
                    queue.append((i, j, 0))
                    
        while queue:
            row, col, dist = queue.popleft()
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                next_node = (next_row, next_col)
                if valid(*next_node) and next_node not in seen:
                    res[next_row][next_col] = dist + 1
                    seen.add(next_node)
                    queue.append((*next_node, dist + 1))
        
        return res

The solution above takes advantage of a so-called multi-source BFS (i.e., a BFS traversal with multiple starting sources). The solution also takes advantage of the fact that cells with a value of 0 do not need to be updated; hence, our BFS can start from all nodes with a value of 0 and explore outwards, updating non-zero nodes (i.e., just nodes with value 1 for this problem) with the distance so far from a node with value 0. Our intuition tells us to start from the nodes with value 1, but it's much easier to start from the nodes with value 0.

Additionally, in the valid function above, the condition and mat[row][col] == 1 is not necessary since all nodes with value 0 are added to the seen set before exploring outwards, which means all subsequent nodes we'll explore that are both valid and not in seen will have a non-zero value (i.e., 1 for this problem). This conditional of the valid function is only kept for the sake of clarity, but it's worth noting that it's not necessary here.

LC 1293. Shortest Path in a Grid with Obstacles Elimination (✓) ★★

Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        # ensures the next node to be visited is in bounds
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n
        
        m = len(grid)
        n = len(grid[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        seen = {(0,0,k)}
        queue = deque([(0,0,k,0)])
        
        while queue:
            row, col, rem, steps = queue.popleft()

            # only valid nodes exist in the queue
            if row == m - 1 and col == n - 1:
                return steps
            
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                next_node = (next_row, next_col)
                
                if valid(*next_node):
                    next_val = grid[next_row][next_col]
                    
                    # if the next value is not an obstacle, then proceed with visits as normal
                    if next_val == 0:
                        if (*next_node, rem) not in seen:
                            seen.add((*next_node, rem))
                            queue.append((*next_node, rem, steps + 1))
                    # the next value is an obstacle: can we still remove obstacles? if so, proceed with visits
                    else:
                        if rem > 0 and (*next_node, rem - 1) not in seen:
                            seen.add((*next_node, rem - 1))
                            queue.append((*next_node, rem - 1, steps + 1))
        
        return -1

This is an excellent problem for thinking through how a node's state should be recorded in the seen set; that is, the majority of BFS and DFS traversals on matrix graphs simply record a node's position (i.e., row and column) because the node's position fully describes the state we do not want to visit again. But for some problems, like this one, it's helpful to record more information than just a node's position. Specifically, the state we do not want to visit more than once is a node's position in addition to the number of remaining obstacles we can move.

Thinking about using the seen set to record states we do not want to visit multiple times is much more accurate and reflective of our actual goal — only perform computation when absolutely necessary.

LC 1129. Shortest Path with Alternating Colors (✓) ★★

Consider a directed graph, with nodes labelled 0, 1, ..., n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn't exist).

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        def build_graph(edge_arr):
            graph = defaultdict(list)
            for node, neighbor in edge_arr:
                graph[node].append(neighbor)
            return graph
        
        RED_GRAPH = build_graph(redEdges)
        BLUE_GRAPH = build_graph(blueEdges)
        RED = 1
        BLUE = 0
        
        ans = [float('inf')] * n
        seen = {(0,RED), (0,BLUE)}
        queue = deque([(0,RED,0),(0,BLUE,0)])
            
        while queue:
            node, color, steps = queue.popleft()
            ans[node] = min(ans[node], steps)
            alt_color = 1 - color
            graph = RED_GRAPH if alt_color == 1 else BLUE_GRAPH
            for neighbor in graph[node]:
                if (neighbor, alt_color) not in seen:
                    seen.add((neighbor, alt_color))
                    queue.append((neighbor, alt_color, steps + 1))
                    
        return [ val if val != float('inf') else -1 for val in ans ]

This is such a great problem in so many ways. The idea is to execute a "semi-multi-source" BFS, where we start with node 0 as if it's red as well as if it's blue. Then we expand outwards.

We also take advantage of a nice numerical trick: 1 - 1 == 0, and 1 - 0 == 1. This allows us to effectively (and efficiently) alternate between colors.

LC 1926. Nearest Exit from Entrance in Maze (✓)

You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrance_row, entrance_col] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and maze[row][col] == '.'
        
        m = len(maze)
        n = len(maze[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        start_node = tuple(entrance)
        seen = {start_node}
        queue = deque([(*start_node, 0)])
        
        exit_rows = {0, m - 1}
        exit_cols = {0, n - 1}
        
        while queue:
            row, col, moves = queue.popleft()
            if row in exit_rows or col in exit_cols:
                if row != start_node[0] or col != start_node[1]:
                    return moves
            
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                next_node = (next_row, next_col)
                if valid(*next_node) and next_node not in seen:
                    seen.add(next_node)
                    queue.append((*next_node, moves + 1))
                    
        return -1

There are several variables to initialize before the proper traversal and that is okay.

LC 909. Snakes and Ladders (✓)

On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows:

You start on square 1 of the board (which is always in the last row and first column). Each move, starting from square x, consists of the following:

You choose a destination square S with number x+1, x+2, x+3, x+4, x+5, or x+6, provided this number is <= N*N.

(This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations, regardless of the size of the board.)

If S has a snake or ladder, you move to the destination of that snake or ladder. Otherwise, you move to S.

A board square on row r and column c has a "snake or ladder" if board[r][c] != -1. The destination of that snake or ladder is board[r][c].

Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving. (For example, if the board is [[4,-1],[-1,3]], and on the first move your destination square is 2, then you finish your first move at 3, because you do not continue moving to 4.)

Return the least number of moves required to reach square N*N. If it is not possible, return -1.

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        def valid(row, col):
            return 0 <= row < n and 0 <= col < n
        
        def label_to_cell(num):
            row = (num - 1) // n
            col = (num - 1) % n
            if row % 2 == 1:
                col = (n - 1) - col
            return [(n - 1) - row, col]
        
        n = len(board)
        seen = {1}
        queue = deque([(1,0)])
        while queue:
            label, moves = queue.popleft()
            
            if label == n ** 2:
                return moves
            
            for next_label in range(label + 1, min(label + 6, n ** 2) + 1):
                row, col = label_to_cell(next_label)
                if valid(row, col) and next_label not in seen:
                    seen.add(next_label)
                    if board[row][col] != -1:
                        queue.append((board[row][col], moves + 1))
                    else:
                        queue.append((next_label, moves + 1))
                        
        return -1

This is a rough one, mostly because of the convoluted problem description. The trickiest part is coming up with a performant way of converting from label to cell:

def label_to_cell(num):
    row = (num - 1) // n
    col = (num - 1) % n
    if row % 2 == 1:
        col = (n - 1) - col
    return [(n - 1) - row, col]

Coming up with the function above takes some patience and experimentation at first. Another challenge is the mental change from generally recording in the seen set the position of the node we're processing; in this case, we only care about what node labels we've previously seen. As we explore neighbors, we add each label to the seen set, but the items we add to the queue will depend on whether or not we've encounter a snake or ladder.

LC 1376. Time Needed to Inform All Employees (✓) ★

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the ith employee, manager[headID] = -1. Also, it is guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.

The ith employee needs informTime[i] minutes to inform all of his direct subordinates (i.e., After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # treat the graph as directed (from managers to subordinates)
        def build_adj_list(manager_arr):
            graph = defaultdict(list)
            for emp in range(n):
                graph[manager_arr[emp]].append(emp)
            del graph[-1]
            return graph
        
        graph = build_adj_list(manager)
        minutes_needed = informTime[headID]
        seen = {headID}
        queue = deque([(headID, 0)]) # unique base case
        
        while queue:
            manager, time_so_far = queue.popleft()
            for subordinate in graph[manager]:
                minutes_needed = max(minutes_needed, time_so_far + informTime[manager])
                seen.add(subordinate)
                queue.append((subordinate, time_so_far + informTime[manager]))
                
        return minutes_needed

This seems like a mostly natural BFS problem, but one of the tricks involves effectively handling how queue is initialized. It's tempting to do queue = deque([(headID, informTime[headID])]), but this would be wrong when subordinates exist because we almost certainly end up overcounting (this is because time_so_far + informTime[manager] is the time so far for each subordinate node of a manager).

Sometimes BFS problems can be tricky because of how we handle queue initialization. This is definitely one of those problems.

LC 994. Rotting Oranges (✓) ★★

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.

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and grid[row][col] == 1
        
        def find_fresh_and_rotten(mat):
            fresh = 0
            rotten = set()
            for i in range(m):
                for j in range(n):
                    if mat[i][j] == 1:
                        fresh += 1
                    elif mat[i][j] == 2:
                        rotten.add((i,j))
            return fresh, rotten
        
        m = len(grid)
        n = len(grid[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        fresh, seen = find_fresh_and_rotten(grid)
        
        if fresh == 0:
            return 0
        
        queue = deque([(*rotten, 0) for rotten in seen])
        while queue:
            row, col, mins = queue.popleft()
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                if valid(next_row, next_col) and (next_row, next_col) not in seen:
                    seen.add((next_row, next_col))
                    fresh -= 1
                    if fresh == 0:
                        return mins + 1
                    queue.append((next_row, next_col, mins + 1))
                    
        return -1

The solution editorial makes it clear there are several ways of going about solving this problem. The approach above is arguably more straightforward than the solutions provided in the editorial though.

The key idea is to pre-process the grid in order to find the total number of fresh oranges as well as where the rotten oranges are located (if no fresh oranges are found, then immediately return 0) — we then execute a mult-source BFS from each rotten orange, and we keep track of how many fresh oranges remain as each cell is processed (if the counter ever reaches 0, then we immediately return the number of minutes required at that point).

Implicit

Remarks

TBD

TBD

Examples

LC 752. Open the Lock (✓)

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def neighbors(node):
            ans = []
            for i in range(4):
                num = int(node[i])
                for change in [-1, 1]:
                    x = (num + change) % 10
                    ans.append(node[:i] + str(x) + node[i + 1:])
            
            return ans

        if "0000" in deadends:
            return -1
        
        queue = deque([("0000", 0)])
        seen = set(deadends)
        seen.add("0000")
        
        while queue:
            node, steps = queue.popleft()
            if node == target:
                return steps
        
            for neighbor in neighbors(node):
                if neighbor not in seen:
                    seen.add(neighbor)
                    queue.append((neighbor, steps + 1))
        
        return -1

The solution above is quite Pythonic. The key insight in this problem is to view each combination as a node or state we want to visit once. A node's neighbors will be all nodes one letter change away. The trickier part of the problem becomes making the string manipulations effectively and actually generating the neighbors. The neighbors function above does this effectively even though (num + change) % 10 seems odd at first because of how Python's modulus operator % operates — its definition is floored, which means, for example, that -1 % 10 == 9. In general, floored division means the remainder procured by the modulus operator will always have the same sign as the divisor. We could change (num + change) % 10 to (num + change + 10) % 10 to explicitly avoid this confusion if we wanted to.

Another approach is much less clean but also still effective in achieving the desired end result:

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def dial_up_down(str_num):
            num = int(str_num)
            if 1 <= num <= 8:
                return str(num - 1), str(num + 1)
            else:
                if num == 0:
                    return '9', '1'
                else:
                    return '8', '0'
        
        seen = {'0000'}
        deadends = set(deadends)
        queue = deque([('0000', 0)])
        
        if target in deadends or '0000' in deadends:
            return -1
        
        while queue:
            combination, moves = queue.popleft()
            if combination == target:
                return moves
            
            candidates = []
            combination = list(combination)
            for i in range(len(combination)):
                char = combination[i]
                up, down = dial_up_down(char)
                new_candidate_up = combination[:]
                new_candidate_up[i] = up
                new_candidate_down = combination[:]
                new_candidate_down[i] = down
                candidates.append("".join(new_candidate_up))
                candidates.append("".join(new_candidate_down))
                
            for candidate in candidates:
                if candidate not in seen and candidate not in deadends:
                    seen.add(candidate)
                    queue.append((candidate, moves + 1))
                    
        return -1

LC 399. Evaluate Division (✓)

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] represent the equation A_i / B_i = values[i]. Each A_i or B_i is a string that represents a single variable.

You are also given some queries, where queries[j] = [C_j, D_j] represents the j^th query where you must find the answer for C_j / D_j = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        def build_graph(edges, weights):
            graph = defaultdict(dict)
            for i in range(len(edges)):
                num, denom = edges[i]
                weight = weights[i]
                graph[num][denom] = weight
                graph[denom][num] = 1 / weight
            return graph
        
        def answer_query(query):
            num, denom = query
            if num not in graph or denom not in graph:
                return -1
            
            seen = {num}
            queue = deque([(num, 1)])
            while queue:
                node, result = queue.popleft()
                if node == denom:
                    return result
                
                for neighbor in graph[node]:
                    if neighbor not in seen:
                        seen.add(neighbor)
                        queue.append((neighbor, result * graph[node][neighbor]))
                        
            return -1
            
        graph = build_graph(equations, values)
        return [ answer_query(query) for query in queries ]

This is kind of a wild problem. It takes a lot of imagination to view it as a graph problem at first. The idea is that each element of a quotient (i.e., numerator and denominator) is a node. An edge is the ratio of numerator to denominator as well as denominator to numerator (we view the equations provided as an edge list of undirected edges). Each edge is weighted — the quotient value is the weight.

For example, if we're given that $\frac{a}{b}=2$ and $\frac{b}{c}=3$ , then we can model the process of trying to solve for $\frac{a}{c}$ as a graph traversal problem:

The idea is to start at node a, the numerator, and try to eventually reach node c, the denominator, by traveling along the weighted edges. As the diagram above shows, we should have $\frac{a}{c} = 6$ , which we get by starting from a with a product of $1$ and then multiplying it by the edge weights as we go: $1 \times 2\times 3 = 6$ .

The BFS solution above is rather clean, but the DFS solution is arguably more intuitive in a sense (even though it may be slightly harder to code) because we're basically trying to determine whether or not there exists a path from the numerator to the denominator:

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        def build_graph(edges, weights):
            graph = defaultdict(dict)
            for i in range(len(edges)):
                num, denom = edges[i]
                weight = weights[i]
                graph[num][denom] = weight
                graph[denom][num] = 1 / weight
            return graph
        
        def answer_query(query):
            num, denom = query
            if num not in graph or denom not in graph:
                return -1
            
            seen = {num}
            def dfs(node):
                if node == denom:
                    return 1
                
                for neighbor in graph[node]:
                    if neighbor not in seen:
                        seen.add(neighbor)
                        result = dfs(neighbor)
                        if result != -1:
                            return result * graph[node][neighbor]
                
                return -1
            
            return dfs(num)
            
        graph = build_graph(equations, values)
        return [ answer_query(query) for query in queries ]

LC 433. Minimum Genetic Mutation (✓)

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        seen = {startGene}
        bank = set(bank)
        queue = deque([(startGene, 0)])
        while queue:
            node, mutations = queue.popleft()
            if node == endGene:
                return mutations
            
            for char in 'ACGT':
                for i in range(8):
                    neighbor = node[:i] + char + node[i+1:]
                    if neighbor not in seen and neighbor in bank:
                        seen.add(neighbor)
                        queue.append((neighbor, mutations + 1))
                    
        return -1

It's easy to over-complicate this problem. The core idea is that each gene is a node and nodes are connected by single-difference mutations. The solution above uses the if neighbor not in seen to its advantage to effectively bypass logic for avoiding the consideration of the same gene more than once. That is, for char in 'ACGT' means char will obviously take on values 'A', 'C', 'G', and 'T' even though the character for the current gene in this place is one of these characters. But since the the current node has already been seen, we will not continue a search from it. It's a clever way to simplify the rest of the logic. The 8 in for i in range(8) is due to the fact that each gene string is 8 characters long.

Here's a longer and more complicated (not recommended) solution:

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        def get_neighbors(node):
            neighbors = []
            for i in range(8):
                for j in range(3):
                    char_mutation = code_to_char[(char_to_code[node[i]] + (j + 1)) % 4]
                    gene_mutation = node[:i] + char_mutation + node[i+1:]
                    if gene_mutation in bank:
                        neighbors.append(gene_mutation)
            return neighbors
        
        char_to_code = { 'A': 0, 'C': 1, 'G': 2, 'T': 3 }
        code_to_char = { 0: 'A', 1: 'C', 2: 'G', 3: 'T' }
        bank = set(bank)
        
        seen = {startGene}
        queue = deque([(startGene, 0)])
        while queue:
            node, mutations = queue.popleft()
            if node == endGene:
                return mutations
            
            for neighbor in get_neighbors(node):
                if neighbor not in seen:
                    seen.add(neighbor)
                    queue.append((neighbor, mutations + 1))
                    
        return -1

LC 1306. Jump Game III (✓)

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        def valid(idx):
            return 0 <= idx < n
        
        n = len(arr)
        seen = {start}
        queue = deque([start])
        
        while queue:
            idx = queue.popleft()
            
            if arr[idx] == 0:
                return True
            
            for neighbor in [ idx - arr[idx], idx + arr[idx] ]:
                if valid(neighbor) and neighbor not in seen:
                    seen.add(neighbor)
                    queue.append(neighbor)
                    
        return False

The BFS solution above is a natural solution for this disguised graph problem.

LC 2101. Detonate the Maximum Bombs (✓)

You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [x_i, y_i, r_i]. x_i and y_i denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas r_i denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        def build_adj_list(edges):
            graph = defaultdict(list)
            n = len(edges)
            for i in range(n):
                x1, y1, r1 = bombs[i]
                for j in range(i + 1, n):
                    x2, y2, r2 = bombs[j]
                    dist = ((x2-x1) ** 2 + (y2-y1) ** 2) ** (1/2)
                    if r1 >= dist:
                        graph[i].append(j)
                    if r2 >= dist:
                        graph[j].append(i)
            
            return graph
        
        def bombs_detonated(bomb):
            seen = {bomb}
            queue = deque([(bomb)])
            count = 0
            while queue:
                node = queue.popleft()
                count += 1
                for neighbor in graph[node]:
                    if neighbor not in seen:
                        seen.add(neighbor)
                        queue.append(neighbor)
            return count
            
        graph = build_adj_list(bombs)
        return max(bombs_detonated(bomb) for bomb in range(len(bombs)))

Time to remember what the distance between two points is! But for real. The idea here is that each bomb is a node and bomb A is connected to bomb B if bomb B lies within bomb A's blast radius (and vice-verse, indicating we should use a directed graph to model this problem). We then explore what happens when any single bomb is detonated — how many bombs in total will be detonated after any one bomb is detonated? We want the maximum.

We can use a BFS or DFS to answer this question here. The approach above uses a BFS. One small edge case to be aware of is that nothing prevents two bombs from being placed at the exact same location and with the same radius; that is, the entries in bombs will be identical, but they will need to be treated separately. Hence, when we build our graph, we should use each bomb's index as its node label as opposed to a tuple for the bomb. Just because a tuple is immutable/hashable does not mean we should use it in such a way; additionally, if we use tuples for each bomb, then we fail to take into account when two bombs can be in the same location and with the same radius.

General

Remarks

TBD

Examples

LC 1557. Minimum Number of Vertices to Reach All Nodes (✓)

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from_i, to_i] represents a directed edge from node from_i to node to_i.

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        indegrees = [0] * n
        for _, destination in edges:
            indegrees[destination] += 1
            
        return [ node for node in range(n) if indegrees[node] == 0 ]

Arguably the hardest part of this problem is actually understanding what it's really asking for:

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists. Notice that you can return the vertices in any order.

What does this really mean? It essentially means that all nodes that have no inbound neighboring nodes will comprise the smallest set of vertices we seek. How? Because these nodes only have outbound connections to all other nodes (they are not reachable from any other nodes). Hence, the problem boils down to finding all nodes that have an indegree of 0, as demonstrated above.

LC 997. Find the Town Judge (✓) ★★

In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if len(trust) < n - 1:
            return -1
        
        def sum_in_out_degrees(edges):
            degree_sum = defaultdict(int)
            for truster, trusted in edges:
                degree_sum[truster] -= 1    # subtract 1 for outdegree
                degree_sum[trusted] += 1    # add 1 for indegree
            return degree_sum
        
        lookup = sum_in_out_degrees(trust)
        for person in range(1, n + 1):
            if lookup[person] == n - 1:
                return person
        return -1

This is a great problem where you can really get creative in how you solve it. The key insight is to recognize that the town judge, if that person exists, must have an indegree of n - 1 and an outdegree of 0. We can go about computing that in a few different ways, but the approach above is slick in that it tracks the degree total for each person, where 1 is added if the person is being trusted or subtracts 1 if the person is doing the trusting.

The result is that the town judge will have a degree total of n - 1 (i.e., this person is being trusted n - 1 times while having never trusted anyone), but this cannot be possible for anyone else. A longer, slightly less efficient approach (albeit in the same complexity classes in terms of time and space) is to separately maintain the indegree and outdegree counts:

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if len(trust) < n - 1:
            return -1
        
        def degree_lookup(edges):
            lookup = defaultdict(lambda: [0,0]) # [indegree, outdegree]
            for truster, trusted in edges:
                lookup[truster][1] += 1
                lookup[trusted][0] += 1
            return lookup
        
        lookup = degree_lookup(trust)
        for person in range(1, n + 1):
            if lookup[person][0] == n - 1 and lookup[person][1] == 0:
                return person
            
        return -1

LC 1615. Maximal Network Rank (✓)

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [a_i, b_i] indicates that there is a bidirectional road between cities a_i and b_i.

The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        def build_adj_list(edges):
            graph = defaultdict(set)
            for node, neighbor in edges:
                graph[node].add(neighbor)
                graph[neighbor].add(node)
            return graph
        
        graph = build_adj_list(roads)
        max_rank = 0
        
        for city in range(n):
            city_rank = len(graph[city])
            for next_city in range(city + 1, n):
                next_city_rank = len(graph[next_city])
                rank = city_rank + next_city_rank
                if city in graph[next_city]:
                    rank -= 1
                max_rank = max(max_rank, rank)
            
        return max_rank

It's easy to get tripped up in this problem and immediately spring for a DFS, where we then count the total number of outdegrees for neighboring nodes (minus 1 to not overcount the shared outdegree to each other), but the fatal flaw here is highlighted in the problem's third example on LeetCode:

All the cities do not have to be connected.

This means the approach remarked on above will work for cities that are connected, but it will not work for cities that are not connected. If cities are not connected, then we'll want the sum of the outdegrees for two cities and we won't have to subtract 1 because no edge will be shared between them. Point being: there's not a nice way of dealing with this problem other than iterating through all pairs of points to see what the maximal combination is. The rank of each pair is the sum of their outdegrees and then we subtract 1 if they happen to be neighbors (this is why the adjacency representation of the graph uses sets for neighbors instead of lists).

LC 463. Island Perimeter (✓) ★★

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        WATER = 0
        LAND = 1
        
        rows = len(grid)
        cols = len(grid[0])
        island_perimeter = 0
        ISLAND_FOUND = False
        
        for row in range(rows):
            ROW_ISLAND = False
            for col in range(cols):
                if grid[row][col] == LAND:
                    contribution = 4
                    ISLAND_FOUND = True
                    ROW_ISLAND = True
                    if row > 0 and grid[row - 1][col] == LAND:
                        contribution -= 2
                        
                    if col > 0 and grid[row][col - 1] == LAND:
                        contribution -= 2
                        
                    island_perimeter += contribution
                    
            if ISLAND_FOUND and not ROW_ISLAND:
                return island_perimeter
            
        return island_perimeter

The editorial solution (approach 2) explains the procedure above effectively. The idea is to purposely count each square as contributing 4 to the total parameter but to subtract away 2 when required (we only have to look at squares up and to the left since we're processing the grid top to bottom and from left to right):

1 / 7

This approach is really quite clever and hard to imagine coming up with in an interview (the WATER variable above is not necessary and is included mostly for the sake of clarity). A more likely solution would be the following where each square's perimeter contribution is directly calculated (we start with a contribution of 4 for each square, as above, but we subtract away 1 whenever adjacent land is encountered):

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        WATER = 0
        LAND = 1
        
        rows = len(grid)
        cols = len(grid[0])
        island_perimeter = 0
        ISLAND_FOUND = False
        
        for row in range(rows):
            ROW_ISLAND = False
            for col in range(cols):
                if grid[row][col] == LAND:
                    contribution = 4
                    ISLAND_FOUND = True
                    ROW_ISLAND = True

                    up = WATER if row == 0 else grid[row - 1][col]
                    down = WATER if row == rows - 1 else grid[row + 1][col]
                    left = WATER if col == 0 else grid[row][col - 1]
                    right = WATER if col == cols - 1 else grid[row][col + 1]
                        
                    island_perimeter += (contribution - (up + down + left + right))
                    
            if ISLAND_FOUND and not ROW_ISLAND:
                return island_perimeter
            
        return island_perimeter

The real trap for this problem is to immediately pursue an overly complicated DFS solution:

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        def in_bounds(row, col):
            return 0 <= row < m and 0 <= col < n
        
        def is_water(row, col):
            return not in_bounds(row, col) or grid[row][col] == 0
        
        def is_land(row, col):
            return in_bounds(row, col) and grid[row][col] == 1
        
        def find_island(mat):
            for i in range(m):
                for j in range(n):
                    if mat[i][j] == 1:
                        return i, j
                    
        def perimeter_contribution(row, col):
            above = row - 1, col
            below = row + 1, col
            left = row, col - 1
            right = row, col + 1
            
            perimeter = 0
            
            if is_water(*above):
                perimeter += 1
            if is_water(*below):
                perimeter += 1
            if is_water(*left):
                perimeter += 1
            if is_water(*right):
                perimeter += 1
                
            return perimeter
        
        def dfs(row, col):
            for dr, dc in dirs:
                next_row, next_col = row + dr, col + dc
                if (next_row, next_col) not in seen and is_land(next_row, next_col):
                    nonlocal total_perimeter
                    total_perimeter += perimeter_contribution(next_row, next_col)
                    seen.add((next_row, next_col))
                    dfs(next_row, next_col)
            
        dirs = [(-1,0),(1,0),(0,-1),(0,1)]
        m = len(grid)
        n = len(grid[0])
        island_entry = find_island(grid)
        seen = {(island_entry)}
        total_perimeter = perimeter_contribution(*island_entry)
        dfs(*island_entry)
        
        return total_perimeter

The solution above would be more relevant if we were tasked with, say, finding the maximum perimeter of a number of different islands (i.e., connected components).

Greedy algorithms

Remarks

TBD

# TBD

Examples

LC 2126. Destroying Asteroids (✓)

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the ith asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.

Return true if all asteroids can be destroyed. Otherwise, return false.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()
        for asteroid in asteroids:
            if asteroid > mass:
                return False
            mass += asteroid
        return True

If our planet is not at least as heavy as the smallest asteroid, then it's clearly impossible to destroy all asteroids. The strategy is to destroy and consume the smallest asteroids first, thus ensuring we can destroy as many asteroids as possible. The solution to this problem naturally lends itself to a greedy approach.

LC 2294. Partition Array Such That Maximum Difference Is K (✓)

You are given an integer array nums and an integer k. You may partition nums into one or more subsequences such that each element in nums appears in exactly one of the subsequences.

Return the minimum number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is at most k.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = 1
        curr_min = nums[0]
        for i in range(1, len(nums)):
            if nums[i] - curr_min > k:
                ans += 1
                curr_min = nums[i] 
        return ans

Intuitively, it makes sense that we would like to cover as many numbers as possible for each subsequence that we could create. We could sort the input and then bunch as many items together as possible whose min-max difference is at most k. The solution above does just that.

LC 502. IPO (✓) ★

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit P_i and a minimum capital of C_i is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        n = len(profits)
        projects = []
        for i in range(n):
            projects.append((capital[i], profits[i]))
        projects.sort()
        
        max_heap = []
        i = 0
        for _ in range(k):
            # push projects to the max heap (based on profit) that we have the capital to start
            while i < n and w >= projects[i][0]:
                heapq.heappush(max_heap, -projects[i][1])
                i += 1
            
            # not enough capital to complete anymore projects
            if not max_heap:
                return w
            
            w -= heapq.heappop(max_heap)
            
        return w

This problem is rather confusing at first because the capital used to start a project is not deducted from the running capital total; hence, all we really need to do is maximize the profit we can obtain at each step. Sort the capital input array in ascending order and use a max heap to keep track of projects and the profits that can be obtained. The strategy is basically to keep pushing profit-based items (i.e., projects) to the max heap so long as we have the capital to start such projects. As soon as we don't have enough capital to cover the next project, we simply pop the item from the heap that gives us the maximal profit that we can cover — as noted above, we also do not deduct the capital just used to obtain profit. This means we're always starting projects for which we can gain the most profit.

LC 1481. Least Number of Unique Integers after K Removals (✓)

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freqs = defaultdict(int)
        for num in arr:
            freqs[num] += 1
            
        freqs = sorted(freqs.values(), reverse=True)
        while k > 0:
            freq = freqs[-1]
            k -= freq
            if k < 0:
                return len(freqs)
            freqs.pop()
        
        return len(freqs)

The core idea in this problem is to first count the frequency with which each number occurs and then to remove numbers one at a time from least frequent to most frequent. A variety of ways exist for doing this (e.g., reverse sorting as above and then popping, using a min heap, etc.). But the main greedy strategy is to remove the least frequently occurring numbers first.

LC 881. Boats to Save People (✓)

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        boats = 0
        people.sort()
        lightest = 0
        heaviest = len(people) - 1
        while lightest <= heaviest:
            if people[heaviest] + people[lightest] <= limit:
                lightest += 1
            heaviest -= 1
            boats += 1
            
        return boats

The solution editorial highlights the key ideas best:

If the heaviest person can share a boat with the lightest person, then do so. Otherwise, the heaviest person can't pair with anyone, so they get their own boat.

The reason this works is because if the lightest person can pair with anyone, they might as well pair with the heaviest person.

LC 1323. Maximum 69 Number (✓)

Given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

class Solution:
    def maximum69Number(self, num: int) -> int:
        pos = 0
        first_six_pos = -1
        ref_num = num
        
        while num > 0:
            if num % 10 == 6:
                first_six_pos = pos
            num //= 10
            pos += 1
            
        return ref_num if first_six_pos == -1 else ref_num + 3 * (10 ** first_six_pos)

The key greedy insight: the first 6 we encounter in the number (if there is one) should be changed to a 9. That's it. And it seems fairly clear. The real challenge is how to get at the final number reported in an efficient manner.

It's easy to do something silly here

class Solution:
    def maximum69Number(self, num: int) -> int:
        def get_digits(number):
            digits = []
            while number > 0:
                rem = number % 10
                digits.append(rem)
                number //= 10
            return digits
        
        digits = get_digits(num)
        ans = 9
        NINE_FOUND = True if digits[-1] == 6 else False
        for i in range(len(digits) - 2, -1, -1):
            digit = digits[i]
            if digit == 6:
                if not NINE_FOUND:
                    ans = ans * 10 + 9
                    NINE_FOUND = True
                else:
                    ans = ans * 10 + 6
            else:
                ans = ans * 10 + 9
                
        return ans

Try not to do something silly here. It's hard not to though. The key implementation insight is recognizing that, for example, the difference between 9 and 6 is 3. The difference between 96 and 99 and is 3. The difference between 69 and 99 is 30. The difference between 699 and 999 is 300. And so on. In general, if no 6 exists, then we should return the original number as no improvement can be made in terms of increasing the number's magnitude.

If, however, a 6 does exist, then we should find the first occurrence as well as its position from the end (with the far right position being 0). Changing something like 969699 to 999699 can then be seen as the following: 969699 + 3 * (10 ** 4) == 999699. This is mostly just a clever manipulation that is highly problem-specific. But it is somewhat interesting nonetheless.

LC 1710. Maximum Units on a Truck (✓)

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]:

numberOfBoxes_i is the number of boxes of type i.
numberOfUnitsPerBox_i is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda box_type: box_type[1], reverse=True)
        units_loaded = 0
        for boxes, units in boxTypes:
            boxes = min(truckSize, boxes)
            units_loaded += (boxes * units)
            truckSize -= boxes
            if truckSize == 0:
                return units_loaded
            
        return units_loaded

As usual, it's easy to over-complicate things on this one. The important greedy insight is that we're given the units per box for each box type and we make no distinction between type of unit or type of box; hence, it makes sense to add as many units as we can per box before exhausting the number of boxes we're allowed to load on to the truck.

LC 1196. How Many Apples Can You Put into the Basket (✓)

You have some apples, where arr[i] is the weight of the ith apple. You also have a basket that can carry up to 5000 units of weight.

Return the maximum number of apples you can put in the basket.

class Solution:
    def maxNumberOfApples(self, weight: List[int]) -> int:
        weight.sort()
        weight_used = 0
        apples = 0
        for apple_weight in weight:
            weight_used += apple_weight
            if weight_used > 5000:
                return apples
            apples += 1
        return apples

This is about as straightforward a greedy algorithm problem as there can be. To maximize the number of apples placed in the basket, we always add the lightest apple at each step.

LC 1338. Reduce Array Size to The Half (✓)

Given an array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        freqs = defaultdict(int)
        for num in arr:
            freqs[num] += 1
        
        max_heap = []
        for _, freq in freqs.items():
            heapq.heappush(max_heap, -freq)
        
        arr_size = len(arr)
        target = arr_size / 2
        set_size = 0
        while arr_size > target:
            arr_size += heapq.heappop(max_heap)
            set_size += 1
            
        return set_size

The idea in the solution above is to greedily remove the element that occurs most frequently at each step. This ensures we reduce the original array size by half as efficiently as possible.

LC 3228. Maximum Number of Operations to Move Ones to the End★

You are given a binary string s.

You can perform the following operation on the string any number of times:

Choose any index i from the string where i + 1 < s.length such that s[i] == '1' and s[i + 1] == '0'.
Move the character s[i] to the right until it reaches the end of the string or another '1'. For example, for s = "010010", if we choose i = 1, the resulting string will be s = "000110".

Return the maximum number of operations that you can perform.

class Solution:
    def maxOperations(self, s: str) -> int:
        res = ones = 0
        for i in range(len(s)):
            char = s[i]
            if char == '1':
                ones += 1
            elif i and s[i - 1] == '1':
                res += ones
        return res

This problem really seems like a major implementation challenge at first. It's clear what we need to do: we need to always move each 1 from as far left as possible to the right before encountering another 1 or the end of the string so as to force ourselves to use as many operations as possible (i.e., we greedily choose to effectively sandbag the completion time of moving all 1s to the end of the string).

But how do we count all of the operations needed? We probably do not need to actually move all the 1s and 0s around and consume additional space unless absolutely necesaary. The following key insight, highlighted in this solution, helps a great deal:

We go from left to right and count ones. If we encounter 0 after 1, then we need to move ones from the left. So, we add ones to the result.

The idea is that, whenever we encounter a 0 with 1 as an immediate predecessor, the maximum number of operations we can get at that point is by moving all previously encountered 1s past the current 0, which is why we add ones to the result whenever we encounter a 0 with a 1 preceding it. The condition elif i and s[i - 1] == '1': simply ensures s[i - 1] doesn't resolve to s[-1], where we end up looking at the last character of the string.

Why does 1 have to be an immediate predecessor of 0 before we add ones to res? The rationale is that a block of contiguous 0 values should be treated essentially the same as a single 0 value; that is, a block of zeros will not contribute anything more to the overall operation count than a single 0. Any solution should take this into account. For example, consider the following solution (based on this solution):

class Solution:
    def maxOperations(self, s: str) -> int:
        res = ones = 0
        zero_prev = False

        for char in s:
            if char == '0':
                zero_prev = True
            else:
                if zero_prev:
                    res += ones
                ones += 1
                zero_prev = False

        if zero_prev:
            res += ones

        return res

If we encounter a block of 0 values that is Z characters long, then zero_prev is assigned the value of True a total number of Z consecutive times. The solution above is probably easier to first understand, but the solution at the top is arguably the way to go in terms of overall simplicity once the crux of the problem is understand: If we encounter 0 after 1, then we need to move ones from the left.

Heaps

Top k

Remarks

TBD

# TBD

Examples

LC 347. Top K Frequent Elements (✓)

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = defaultdict(int)
        for num in nums:
            freqs[num] += 1
            
        min_heap = []
        for num, freq in freqs.items():
            heapq.heappush(min_heap, (freq, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
                
        return [ pair[1] for pair in min_heap ]

Since we are trying to find the k elements that occur with maximal frequency, we should use a min heap so that we regularly remove the "worst" element (i.e., least frequently occurring element). Pre-processing steps like finding each element's frequency is fairly common in problems whose solutions rely on heaps in some way.

LC 658. Find K Closest Elements (✓)

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        max_heap = []
        for num in arr:
            heapq.heappush(max_heap, (-abs(num - x), -num))
            if len(max_heap) > k:
                heapq.heappop(max_heap)
                
        return sorted(-pair[1] for pair in max_heap)

This is one of those problems that can be solved with a heap, but that does not mean a heap is necessarily the best option (in fact, this almost certainly cannot be the best option for this problem since we do not use the fact that the input array is already sorted). Regardless, the heap solution above can be informative because it makes us think through how tuples should be pushed to the heap (the distance is the first criterion for the priority, but the magnitude of the number is the second criterion).

LC 215. Kth Largest Element in an Array (✓) ★

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

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []
        for num in nums:
            heapq.heappush(min_heap, num)
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        return min_heap[0]

This is kind of a classic, simplified heap application. We limit the heap to be of size k, and we use a min heap to gradually remove smaller elements. Once we've processed the entire array, the element at the root of the min heap is the kth largest element (the heap holds the k largest elements and the min heap gives us access to the smallest one, which is the kth largest).

LC 973. K Closest Points to Origin (✓) ★

Given an array of points where points[i] = [x_i, y_i] 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., sqrt((x₁ - x₂)² + (y₁ - y₂)²).)

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

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        def distance_from_origin(x, y):
            dist = (x * x + y * y) ** 0.5
            return (-dist, x, y)
        
        max_heap = []
        for point in points:
            heapq.heappush(max_heap, distance_from_origin(*point))
            if len(max_heap) > k:
                heapq.heappop(max_heap)
                
        return [ [pair[1], pair[2]] for pair in max_heap ]

This is a great heap problem. The origin is (0,0); hence, we simply need to find the distance from each point in points to the origin and use a max heap to keep track of the distances, popping the "worst" (i.e., farthest away) point whenever the size of the heap exceeds k.

LC 703. Kth Largest Element in a Stream (✓)

Design a class to find the k^th largest element in a stream. Note that it is the k^th largest element in the sorted order, not the k^th 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) Returns the element representing the k^th largest element in the stream.

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.min_heap = []
        for num in nums:
            heapq.heappush(self.min_heap, num)
            if len(self.min_heap) > k:
                heapq.heappop(self.min_heap)

    def add(self, val: int) -> int:
        heapq.heappush(self.min_heap, val)
        if len(self.min_heap) > self.k:
            heapq.heappop(self.min_heap)
        return self.min_heap[0]

Arguably the hardest part of this problem lies in fully understanding the problem statement. It's poorly expressed. Essentially, we're given k as well as the data stream of numbers, nums, as it exists so far. Then we incrementally add numbers to the stream where we report the kth largest in the stream as we go. We can use a heap here even though it's a little unnatural because we end up ejecting elements from the heap as we go along.

LC 692. Top K Frequent Words (✓) ★★★

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

class Pair:
    def __init__(self, word, freq):
        self.word = word
        self.freq = freq
        
    def __lt__(self, other):
        return self.freq < other.freq or (self.freq == other.freq and self.word > other.word)

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        freqs = defaultdict(int)
        for word in words:
            freqs[word] += 1
        
        min_heap = []
        for word, freq in freqs.items():
            heapq.heappush(min_heap, Pair(word, freq))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
                
        res = [''] * k
        i = k - 1
        while min_heap:
            res[i] = heapq.heappop(min_heap).word
            i -= 1
            
        return res

Probably the easiest semi-effective heap solution is to actually use a max heap in a somewhat bizarre way where we do not limit the heap size and we simply pop k elements from the heap — the k elements will have maximal frequency and words with equal frequencies will be popped in such a way that the lexicographically smaller ones remain (because using a max heap in Python means we simulate its usage with a min heap):

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        freqs = defaultdict(int)
        for word in words:
            freqs[word] += 1
        
        max_heap = []
        for word, freq in freqs.items():
            heapq.heappush(max_heap, (-freq, word))
            
        return [ heapq.heappop(max_heap)[1] for _ in range(k) ]

But we should be able to do better than this. The issue is clear: The hardest part of this problem from the standpoint of a heap-based solution is that the first priority is maximal frequency, but the second priority is minimal lexicographic value of the word whose frequency is being considered. The "top k" nature of the problem where we're trying to find words with maximal frequencies indicates we should use a min heap. But complications arise when we run into two words of the same frequency that maybe start with the same first few letters.

For example, suppose (3, 'hope') and (3, 'home') are both in the running for the final spot in the list of words we should return (i.e., other words occur less frequently). If we're using a min heap to store the tuples above, then (3, 'home') will be popped before (3, 'hope') because 3 == 3 and 'home' < 'hope'; that is, the frequency values are the same, but 'home' is lexicographically smaller than 'hope'. But eliminating 'home' is not what we want in this case! How can we ensure lexicographically larger words are considered to be less than lexicographically smaller words when the frequencies of the words are the same?

As the solution above indicates, a savvy approach is to create a user-defined class, Pair, where each class instance is an object with the priority information encoded, namely the word itself as well as its frequency. As the Python docs note, the expression x < y results in calling x.__lt__(y), which has the following signature: object.__lt__(self, other). Hence, our Pair class should have __lt__ defined in such a way that Pair_1 is considered to be less than Pair_2 if the word frequency of Pair_1 is less than the word frequency of Pair_2 or if their word frequencies are the same and the word in Pair_1 is lexicographically larger than the word in Pair_2:

def __lt__(self, other):
    return self.freq < other.freq or (self.freq == other.freq and self.word > other.word)

Defining the Pair class means we can ensure our heap behaves as desired, and it also paves a path forward for other problems that may need a heap-based solution where we need to get creative in how priorities are managed.

Multiple heaps

Remarks

TBD

# TBD

Examples

LC 295. Find Median from Data Stream (✓)

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

class MedianFinder:
    def __init__(self):
        self.min_heap = []
        self.max_heap = []
        self.length = 0

    def addNum(self, num: int) -> None:
        heapq.heappush(self.min_heap, num)
        heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
        if len(self.max_heap) - len(self.min_heap) > 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        self.length += 1

    def findMedian(self) -> float:
        return -self.max_heap[0] if self.length % 2 == 1 else (self.min_heap[0] - self.max_heap[0]) * 0.5

The idea above is to use two heaps, a min_heap and a max_heap, to effectively partition the data stream into "lower" and "upper" halves in terms of numeric values (since a median always depends on a sorted list of numbers). The max heap will contain the lower half (root value in the max heap will be the maximum number for the lower half, meaning it resides towards the middle of the data stream), and the min heap will contain the upper half (root value in the min heap will be the minimum number for the upper half, meaning it resides towards the middle of the data stream).

Arbitrarily, the solution above is structured in such a way that the root of the max heap will be used if the overall length of the stream is odd. If the stream length is even, then the average of the roots for the heaps will need to be taken.

LC 480. Sliding Window Median (✓) ★★

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5

Given an array 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. Your job is to output the median array for each window in the original array.

For example, given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 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]      6

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note: You may assume k is always valid, ie: k is always smaller than input array's size for non-empty array. Answers within 10^-5 of the actual value will be accepted as correct.

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        def get_median(min_h, max_h, parity):
            return -max_h[0] if parity else (min_h[0] - max_h[0]) * 0.5
        
        # initialize various variables
        PARITY = k % 2
        medians = []
        min_heap = []
        max_heap = []
        invalids = defaultdict(int)
        
        # initialize both heaps by processing the first k elements
        # (if k is odd, then max heap will contain one more element than min heap)
        for i in range(k):
            heapq.heappush(max_heap, -nums[i])
            
        for _ in range(k // 2):
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
            
        # append first sliding window median to answer array
        medians.append(get_median(min_heap, max_heap, PARITY))
        
        for i in range(k, len(nums)):
            
            in_num = nums[i]        # new window element
            out_num = nums[i - k]   # invalid/outgoing window element
            invalids[out_num] += 1  # increment invalid count of newly invalidated element
            
            # balance factor (out_num exits the window)
            # initialize as -1 if an item in the max heap is invalidated
            # initialize as 1 if an item in the min heap is invalidated
            balance = -1 if out_num <= -max_heap[0] else 1
            
            # (in_num enters the window, try to add to max heap first)
            if max_heap and in_num <= -max_heap[0]:
                heapq.heappush(max_heap, -in_num)
                balance += 1
            else:
                heapq.heappush(min_heap, in_num)
                balance -= 1

            # re-balance heaps    
            if balance < 0:       # max_heap needs more valid elements
                heapq.heappush(max_heap, -heapq.heappop(min_heap))
                balance += 1
            if balance > 0:       # min_heap needs more valid elements
                heapq.heappush(min_heap, -heapq.heappop(max_heap))
                balance -= 1

            # remove invalid numbers that should be discarded from heap tops    
            while max_heap and invalids[-max_heap[0]]:
                invalids[-max_heap[0]] -= 1
                heapq.heappop(max_heap)
            while min_heap and invalids[min_heap[0]]:
                invalids[min_heap[0]] -= 1
                heapq.heappop(min_heap)

            # get median of newly prepared window and add to medians array
            medians.append(get_median(min_heap, max_heap, PARITY))
        
        return medians

This is definitely a tough one, a problem similar to LC 295. Find Median from Data Stream but with an added degree of difficulty: now we need to remove elements from the heaps we're maintaining to dynamically calculate the median for each window.

The strategy is essentially as follows:

The parity of k (i.e., odd or even) will determine how median items are calculated (i.e., if k is odd, then we'll automatically pull from max_heap since max_heap is what we've chosen to possibly be the heap with at most a larger size of 1 for valid elements)
Start by indiscriminately pushing k elements to max_heap. Then pop half of those elements from max_heap and push them to min_heap. This ensures the heaps start off as balanced as possible, and the first window of k valid elements has been prepared. We append its median to the medians array we will ultimately return.
For each remaining number in the nums input array:
- Declare each newly encountered number as in_num, the newest valid number in a window.
- Keep track of the newly invalidated number out_num that is no longer part of the window (increment the count of out_num in the invalids lookup dictionary).
- Let balance denote how removing out_num will effect the balance of the two heaps: if out_num will be removed from max_heap (i.e., out_num is less than or equal to the root of the max heap), then set balance = -1; if, however, out_num will be removed from min_heap, then set balance = 1. The value assigned to balance here will effect whether or not we need to re-balance the heaps after in_num is added to one of the heaps.
- Which heap should in_num be added to? If in_num is less than or equal to -max_heap[0], then in_num should be added to max_heap, which means balance should be incremented by 1; otherwise, in_num should be added to min_heap, and balance should be decremented by 1.
- We've now virtually removed out_num from the window and adjusted balance accordingly. We've also literally added in_num to one of the heaps and also adjusted balance accordingly. If balance == 0, then the heaps are balanced and we can proceed (max_heap may have one more valid element than min_heap at this stage, but that is by design). If, however, balance < 0, then this means max_heap has more valid elements than it should, and the heaps are not balanced — an element needs to be moved from max_heap to min_heap. Similar logic applies to needing to move an element from min_heap to max_heap when balance > 0.
- After the re-balancing done above, it's possible invalid elements now reside at the top of either heap (or both). We need to remove the invalid elements from the heap tops. Note that order matters here based on how the rest of the solution is constructed. We need to first remove invalid elements from max_heap. Why? Consider the following example input: nums = [1,1,1,1], k = 2. How could this be problematic if we removed invalid elements from min_heap first instead of max_heap? Because the heaps will start out properly balanced with 1 in both heaps. Then, as the window slides to the right, the leftmost 1 becomes invalidated, but our solution doesn't track indexing; hence, when we attempt to remove an invalid 1, and we do so from min_heap, we basically end up with an empty min_heap and a max_heap with two elements. Since k == 2 is even, trying to compute the median from the root elements of min_heap and max_heap leads to an error (min_heap is empty). First removing from max_heap avoids this, and it makes even more sense when we consider that we're always first trying to add to max_heap.
- The new window has now been prepared, where heap tops are valid elements. We calculate the median and add it to our list.

LC 2462. Total Cost to Hire K Workers (✓) ★★★

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.

You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:

You will run k sessions and hire exactly one worker in each session.
In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
- For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2].
- In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.
If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
A worker can only be chosen once.

Return the total cost to hire exactly k workers.

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)
        m = candidates
        
        # if using m candidates on both sides of costs results in a single partition,
        # then there is no need to consider separate partitioning of worker
        # (the answer can be obtained via simple usage of a max heap)
        if 2 * m >= n:
            max_heap = []
            for i in range(n):
                heapq.heappush(max_heap, -costs[i])
                if len(max_heap) > k:
                    heapq.heappop(max_heap)
            return -sum(max_heap)
        
        HEAD = 0  # marker for head partition workers
        TAIL = 1  # marker for tail partition workers
        total_cost = 0
        min_heap = []
        
        # push all partitioned workers (thus far) into min heap
        for i in range(m):
            heapq.heappush(min_heap, (costs[i], HEAD))
            heapq.heappush(min_heap, (costs[n - i - 1], TAIL))
            
        next_head = m           # next available worker from head partition
        next_tail = n - m - 1   # next available worker from tail partition
        for _ in range(k):
            # add cost of minimal cost worker to total cost;
            # note the section (head/tail) the worker was chosen from
            #   because that section will need a new worker
            cost, section = heapq.heappop(min_heap)
            total_cost += cost

            # only maintain partitions if new worker(s) are still available
            if next_head <= next_tail:
                if section == HEAD:
                    heapq.heappush(min_heap, (costs[next_head], HEAD))
                    next_head += 1
                else:
                    heapq.heappush(min_heap, (costs[next_tail], TAIL))
                    next_tail -= 1
        
        return total_cost

This is a deceptively difficult problem at first. If the number of candidates on both ends of costs ends up overlapping (i.e., 2 * m >= n in the solution above), then we can treat this problem as a basic heap problem where we find the minimum total cost by using a max heap and ejecting the most costly workers as we encounter them (keeping the k cheapest workers on the heap).

The real difficulty lies in what to do when there is no overlap and we need to somehow keep track of how we process workers. As the official solution notes, two heaps can be used to solve this problem (Approach 1), but we can just as easily solve the problem using a single heap if we introduce an effective way of determining which "side" or "partition" of costs a worker's cost just came from when we are processing the costs of all workers. That side will be the side we need to add a new worker to.

We consider the initial m workers (i.e., m == len(candidates)) on the left side of costs to be in the HEAD partititon and the initial m workers on the right side of costs to be in the TAIL partition. For each of k iterations, we extract the cost of the cheapest worker and remove that worker from their partition and, so long as new workers remain to be processed, we add a new worker back to that partition. Using a heap in this way allows us to keep the partitions balanced so long as there isn't overlap — when there is overlap, there's no need to distinguish between the head and tail partitions and we can just remove the minimal cost worker.

LC 2402. Meeting Rooms III (✓) ★★

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [start_i, end_i] means that a meeting will be held during the half-closed time interval [start_i, end_i). All the values of start_i are unique.

Meetings are allocated to rooms in the following manner:

Each meeting will take place in the unused room with the lowest number.
If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

A half-closed interval [a, b) is the interval between a and b including a and not including b.

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        # unused_rooms and used_rooms are both min heaps
        unused_rooms = list(range(n))
        used_rooms = []
        room_meetings = [0] * n
        most_meetings = [0, 0]
        
        meetings.sort()
        for start, end in meetings:
            # maintenance: remove each used room whose end time occurred
            #   before (or at the same time as) the current meeting's start time;
            #   push the now removed used room to the available unused rooms
            while used_rooms and used_rooms[0][0] <= start:
                _, room = heapq.heappop(used_rooms)
                heapq.heappush(unused_rooms, room)
            
            # if an unused room is available, take the smallest numbered one
            if unused_rooms:
                room = heapq.heappop(unused_rooms)      # note room number and remove from unused rooms
                heapq.heappush(used_rooms, (end, room)) # push room to used rooms and note when room will next become available
            else:
                curr_meeting_duration = end - start # time to add to the next available time for the room we will use for the current meeting
                next_available_room_time, room = heapq.heappop(used_rooms) # note the availability time and room number of next available room
                heapq.heappush(used_rooms, (next_available_room_time + curr_meeting_duration, room)) # mark the next available room appropriately
            room_meetings[room] += 1
            
            # keep track of room with the most meetings thus far
            if room_meetings[room] >= most_meetings[0]:
                if room_meetings[room] > most_meetings[0]:
                    most_meetings[0] = room_meetings[room]
                    most_meetings[1] = room
                else:
                    most_meetings[1] = min(most_meetings[1], room)
                    
        return most_meetings[1]

This is quite a tough problem at first, but once the idea becomes clear how to use two heaps to effectively manage the used and unused rooms, everything falls neatly into place. The code comments nicely explain the intuition for the solution above.

General

Remarks

TBD

# TBD

Examples

LC 1046. Last Stone Weight (✓)

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [ -val for val in stones ]
        heapq.heapify(stones)
        
        while len(stones) > 1:
            y = -heapq.heappop(stones)
            x = -heapq.heappop(stones)
            
            if x == y:
                continue
            else:
                y = y - x
                heapq.heappush(stones, -y)
                
        return -stones[0] if stones else 0

Start by heapifying stones into a max heap. Then process the heap in such a way that the rules of the game are respected.

LC 2208. Minimum Operations to Halve Array Sum (✓)

You are given an array nums of positive integers. In one operation, you can choose any number from nums and reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return the minimum number of operations to reduce the sum of nums by at least half.

class Solution:
    def halveArray(self, nums: List[int]) -> int:
        arr_sum = 0
        for i in range(len(nums)):
            arr_sum += nums[i]
            nums[i] = -nums[i]
        
        target = arr_sum * 0.5
        heapq.heapify(nums)
        ops = 0
        
        while arr_sum > target:
            reduced = heapq.heappop(nums) * 0.5
            arr_sum += reduced
            ops += 1
            heapq.heappush(nums, reduced)
            
        return ops

The idea here is to first get the entire sum of nums and then to heapify nums into a max heap. Then we can follow the guidelines outlined in the problem statement.

LC 1845. Seat Reservation Manager (✓) ★★

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

class SeatManager:
    def __init__(self, n: int):
        self.available = [ i for i in range(1, n + 1) ]

    def reserve(self) -> int:
        return heapq.heappop(self.available)

    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.available, seatNumber)

This is an easy problem to over-complicate. It's tempting to craft a solution where we're actively tracking the available and unavailable seats:

class SeatManager:
    def __init__(self, n: int):
        self.available = [ i for i in range(1, n + 1) ]
        self.unavailable = set()

    def reserve(self) -> int:
        while self.available[0] in self.unavailable:
            heapq.heappop(self.available)
        seat_number = heapq.heappop(self.available)
        self.unavailable.add(seat_number)
        return seat_number

    def unreserve(self, seatNumber: int) -> None:
        self.unavailable.remove(seatNumber)
        heapq.heappush(self.available, seatNumber)

But this is really a waste of time and space. The reality is that if we start with a min heap that represents all available seats, then every time we reserve a seat, that seat simply gets popped from the min heap and is no longer an available seat. When we unreserve a seat, that simply means we add the seat back to the heap. The takeaway: there's no need to explicitly track unavailable seats.

LC 2336. Smallest Number in Infinite Set (✓) ★★

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.
int popSmallest() Removes and returns the smallest integer contained in the infinite set.
void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

class SmallestInfiniteSet:
    def __init__(self):
        self.added_back = []
        self.removed = set()
        self.curr_smallest = 1

    def popSmallest(self) -> int:
        if self.added_back:
            remove_again = heapq.heappop(self.added_back)
            self.removed.add(remove_again)
            return remove_again
        else:
            smallest = self.curr_smallest
            self.removed.add(smallest)
            self.curr_smallest += 1
            return smallest

    def addBack(self, num: int) -> None:
        if num in self.removed and num < self.curr_smallest:
            self.removed.remove(num)
            heapq.heappush(self.added_back, num)

The intended solution, as provided above, is not the easiest to come up with at first. It would be much easier if we simply exploited the problem constraint of 1 <= num <= 1000:

class SmallestInfiniteSet:
    def __init__(self):
        self.min_heap = [ num for num in range(1, 1000 + 1)]
        self.removed = set()

    def popSmallest(self) -> int:
        smallest = heapq.heappop(self.min_heap)
        self.removed.add(smallest)
        return smallest

    def addBack(self, num: int) -> None:
        if num in self.removed:
            self.removed.remove(num)
            heapq.heappush(self.min_heap, num)

But this is cheating and doesn't really apply at scale. We should be able to come up with a solution that doesn't depend on initializing our min heap in such a way. We can still use some of the logic in the "cheat solution" above in the intended solution. The intended solution basically uses the following logic:

Maintain self.curr_smallest, which will always be a pointer to what the newest smallest number in the infinite set could be.
If numbers get added back that are smaller than self.curr_smallest, then we need some way of being able to manage these numbers in such a way that we always have access to the smallest one. We use a min heap for that: self.added_back. Of course, numbers should only ever be added back if, in fact, they were once removed and they are smaller than self.curr_smallest. We use the set self.removed to track the status of which elements have, in fact, been removed.

LC 2182. Construct String With Repeat Limit (✓) ★

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        freqs = defaultdict(int)
        for char in s:
            freqs[ord(char)] += 1
            
        max_heap = []
        res = []
        for char_code, freq in freqs.items():
            heapq.heappush(max_heap, (-char_code, freq))
            
        while max_heap:
            char_code, char_count = heapq.heappop(max_heap)
            char = chr(-char_code)
            repeat_count = 0
            
            while char_count > 0 and repeat_count < repeatLimit:
                res.append(char)
                char_count -= 1
                repeat_count += 1
                
                if repeat_count == repeatLimit and char_count > 0:
                    if not max_heap:
                        return ''.join(res)
                    else:
                        repeat_count = 0
                        next_char_code, next_char_freq = heapq.heappop(max_heap)
                        res.append(chr(-next_char_code))
                        next_char_freq -= 1
                        if next_char_freq > 0:
                            heapq.heappush(max_heap, (next_char_code, next_char_freq))
            
        return ''.join(res)

This is a tough problem primarily because of the fancy footwork required to manage how letters are used as well as "next largest letters". It's somewhat clear from the problem statement that we should use a max heap to keep track of the lexicographically largest letters (which we can simulate in Python by negating the character code for each character) as well as the frequency of each letter.

Then we start processing all letters on the heap. The current letter being processed is always the lexicographically largest letter remaining. Our job is to ensure we use all occurrences of this letter or return early if we can proceed no longer. We keep track of the repeat count so far and, whenever that limit is reached and occurrences still remain, we check to see if anything else is on the heap to use as a reference for the next largest letter. If not, we're done and we return early because we can't add another letter occurrence without violating the repeat limit. If so, then we essentially "steal" a single occurrence of the next largest letter, adding that to the result string, and reset the repeat count to zero for the current letter being processed.

The mechanics for this problem are largely what makes it difficult.

LC 373. Find K Pairs with Smallest Sums (✓) ★★

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u₁, v₁), (u₂, v₂), ..., (u_k, v_k) with the smallest sums.

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        m = len(nums1)
        n = len(nums2)
        min_heap = [(nums1[0] + nums2[0], 0, 0)]
        res = []
        
        while min_heap and k > 0:
            _, i, j = heapq.heappop(min_heap)
            res.append([nums1[i], nums2[j]])  # append values for sum at row i, column j
            k -= 1
            
            # always add tuple to right of current tuple if possible 
            # (i.e., advance 1 column to the right on the current row)
            if j + 1 < n:
                heapq.heappush(min_heap, (nums1[i] + nums2[j + 1], i, j + 1))
            # only add tuple below current tuple if current tuple resides in first column
            # (i.e., advance 1 row down if current tuple lies on first column)
            if j == 0 and i + 1 < m:
                heapq.heappush(min_heap, (nums1[i + 1] + nums2[j], i + 1, j))
                
        return res

It's incredibly helpful/useful to look at the provided data as a grid graph where we solve the problem by sort of treating it as a BFS with the help of a min heap:

The illustration above provides an example for the input nums1 = [2, 5, 8], nums2 = [1, 3, 7, 9].
The green numbers are from the input arrays themselves while the blue numbers indicate index values — the blue tuples show the index values from each input array.
The grid is constructed in such a way that it's as if we have an m x n matrix with m rows and n columns (i.e., the number of rows is the same as the number of elements in nums1 and the number of columns is the same as the number of elements in nums2).
The magenta numbers above each tuple show the pair sum for that tuple.
Suppose a tuple is popped from the heap and processed (e.g., the very first tuple at coordinates (0,0)). The orange arrows show which tuples are added to the heap after processing the current tuple. Since both input arrays are sorted, note that it only ever makes sense to add tuples to the right of each processed tuple unless the tuple processed is in the first column. This also makes it easy for us to avoid having to keep track of potentially considering duplicate tuples.

LC 632. Smallest Range Covering Elements from K Lists (✓) ★★

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # initialize a min heap that will contain left boundary candidates
        # this min heap will always have k values, one from each list of numbers
        left_boundaries = []
        for i in range(len(nums)):
            nums_arr = nums[i]
            heapq.heappush(left_boundaries, (nums_arr[0], i, 0))

        # the initial right boundary will be the largest of the left boundary candidates
        right = max(triple[0] for triple in left_boundaries)
        
        # initialize the answer to be an infinite interval
        ans = [ float('-inf'), float('inf') ]
        while left_boundaries:
            # minimal left boundary, ith list, jth element
            left, i, j = heapq.heappop(left_boundaries)

            # only update if strictly tighter range has been found
            # (equivalent ranges should not result in an update
            # because left boundaries are popped from the min heap
            # which means the current answer's left boundary would be smaller)
            if right - left < ans[1] - ans[0]:
                ans = [left, right]

            # only return the answer as soon as one of the k lists has been exhausted
            # if we continued despite the condition below, then our range would potentially
            #   not include an element from each of the k lists
            if j + 1 == len(nums[i]):
                return ans
            
            # if the condition above was not met, then update the right boundary
            #   to be the maximum of the current right boundary and the newest added element
            right = max(right, nums[i][j + 1])

            # the first line of the while loop resulted in removing from the heap
            #   the jth element from list i; we now add the (j + 1)st element from list i
            #   to the heap (this ensures the heap still contains an element from each list)
            heapq.heappush(left_boundaries, (nums[i][j + 1], i, j + 1))

The solution above, based on the top-voted one on LeetCode, takes some real ingenuity to conjure up. It's a real head-scratcher at first.

As noted in one of the comments on the linked solution above:

The key insight/ intuition (non-obvious) is that the heap always contains ONLY 1 element from each list/ row array. The heap NEVER contains 2 or more elements from the SAME list. This is important because it means that the range calculated at every iteration is always guaranteed to be a range that has exactly 1 element from every single list!

For example, suppose we have the input array from the first example in the problem description on LeetCode:

nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

Now add the print statement print(left_boundaries) directly under the beginning of the while loop in the solution above:

[(0, 1, 0),  (4, 0, 0),   (5, 2, 0)]
[(4, 0, 0),  (5, 2, 0),   (9, 1, 1)]
[(5, 2, 0),  (9, 1, 1),  (10, 0, 1)]
[(9, 1, 1),  (10, 0, 1), (18, 2, 1)]
[(10, 0, 1), (18, 2, 1), (12, 1, 2)]
[(12, 1, 2), (18, 2, 1), (15, 0, 2)]
[(15, 0, 2), (18, 2, 1), (20, 1, 3)]
[(18, 2, 1), (20, 1, 3), (24, 0, 3)]
[(20, 1, 3), (24, 0, 3), (22, 2, 2)]

The middle number in each tuple denotes which list the left boundary (leftmost tuple number) came from. Note how every time we print the contents of the heap we see that each list (0, 1, and 2 for the example input comprised of three lists) is represented and is only represented once. This is a brilliant way of ensuring an element from each list is always present for each range query.

Initialize heap in O(n) time

Remarks

Min heap: Sometimes it is helpful to initialize our own min heap in such a way that we simply append the smallest elements to a list, one at a time. Time and space: $O(n)$ .
Max heap: Python uses a min heap. Hence, we need to add the biggest elements to the heap, in order, but negate them as we do so. Time and space $O(n)$ .
Heapify (to min heap): Both approaches above assume we have the luxury of being able to add the minimum or maximum elements to a list and then use that list as a min or max heap, respectively. This is often not the case. We will often want to take an existing list of $n$ elements, arr, and modify it in-place to be a heap in $O(n)$ time. This is not a trivial task, as Python's source code for the heapify method shows. This is not something we want to have to manually implement ourselves. Fortunately, we don't have to!

Simply use Python's heapify method. Time: $O(n)$ ; space: $O(1)$ .
Heapify (to max heap): The heapify approach above only applies for a min heap. As noted in this question, Python's source code actually supports a _heapify_max method! But there's not similar support for operations like pushing to the max heap. We effectively have two options to utilize the fulle suite of methods available in Python's heapq module:
1. Negate the elements of arr in-place. Then use the heapify method to simulate a max heap even though Python is technically maintaining a min heap. Time: $O(n)$ ; space: $O(1)$ .
2. Loop through all elements in arr, negating each along the way, and simultaneously use the heappush method to push the element to the max heap we are building. Time: $O(n\lg n)$ ; space: $O(n)$ .
The time cost of the first approach is $O(n + n) = O(2n) = O(n)$ since the initial loop through to negate all numbers is $O(n)$ and the heapify method is also $O(n)$ . But practically speaking the second method is also fairly effective and more intuitive. But the first option is surely better for coding interviews!

Min heap
Max heap
Heapify (to min heap)
Heapify (to max heap)

min_heap = []
for i in range(n):
    min_heap.append(i)

max_heap = []
for i in range(n - 1, -1, -1):
    max_heap.append(-1 * i)

import heapq

arr = [ ... ] # n elements
heapq.heapify(arr)

import heapq

# Approach 1 (negate, heapify in-place); T: O(n); S: O(1)
arr = [ ... ] # n elements
arr = [ -1 * arr[i] for i in range(len(arr)) ] # negate elements in-place
heapq.heapify(arr)

# Approach 2 (negate, build heap); T: O(n lg n); S: O(n)
arr = [ ... ] # n elements
the_heap = []
for num in arr:
  heapq.heappush(the_heap, -1 * num)

Examples

LC 1845. Seat Reservation Manager

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

class SeatManager:
    def __init__(self, n: int):
        self.available = [ i for i in range(1, n + 1) ]

    def reserve(self) -> int:
        return heapq.heappop(self.available)

    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.available, seatNumber)

This is an easy problem to over-complicate. It's tempting to craft a solution where we're actively tracking the available and unavailable seats:

class SeatManager:
    def __init__(self, n: int):
        self.available = [ i for i in range(1, n + 1) ]
        self.unavailable = set()

    def reserve(self) -> int:
        while self.available[0] in self.unavailable:
            heapq.heappop(self.available)
        seat_number = heapq.heappop(self.available)
        self.unavailable.add(seat_number)
        return seat_number

    def unreserve(self, seatNumber: int) -> None:
        self.unavailable.remove(seatNumber)
        heapq.heappush(self.available, seatNumber)

Linked lists

What does it mean for two linked list nodes to be "equal"?

TLDR: The default comparison is made by determining whether or not the two nodes point to the same object in memory; that is, node1 == node2 effectively equates to id(node1) == id(node2) by default in Python.

If node1 and node2 are both nodes from a linked list, then what does node1 == node2 actually test? How is the returned boolean computed? The following snippet is illustrative:

nodeA = ListNode(1)
nodeB = nodeA
nodeC = ListNode(1)

print(nodeA == nodeB)   # True
print(nodeA == nodeC)   # False

As noted on Stack Overflow, for an arbitrary object, the == operator will only return true if the two objects are the same object (i.e., if they refer to the same address in memory). This is often what we actually want when it comes to linked list nodes.

The Python docs about value comparisons back up the note above:

The operators <, >, ==, >=, <=, and != compare the values of two objects. The objects do not need to have the same type.

Chapter Objects, values and types states that objects have a value (in addition to type and identity). The value of an object is a rather abstract notion in Python: For example, there is no canonical access method for an object's value. Also, there is no requirement that the value of an object should be constructed in a particular way, e.g. comprised of all its data attributes. Comparison operators implement a particular notion of what the value of an object is. One can think of them as defining the value of an object indirectly, by means of their comparison implementation.

Because all types are (direct or indirect) subtypes of object, they inherit the default comparison behavior from object. Types can customize their comparison behavior by implementing rich comparison methods like __lt__(), described in Basic customization.

The default behavior for equality comparison (== and !=) is based on the identity of the objects. Hence, equality comparison of instances with the same identity results in equality, and equality comparison of instances with different identities results in inequality. A motivation for this default behavior is the desire that all objects should be reflexive (i.e. x is y implies x == y).

One can override the default __eq__, if desired, but this will likely lead to undesired behavior, particularly in this context of dealing with linked lists. As the Python docs note:

By default, object implements __eq__() by using is, returning NotImplemented in the case of a false comparison: True if x is y else NotImplemented. For __ne__(), by default it delegates to __eq__() and inverts the result unless it is NotImplemented. There are no other implied relationships among the comparison operators or default implementations; for example, the truth of (x<y or x==y) does not imply x<=y. To automatically generate ordering operations from a single root operation, see functools.total_ordering().

What are sentinel nodes and how can they be useful for solving linked list problems?

TLDR: Sentinel or "dummy" nodes can simplify linked list operations, especially those involving the head for singly linked lists (one sentinel node) or the head and tail for doubly linked lists (two sentinel nodes).

Sentinel nodes, also known as "dummy" nodes, often simplify linked list operations considerably, especially when dealing with addition or removal operations involving the head of a linked list. The following brief explanation/definition from ChatGPT is arguably more readable than the linked Wiki article above:

A sentinel node is a dummy or placeholder node used in data structures to simplify boundary conditions and operations. In the context of linked lists, a sentinel node acts as a non-data-bearing head or tail node, eliminating the need for handling special cases for operations at the beginning or end of the list, such as insertions or deletions. It streamlines code by providing a consistent starting or ending point, regardless of whether the list is empty or contains elements.

In the context of solving LeetCode problems (or algorithmic problems in general), you will often see a sentinel node used for singly linked lists in the following manner:

class Solution:
    def fn(self, head: Optional[ListNode]) -> Optional[ListNode]:
      sentinel = ListNode(-1)
      sentinel.next = head
      prev = sentinel
      curr = head

      # do something with prev, curr, and execute other logic
      
      return sentinel.next  # return the new/original head of the modified linked list

A very simple example that highlights the utility of sentinel nodes is the following: Given an integer array nums, how can you convert the array into a linked list? The immediate problem that confronts is what to do about the head for the new linked list. It will obviously be the first element in nums, but is there a nice way of building the list? A simple sentinel node allows us to do just that:

def linked_list_from_arr(nums):
    sentinel = ListNode(-1)
    curr = sentinel
    for num in nums:
        curr.next = ListNode(num)
        curr = curr.next
    return sentinel.next

Pointer manipulation and memory indexes

TLDR: Linked list problems are all about pointer manipulation. Rarely do we change val attributes for nodes in a linked list, but we regularly shift nodes around by artfully manipulating next attributes for various nodes (i.e., pointer manipulation).

Note 1: The assignment my_var = some_node means my_var will always point to the original some_node object in memory unless modified directly (e.g., my_var = something_else). Caveat to this is the note below.
Note 2: The attribute values of some_node, namely val and next, can be modified indirectly by various means. Hence, even though my_var may not point to a different object in memory, if the attribute values of the underlying object in memory are changed, then it will likely appear as though my_var no longer refers to its originally referenced object even though it technically does.

Note 1 (variables remain at nodes unless modifed directly):

When you assign a pointer to an existing linked list node, the pointer refers to the object in memory. Suppose you have a node head:

ptr = head
head = head.next
head = None

After these lines of code, ptr still refers to the original head node, even though the head variable changed. This underscores an important concept concerning linked lists and pointer manipulation: variables remain at nodes unless they are modified directly (i.e., ptr = something is the only way to modify ptr).

We can see this more easily and explicitly in Python by using the id() function, which returns the address of the object in memory (for the CPython implementation of Python):

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
    
one = ListNode(1)
two = ListNode(2)
one.next = two
head = one

print(id(head))     # 4423470576
ptr = head 
print(id(ptr))      # 4423470576
head = head.next
print(id(head))     # 4423470480
head = None 
print(id(head))     # 4420398192
print(id(ptr))      # 4423470576

Objects are mutable in Python. When we make the assignment ptr = head, we are effectively making ptr point to the same memory address as head. The assignment more or less looks like the following:

Subsequently, when we assign head to head.next, we are making head point to the same memory address as head.next:

Note that ptr is not still pointing at head (it's pointing to the object in memory that head originally pointed to). The takeaway: a variable that serves as a specific node assignment will remain as such a specific node assignment unless modified directly to point to another node. This is what allows us above to point ptr to head and then do whatever we want to with head all while maintaining our reference to the original head with ptr.

Note 2 (node attributes such as val and next may be modified indirectly):

As detailed in the note above, the code block

ptr = head
head = head.next
head = None

means that ptr, unless modified directly, will always point to the object in memory originally referred to by head.

Importantly, however, the object in memory originally referred to by head can have its attributes modified indirectly (i.e., the val and next attributes of the head object to which ptr points can be modified without altering ptr directly). The following example can help illustrate this important observation:

head = ListNode(100)
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
head.next = node1
node1.next = node2
node2.next = node3

sentinel = ListNode(-1)
sentinel.next = head

ptr = head
head = head.next
head = None


print(id(ptr))              # 0123456789
print(ptr)                  # 100 -> 1 -> 2 -> 3 -> None
print(ptr.val)              # 100
print(ptr.next)             # 1 -> 2 -> 3 -> None

sentinel.next.val = 7       # original "head" attribute "val" changes from 100 to 7
sentinel.next.next = node2  # original "head" attribute "next" changes from node1 to node2

print(id(ptr))              # 0123456789
print(ptr)                  # 7 -> 2 -> 3 -> None
print(ptr.val)              # 7
print(ptr.next)             # 2 -> 3 -> None

Note that ptr was never modified directly and that it still points to the same object in memory before and after the sentinel.next.[val|next] changes (i.e., printing id(ptr) before and after the changes confirms this since the printed values are the same).

But it certainly seems like ptr has changed somehow. This is because the object ptr points to has changed in terms of its val and next attribute values. We changed those values indirectly by altering sentinel.next, which pointed to the same mutable object in memory as ptr. Altering the attribute values of the original head object in memory directly with ptr.[val|next] or indirectly with sentinel.next.[val|next] makes no difference. The effect is the same: ptr looks different even though it still points to the same object in memory.

Example: A solution to problem LC 2095. Delete the Middle Node of a Linked List can illustrate the concepts in the second note in a concrete, practical manner:

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        sentinel = ListNode(-1)
        sentinel.next = head
        
        prev = sentinel
        slow = head
        fast = head
        
        # slow points to middle node upon termination
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        
        # skip middle node, effectively removing it
        prev.next = prev.next.next
        return sentinel.next

How does this illustrate the utility of the second note? Consider the case where the linked list is just a single node: [1]. Removing the middle node means removing the only node, meaning we should return [] or None. How is the solution above correct for this edge case since the while loop does not fire, sentinel.next originally points to head, and we ultimately return sentinel.next without ever making a direct reassignment? How does sentinel.next end up pointing to a null value even though it originally points to head?

The reason is due to how prev is being manipulated. Since prev points to sentinel and the while loop doesn't fire, the assignment prev.next = prev.next.next effectively changes what sentinel.next points to; that is, we're not changing sentinel directly, but we are changing the next attribute value of the underlying object in memory being pointed to by sentinel. Hence, prev.next = prev.next.next is effectively the assignment sentinel.next = sentinel.next.next; since sentinel.next points to head and head.next is None, we get our desired result by returning the null value (which indicates the single object has been removed).

Visualizing singly linked lists and debugging your code locally

TLDR: Add a simple __repr__ method to the base ListNode class. This lets you view the linked list extending from any given my_node by simply running print(my_node). To effectively use sample LeetCode inputs in your local testing, you'll need a function arr_to_ll to convert integer arrays into linked lists.

Linked list problems are all about pointer manipulation and it can help a ton to see things, especially if you need to debug issues with your code. LeetCode almost always provides a linked list by simply providing the head node, where all nodes in the list have been created with the following ListNode class (or some minor variation):

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

Given any node, probably the easiest way to visualize the singly linked list that extends from this node is to implement a basic __repr__ method as part of the ListNode class:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        
    def __repr__(self):
        node = self
        nodes = []
        
        while node:
            nodes.append(str(node.val))
            node = node.next
            
        nodes.append('None')

        return ' -> '.join(nodes)

Of course, LeetCode generally shows a linked list as input by providing an integer array. To effectively test your local code on LeetCode inputs, it's necessary to first convert the integer array to a linked list:

def arr_to_ll(arr):
    sentinel = ListNode(-1)
    curr = sentinel
    for val in arr:
        new_node = ListNode(val)
        curr.next = new_node
        curr = curr.next
    return sentinel.next

We can now effectively use LeetCode inputs, visualize them, and also subsequently visualize whatever changes we make to the input:

example_input = [5,2,6,3,9,1,7,3,8,4]
head = arr_to_ll(example_input)
print(head) # 5 -> 2 -> 6 -> 3 -> 9 -> 1 -> 7 -> 3 -> 8 -> 4 -> None

Fast and slow pointers

Remarks

The "fast and slow" pointer technique is a two pointer technique with its own special use cases when it comes to linked lists. Specifically, the idea is that the pointers do not move side by side — they could move at different "speeds" during iteration, begin iteration from different locations, etc. Whatever the abstract difference is, the important point is that they do not move side by side in unison.

There are many two pointer variations when it comes to arrays and strings, but the fast and slow pointer technique for linked lists usually presents itself as, "move the slow pointer one node per iteration, and move the fast node two nodes per iteration."

def fn(head):
    slow = head
    fast = head
    ans = 0
    
    while fast and fast.next:
        # some logic
        slow = slow.next
        fast = fast.next.next
        
    return ans

Examples

Return the middle node value of a linked list with an odd number of nodes (✓)

def get_middle(head):
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
    return slow.val

The main problem here is not knowing the length of the linked list ahead of time. We could push the node values into an array and then find the middle node value that way, but that would be cheating and would never pass in an interview. We could also iterate through the entire linked list, note the full length, iterate through half the full length, and then report the value of the middle node. But that also seems potentially inefficient. The solution above takes advantage of the fact that the slow node will have traveled half the distance of the fast node once the while loop terminates (meaning the slow node should be in the middle of the list, as desired).

It's easier to see with a visualization like the following (x is the desired node while s and f denote the slow and fast pointers, respectively):

Start
  x
12345
s
f

After first iteration
  x
12345
 s
  f

After second iteration
  x
12345
  s
    f

Note that now fast is not null, but fast.next is null, meaning the while loop will not execute, and s points to the middle node, x, as desired.

Return the kth node from the end provided that it exists (✓)

def find_node(head, k):
    slow = head
    fast = head
    
    for _ in range(k):
        fast = fast.next
        
    while fast:
        slow = slow.next
        fast = fast.next
        
    return slow

The idea here is to first advance the fast pointer k units ahead of the slow pointer and then to move them at the same speed for each iteration, meaning they will always be k units apart. When the fast pointer reaches the end (i.e., it points to null), the slow pointer will still be k nodes behind the fast pointer, which is the desired result.

The following illustration, where k = 3, may help:

Start
    k
1234567
s
f

Move fast pointer ahead by k = 3 units
    k
1234567
s
   f

After first iteration
    k
1234567
 s
    f

After second iteration
    k
1234567
  s
     f

After third iteration
    k
1234567
   s
      f

After fourth iteration
    k
1234567
    s
       f

LC 141. Linked List Cycle (✓) ★

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                return True
            
        return False

The solution above takes advantage of Floyd's cycle-detection algorithm, which is quite overcomplicated on the Wikipedia link. The main outcome of the algorithm is that the slow and fast pointers above must be equal at some point if there is a cycle. But how do we know this to be true? Would it be possible for the fast pointer to "jump" the slow pointer in some way? How do we know they'll actually meet if there's a cycle?

The easiest way to answer this question is to break down all of the possibilities once slow and fast are both within the cycle; that is, fast will obviously be well ahead of slow until slow actually enters the cycle, at which point slow and fast will either be at the same node or fast will be behind slow. We have the following possibilities:

Case 1: fast and slow meet exactly when slow enters the cycle (i.e., at the beginning of the cycle)
Case 2: fast is exactly one node behind slow, and the two nodes will meet on the very next iteration since slow will move forward one node and fast will move forward two nodes
Case 3: fast is exactly two nodes behind slow, and the nodes will meet after two more iterations since slow will have moved two more nodes and fast will have moved four more nodes
Case 4: fast is more than two nodes behind slow, which means fast will eventually catch up to slow in such a way that this case resolves into either case 2 or case 3, which means the nodes will still meet

The important takeaway above is that fast will never jump slow. The two nodes must meet if there is a cycle.

LC 142. Linked List Cycle II (✓) ★★

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Notice that you should not modify the linked list.

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                slow = head
                
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                    
                return slow
            
        return None

Determining whether or not a cycle exists is a pre-requisite for coming up with a solution for this problem. We can effectively tweak our solution to LC 141. Linked List Cycle in order to come up with the solution above:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                return True
            
        return False

That is, as the highlighted lines above suggest, we need to do something once we actually have determined that we have a cycle. What should we do? The following image (from this YouTube video) may help:

This image shows how X units are traveled before the cycle starts. We'll assume we're moving in a counterclockwise direction once we've entered the cycle. We can't know for sure how many times fast might travel the full cycle of Y + Z units before slow enters the cycle. The important observation is that eventually there will come a revolution where fast starts at the beginning of the cycle and slow joins the cycle during this revolution.

How many units does fast travel before it meets slow? Where exactly fast is when slow enters the cycle does not matter — the important point is that it must travel the full distance of Z + Y + Z before coming back around to meet slow. In total, then, fast travels a distance of X + R(Z + Y) + (Z + Y + Z), where R(Z + Y) denotes that fast has traveled R full cycle lengths before it starts its last revolution before slow enters the cycle. Since slow travels a total distance of X + Z, we have the following useful equation (we discard R(Z + Y) during the second simplifying step due to its cyclical nature):

2(X + Z) = X + R(Z + Y) + (Z + Y + Z)

2X + 2Z = X + 2Z + Y

X = Y

What the above equation means in the context of this problem is that all we really need to do to actually return the node at which the cycle starts is reset one of the nodes to start at the head and then just move them together in unison until they meet again (at the beginning of the cycle). We can then return the desired node.

LC 876. Middle of the Linked List (✓)

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        return slow

This uses the classic fast-slow technique. For an odd-length list:

Start
  x
12345
s
f

After first iteration
  x
12345
 s
  f

After second iteration
  x
12345
  s
    f

Done! And we're fortunate for even-length lists since we're asked to return the second middle node:

Start
   x
123456
s
f

After first iteration
   x
123456
 s
  f

After second iteration
   x
123456
  s
    f

After third iteration
   x
123456
   s
      f

Things work out nicely in this case. What if, however, we were asked to return the first middle node? Then we could make use of a prev pointer to basically lag behind the slow pointer. Which node we returned at the end would depend on where fast was (not null for odd-length lists and null for even-length lists):

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
            
        return prev if not fast else slow

LC 83. Remove Duplicates from Sorted List (✓) ★

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        while curr and curr.next:
            if curr.val == curr.next.val:
                curr.next = curr.next.next
            else:
                curr = curr.next
                
        return head

The solution above is probably less obvious than it should seem at first glance, but it cleverly avoids the need to use two pointers (slow and fast) because of how curr is manipulated. Three observations worth making:

It only makes sense to test for duplicates if we have at least two nodes for comparison. Hence, we only look to make modificates while curr and curr.next both exist.
If we have node1 -> node2 -> ..., then how can we effectively "delete" node2 from this list? We do so in the following standard way (i.e., using its previous node, node1, to skip it): node1.next = node1.next.next. Such an assignment means node2 is "skipped" from node1 and effectively removed from the chain. In the context of this problem, if curr.val == curr.next.val, then we want to remove curr.next from the list, and we do so in the standard way: curr.next = curr.next.next.
If curr and the next node have different values, then we simply advance curr in the standard way: curr = curr.next. Note how curr is only ever advanced/reassigned when we encounter different values. Since the list is already sorted, this ensures the resultant list only contains distinct values, as desired.

The solution above is elegant, straightforward, and uncomplicated; however, if we wanted to use two pointers, then how would we do so? We could use lag and lead as slow and fast pointers, respectively. The idea is that lag always points to the first non-duplicate value we find, and it "lags" behind lead until lead discovers a value for which lead.val != lag.val, whereby lag.next now points to this new non-duplicate node/value, and we update lag to point to where lead was when this non-duplicated value was discovered.

The main potential "gotcha" with this approach occurs at the end of the list. If there are duplicates at the end of the list, then lag points at the first duplicate value and lead never discovers a non-duplicate value. Thus, if we don't manually make the assignment lag.next = None after lead has iterated through the entire list, then we run the risk of accidentally including all duplicated values at the end of the list.

Here's the working solution for this two pointer approach:

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        
        lead = head
        lag = head
        
        while lead:
            lead = lead.next
            if lead and lead.val != lag.val:
                lag.next = lead
                lag = lead
                
        lag.next = None
                
        return head

The primary difference between the solutions is how the duplicate nodes are being deleted. In the first approach, duplicate nodes are being deleted as they are encountered. A duplicate node is deleted as soon as it's encountered: curr.next = curr.next.next. In the second approach, all duplicate nodes are deleted as soon as a non-duplicate value is found: lag.next = lead.

LC 2095. Delete the Middle Node of a Linked List (✓)

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        sentinel = ListNode(-1)
        sentinel.next = head
        prev = sentinel
        slow = fast = head
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = prev.next.next
        return sentinel.next

Since slow will point to the middle node after the while loop terminates above, what we really need is for the node prior to slow to skip it, effectively deleting it: prev.next = prev.next.next.

LC 19. Remove Nth Node From End of List (✓)

Given the head of a linked list, remove the n^th node from the end of the list and return its head.

Follow up: Could you do this in one pass?

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        sentinel = ListNode(-1)
        sentinel.next = head
        prev = sentinel
        slow = fast = head
        
        for _ in range(n):
            fast = fast.next
            
        while fast:
            prev = slow
            slow = slow.next
            fast = fast.next
            
        prev.next = prev.next.next
        return sentinel.next

The idea: advance fast $n$ nodes past slow so that there are always $n$ nodes between these pointers. When the while loop terminates, slow will be $n$ units behind fast or $n$ nodes from the end of the list, as desired. But we need to delete this node, hence the use of the prev pointer.

LC 82. Remove Duplicates from Sorted List II (✓) ★

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        sentinel = ListNode(-1)
        sentinel.next = head
        prev = sentinel
        curr = head
        while curr and curr.next:
            if curr.val == curr.next.val:
                while curr and curr.next and curr.val == curr.next.val:
                        curr.next = curr.next.next
                curr = curr.next
                prev.next = curr
            else:
                prev = curr
                curr = curr.next
        
        return sentinel.next

This problem is obviously quite similar to LC 83. Remove Duplicates from Sorted List, but the requirement to remove all numbers that have duplicates basically makes this a completely different problem. As always, it's amazing how helpful a drawing that solves a basic example can be:

The picture above illustrates how prev and curr need to be moved together in unison when there are not duplicates; however, if duplicates are encountered, then we can employ a strategy similar to that used in LC 83, where we effectively "delete" duplicates as they are encountered by changing the next attribute for curr: curr.next = curr.next.next. The twist with this problem is that we want to retain none of the duplicate values once we've encountered a non-duplicate value. As the figure suggests, one way of achieving this is to move curr past the last duplicate, and then change the next attribute for prev to point to the updated, non-duplicate curr node. This effectively cuts out all duplicate values, and prev itself is only ever updated when non-duplicate values are adjacent.

LC 1721. Swapping Nodes in a Linked List (✓)

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the k^th node from the beginning and the k^th node from the end (the list is 1-indexed).

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        left = right = null_checker = head
        for _ in range(k - 1):
            left = left.next
            null_checker = null_checker.next
        
        while null_checker.next:
            right = right.next
            null_checker = null_checker.next
            
        left.val, right.val = right.val, left.val
        return head

The fast-slow pointer approach above works great for this problem where only the node values need to be swapped. But switching the nodes themselves requires a little bit more work:

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def swap_nodes(prev_left, prev_right):
            if not prev_left or not prev_right \
                or not prev_left.next or not prev_right.next \
                    or prev_left.next == prev_right.next:
                        return
                    
            left = prev_left.next
            right = prev_right.next
            prev_left.next, prev_right.next = right, left
            right.next, left.next = left.next, right.next
            
        sentinel = ListNode(-1)
        sentinel.next = head
        prev_left = prev_right = sentinel
        null_checker = head
        
        for _ in range(k - 1):
            prev_left = prev_left.next
            null_checker = null_checker.next
            
        while null_checker.next:
            prev_right = prev_right.next
            null_checker = null_checker.next
        
        swap_nodes(prev_left, prev_right)
        return sentinel.next

See more about this approach in the "swap two nodes" template section.

Reverse a linked list

Remarks

The template below is the simplest way of reversing a portion of a linked list from a given node (potentially the entire list if given the head of a linked list). One important observation is that the reversed portion is effectively severed from the rest of the list.

For example:

ex = [1,2,3,4,5,6]        # integer array
head = arr_to_ll(ex)      # convert integer array to linked list
print(fn(head.next.next)) # start reversal from node 3
                          # outcome: 6 -> 5 -> 4 -> 3 -> None

Suppose the outcome above is not desirable and instead we wanted the reversal to be incorporated into the original list: 1 -> 2 -> 6 -> 5 -> 4 -> 3 -> None. We clearly need to preserve the node previous to the node where the reversal starts (i.e., the 2 node is a sort of "connecting" node that needs to be preserved). Solving this problem is outside the scope of this template; however, the subsequent template for reversing k nodes of a linked list does solve this problem.

def fn(node):
    prev = None
    curr = node
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

Examples

LC 206. Reverse Linked List (✓)

Given the head of a singly linked list, reverse the list, and return the reversed list.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
            
        return prev

This is a classic linked list "pointer manipulation" problem, and the approach above is the conventionally efficient approach, where next_node effectively serves as a temporary variable (so we don't lose the linked list connection when we make the assignment curr.next = prev).

One thing worth noting about this conventional approach is how the reversed segment is effectively broken off from the rest of the list if the reversal is started on a node other than the linked list's head. For example, consider the list 1 -> 2 -> 3 -> 4 -> 5 -> None. If we start the reversal at node 3, then reversing 3 -> 4 -> 5 gives us 5 -> 4 -> 3, but what happens to the rest of the list? We lose the connection. Hence, starting from the head of the original linked list we have 1 -> 2 -> 3 -> None while starting from the head of the reversed segment gives us 5 -> 4 -> 3 -> None.

Python's support for tuple packing/unpacking and multiple assignment means we can simplify the reversal in a pretty dramatic fashion:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
            
        return prev

Here's a quick breakdown:

Tuple Packing: The expression on the right side of the assignment, prev, curr, curr.next, effectively creates a tuple of these three references/values. This happens before any assignments are made, which means the original values are preserved in the tuple.
Multiple Assignment: The left-hand side of the assignment has three variables, curr.next, prev, curr, awaiting new values. Python will assign the values from the tuple on the right-hand side to these variables in a left-to-right sequence.
Tuple Unpacking: The assignment unpacks the values stored in the tuple into the variables on the left. This happens simultaneously, so the operations do not interfere with each other. Specifically:
- curr.next is assigned prev. This reverses the pointer/link of the current node to point to the previous node, effectively starting the reversal of the linked list.
- prev is assigned curr. This moves the prev pointer one node forward to the current node, which after the assignment, becomes the new "previous" node.
- curr is assigned curr.next (the original curr.next before any changes). This moves the curr pointer one node forward in the original list, to continue the reversal process on the next iteration.

The one-liner above is slick and may be useful for problems where reversing the linked list (or part of it) is naturally part of the solution (e.g., LC 2130. Maximum Twin Sum of a Linked List).

LC 24. Swap Nodes in Pairs (✓)

Given a linked list, swap every two adjacent nodes and return its head.

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        sentinel = ListNode(-1)
        sentinel.next = head
        
        prev = sentinel
        left = head
        
        while left and left.next:
            right = left.next
            next_left = left.next.next
            right.next = left
            left.next = next_left
            prev.next = right
            prev = left
            left = next_left
            
        return sentinel.next

As with most linked list problems, this problem becomes much easier if we take a moment to draw what happens for a general pair swap:

The solution above naturally presents itself from this figure.

LC 2130. Maximum Twin Sum of a Linked List (✓) ★★

In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        def reverse(node):
            prev = None
            curr = node
            while curr:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev
        
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        left = head
        right = reverse(slow)
        ans = 0
        
        while right:
            ans = max(ans, left.val + right.val)
            left = left.next
            right = right.next
            
        return ans

This is a fun one: Find the middle of the linked list, reverse the rest of the linked list, and then iterate back towards the middle from the head as well as from the end that was just reversed (i.e., the head of the newly reversed portion of the linked list), maintaining the maximum pairwise sum as you go. Small potential "gotcha": after the reversal, slow points to the second middle node of the linked list (since the total number of nodes is always even), which means it's a single node past what we need to iterate through on the left hand side. The last while loop condition needs to be while right; otherwise, if we used while left, then trying to access right.val would eventually throw an error because the reversed segment on the right would be exhausted while there's a single node left on the left side.

LC 234. Palindrome Linked List (✓)

Given the head of a singly linked list, return true if it is a palindrome.

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        def reverse(node):
            prev = None
            curr = node
            while curr:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev
        
        if not head or not head.next:
            return True
        
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        left = head
        right = reverse(slow)
        
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        
        return True

The solution above is likely the intended solution for this problem even though destroying the original linked list is not a very desirable side effect. It's also nice that we do not have to consider the length of the list when making the reversal. An odd-length list like 1 -> 2 -> 3 -> 2 -> 1 means that once the reversal occurs we get 1 -> 2 -> 3 starting from the original head and 1 -> 2 -> 3 starting from the head of the reversed segment. An even-length list like 1 -> 2 -> 2 -> 1 means after the reversal we have 1 -> 2 -> 2 starting from the head of the original list and 1 -> 2 starting from the head of the reversed segment. This is why it's important that our last while loop uses the condition while right as opposed to while left.

If the side effect mentioned above is not allowed, then we can use the "reverse k nodes in-place" template to determine whether or not the list's values are palindromic and also restore the list itself (although the logic becomes a bit more complicated):

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        def reverse_k_nodes(prev, k):
            if not prev.next or k < 2:
                return prev.next
            
            rev_start = prev.next
            next_node = rev_start.next
            rev_end = rev_start
            
            count = 1
            while count <= k - 1 and next_node:
                rev_start.next = next_node.next
                next_node.next = prev.next
                prev.next = next_node
                next_node = rev_start.next
                count += 1
            
            return rev_end
        
        if not head or not head.next:
            return True
        
        sentinel = ListNode(-1)
        sentinel.next = head
        prev = sentinel
        slow = fast = head
        char_count = 1
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
            char_count += 1
        
        middle = slow if fast else prev
        reverse_k_nodes(middle, char_count)
        right = middle.next
        
        left = head
        for _ in range(char_count - 1):
            if left.val != right.val:
                reverse_k_nodes(middle, char_count)
                return False
            left = left.next
            right = right.next

        # this reversal optional since values are palindromic after the in-place reversal
        reverse_k_nodes(middle, char_count)
        return True

LC 2487. Remove Nodes From Linked List★★

You are given the head of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the head of the modified linked list.

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node):
            prev = None
            curr = node
            while curr:
                curr.next, prev, curr = prev, curr, curr.next
            return prev
        
        rev_head = reverse(head)
        sentinel = ListNode(float('-inf'))
        sentinel.next = rev_head
        
        prev = sentinel
        curr = rev_head
        while curr:
            if prev.val > curr.val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next
        
        return reverse(sentinel.next)

The issue at the beginning of the problem lies in how the pointers restrict how we can manage what happens with decreasing values. Reversing the linked list as a pre-processing step is an effective strategy here. Then we can simply adjust pointers as needed to ensure our linked list is weakly increasing. Then as a final step we return the reversal of that linked list.

LC 2816. Double a Number Represented as a Linked List (✓)

You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes.

Return the head of the linked list after doubling it.

class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node):
            prev = None
            curr = node
            while curr:
                curr.next, prev, curr = prev, curr, curr.next
            return prev
        
        rev_head = reverse(head)
        carried = 0
        
        sentinel = ListNode(-1)
        sentinel.next = rev_head
        curr = sentinel.next
        while curr:
            doubled = carried + curr.val * 2
            new_val = doubled % 10
            carried = doubled // 10
            curr.val = new_val
            curr = curr.next
            
        doubled_head = reverse(sentinel.next)
        
        if carried:
            new_head = ListNode(carried)
            new_head.next = doubled_head
            return new_head
        else:
            return doubled_head

The basic idea above is to first reverse the list so we can more easily manage the updating of node values — values range from 0 through 9 which means the doubled values range from 0 through 18, where the original value being 5 or more means having a doubled value in the range 10-18, which requires carrying.

We perform the needed value updates and maintain the number being carried along the way. Once we're done, we reverse the new list. If carried is 0, then we're done, but if carried is not 0, then whatever carried is should become the first value in our new list.

The editorial for this problem is great. Reversing twice as done above is not necessary even though it is sufficient. There's a really slick one-pointer approach that takes advantage of how "carrying" works in terms of whether or not we ever need to update a node's value.

Reverse k nodes of a linked list in-place

What is the purpose of this template?

The purpose of the template, of course, is to reverse k nodes of a linked list in-place. But, as this post notes (the post that originally motivated this template), the template below does not break off the section to be reversed (this is what happens with the conventional reversal, as detailed in the previous template).

The template below leaves the start node of the section linked to the rest of the list and moves the remaining nodes one by one to the front. This results in the k-length section (starting at the start node) being reversed, the original start node being the end node of the reversed section, and the original start node being connected to the rest of the list instead of being severed or pointing to None. The next remark provides some intuition as to how this actually works.

What is the intuition behind how and why this template works?

The core idea is actually somewhat simple: given a prev node that precedes the start node for the k-length section to be reversed, we effectively move the k - 1 nodes that follow the start so that they now come before the start node. One at a time. Suppose we want the section 3 -> 4 -> 5 -> 6 to be reversed in the following list (spaces added to emphasize section being reversed):

1 -> 2 ->   3 -> 4 -> 5 -> 6   -> 7 -> 8 -> 9 -> None

The desired outcome would then be the following list:

1 -> 2 ->   6 -> 5 -> 4 -> 3   -> 7 -> 8 -> 9 -> None

Above, we see that k = 4, prev is node 2, and node 3 is the start of the section to be reversed. Our template stipulates that nodes 4, 5, 6, which originally follow node 3, will now be moved to come before node 3. One at a time:

-> 2 ->   3 -> 4 -> 5 -> 6   -> 7 -> 8 -> 9 -> None   # start
-> 2 ->   4 -> 3 -> 5 -> 6   -> 7 -> 8 -> 9 -> None   # after iteration 1
-> 2 ->   5 -> 4 -> 3 -> 6   -> 7 -> 8 -> 9 -> None   # after iteration 2
-> 2 ->   6 -> 5 -> 4 -> 3   -> 7 -> 8 -> 9 -> None   # after iteration 3

Hence, k - 1 iterations are needed to reverse the k-length section in-place, and we conclude by returning the end node for the reversed section, node 3 in this case. Here's a more colorful illustration of what things look like for each iteration:

The top part of the image shows the initial list and which four nodes need to be reversed, where the red numbering 1, 2, and 3 indicates where the nodes end up after that many iterations have taken place. The actual node coloring scheme:

Red 2: This fixed node denotes the node preceding where the reversal starts.
Magenta 3: This fixed coloring denotes the node where the reversal starts (and also the node returned at the end).
Orange nodes: The orange node is always the "next node" to be moved to the front (i.e., next_node in the template).
White nodes: This coloring indicates the nodes that have already been processed. The last iteration shows how the node where the reversal started concludes with its proper positioning at the end of the reversed segment.

The image above, particularly the top part of the image with the initial list and the arrow indicators which show how each node moves for each iteration, provides an intuition for how and why the template works. The following image shows the mechanics in more detail:

def reverse_k_nodes(prev, k):
    if not prev.next or k < 2:
        return prev.next
    
    rev_start = prev.next
    next_node = rev_start.next
    rev_end = rev_start
    
    count = 1 
    while count <= k - 1 and next_node:
        rev_start.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node
        next_node = rev_start.next
        count += 1
        
    return rev_end

Examples

LC 92. Reverse Linked List II (✓) ★★

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 <= m <= n <= length of list

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        def reverse_k_nodes(prev, k):
            if not prev.next or k < 2:
                return prev.next
            
            rev_start = prev.next
            next_node = rev_start.next
            rev_end = rev_start
            
            count = 1
            while count <= k - 1 and next_node:
                rev_start.next = next_node.next
                next_node.next = prev.next
                prev.next = next_node
                next_node = rev_start.next
                count +=1
                
            return rev_end
        
        sentinel = ListNode(-1)
        sentinel.next = head
        prev = sentinel
        
        for _ in range(left - 1):
            prev = prev.next
            
        reverse_k_nodes(prev, right - left + 1)
        return sentinel.next

The template for reversing k nodes in-place was born out of the efforts to find a nice solution for this problem. The main potential "gotcha" is when left = 1, where the prev we need to feed into reverse_k_nodes needs to be a sentinel node.

LC 2074. Reverse Nodes in Even Length Groups (✓) ★★★

You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

The 1st node is assigned to the first group.
The 2nd and the 3rd nodes are assigned to the second group.
The 4th, 5th, and 6th nodes are assigned to the third group, and so on. Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse_k_nodes(prev, k):
            if not prev.next or k < 2:
                return prev.next
            
            rev_start = prev.next
            next_node = rev_start.next
            rev_end = rev_start
            
            count = 1
            while count <= k - 1 and next_node:
                rev_start.next = next_node.next
                next_node.next = prev.next
                prev.next = next_node
                next_node = rev_start.next
                count += 1
                
            return rev_end
        
        if not head or not head.next:
            return head
        
        sentinel = ListNode(-1)
        sentinel.next = head
        connector = sentinel
        curr = head
        grp_size = count = 1
        
        while curr:
            if grp_size == count or not curr.next:
                if count % 2 == 0:
                    curr = reverse_k_nodes(connector, count)
                connector = curr
                count = 0
                grp_size += 1
                
            count += 1
            curr = curr.next
            
        return sentinel.next

This is such an excellent problem. The solution above, originally inspired by this one, is brilliant in how it fulfills the problem's requirements and deftly utilizes reversing a specified number of nodes in place.

How does the solution logic work apart from reverse_k_nodes? First, recall what reverse_k_nodes does apart from reversing k nodes in-place: it returns the last node of the reversed segment. With this in mind, there are a few key points to highlight to illustrate how and why the solution above works:

We will maintain a connector node that allows us to keep all groups of the list connected. This node will always directly precede the beginning of a group.
It's easy to get lost in keeping track of the odd or even groups, especially since the last group has to be treated differently than all the rest. A clever way of treating everything in a uniform fashion is to keep track of what the current group's full size would be, grp_size as well as the current node count, count, as we move our way through the list.
How do we move from one group to another effectively? We do so by determining whether or not the current node count equals the full size of the current group (i.e., grp_size == count) or if there aren't any nodes left to process, in which case we are done iterating and need to process the last group (i.e., not curr.next).

In both cases mentioned above, if the number of nodes in the group is even, then we need to reverse all these nodes in the group, and then continue on. Since reverse_k_nodes returns the last node of the newly reversed segment, we can set curr equal to this function's return value. What remains is to set connect = curr before moving to the next group. We also add 1 to the next group's size, grp_size += 1, and we reset count = 0 because we add 1 to count after the if block no matter what happens.

LC 25. Reverse Nodes in k-Group (✓)

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.

Follow up:

Could you solve the problem in $O(1)$ extra memory space?
You may not alter the values in the list's nodes, only nodes itself may be changed.

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def reverse_k_nodes(prev, k):
            if not prev.next or k < 2:
                return prev.next
            
            rev_start = prev.next
            next_node = rev_start.next
            rev_end = rev_start
            
            count = 1
            while count <= k - 1 and next_node:
                rev_start.next = next_node.next
                next_node.next = prev.next
                prev.next = next_node
                next_node = rev_start.next
                count += 1
            
            return rev_end
        
        if not head or not head.next:
            return head
        
        sentinel = ListNode(-1)
        sentinel.next = head
        connector = sentinel
        curr = head
        grp_size = k
        count = 1
            
        while curr:
            if count == k:
                curr = reverse_k_nodes(connector, count)
                count = 0
                connector = curr
            count += 1
            curr = curr.next
            
        return sentinel.next

This problem is very similar to LC 2074. Reverse Nodes in Even Length Groups. In fact, this problem is actually easier than that problem!

Swap two nodes

Remarks

TLDR: Don't overthink what seems like the tricky edge case of swapping adjacent nodes. The lengthy initial condition simply ensures we don't try to swap nodes that don't exist or identical nodes in memory.

Let left and right be the nodes we want to swap. We will need the nodes prior to left and right to facilitate the node swapping. Let these nodes be prev_left and prev_right, respectively. Most node swaps will look something like the following:

That is, as the figure suggests, we will first make the assignment prev_left.next = right and then prev_right.next = left. Now we need right.next to point to what left.next was pointing to, and we need left.next to point to what right.next was pointing to. We can do this without a temporary variable in Python: right.next, left.next = left.next, right.next.

Great! But what about the seemingly tricky case when nodes are adjacent? The really cool thing is that the template handles this case seamlessly. For the example figure above, consider what would happen if we tried swapping nodes 4 and 5:

The assignment prev_left.next = right behaves as expected, but the assignment prev_right.next = left seems like it could cause some issues because we have effectively created a self-cycle. But the beautiful thing is how this is exploited to restore the list in the next set of assignments:

right.next, left.next = left.next, right.next

When nodes left and right are adjacent, we want right.next to point to left. The assignment right.next = left.next accomplishes exactly this because the self-cycle means left.next actually points to itself (i.e., left). The subsequent assignment left.next = right.next effectively removes the self-cycle and restores the list, resulting in the adjacent left and right nodes being swapped, as desired.

def swap_nodes(prev_left, prev_right):
    if not prev_left or not prev_right \
        or not prev_left.next or not prev_right.next \
            or prev_left.next == prev_right.next:
        return
    
    left = prev_left.next
    right = prev_right.next
    prev_left.next, prev_right.next = right, left
    right.next, left.next = left.next, right.next

Examples

LC 24. Swap Nodes in Pairs (✓)

Given a linked list, swap every two adjacent nodes and return its head.

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def swap_nodes(prev_left, prev_right):
            if not prev_left or not prev_right \
                or not prev_left.next or not prev_right.next \
                    or prev_left.next == prev_right.next:
                return
            
            left = prev_left.next
            right = prev_right.next
            prev_left.next, prev_right.next = right, left
            right.next, left.next = left.next, right.next
        
        if not head or not head.next:
            return head
        
        sentinel = ListNode(-1)
        sentinel.next = head
        prev_left = sentinel
        prev_right = sentinel.next
        
        while prev_left and prev_right:
            swap_nodes(prev_left, prev_right)
            prev_left = prev_right
            prev_right = prev_right.next
            
        return sentinel.next

The while loop condition conveys that we are only ever interested in trying to swap two nodes if both of their predecessors exist. Since this problem involves swapping pairs of nodes (i.e., the nodes are adjacent), the prev_left condition in the while loop is actually unnecessary (prev_right can only be true if prev_left is also true).

The main potential "gotcha" occurs after the swapping of the nodes. Note that prev_left and prev_right are never reassigned during the node swapping but their next attributes are. This means we need to be somewhat careful when making reassignments. As always, a drawing of a simple example can be immensely helpful:

Now the solution above basically suggests itself.

LC 1721. Swapping Nodes in a Linked List (✓)

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the k^th node from the beginning and the k^th node from the end (the list is 1-indexed).

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def swap_nodes(prev_left, prev_right):
            if not prev_left or not prev_right \
                or not prev_left.next or not prev_right.next \
                    or prev_left.next == prev_right.next:
                        return
                    
            left = prev_left.next
            right = prev_right.next
            prev_left.next, prev_right.next = right, left
            right.next, left.next = left.next, right.next
            
        sentinel = ListNode(-1)
        sentinel.next = head
        prev_left = prev_right = sentinel
        null_checker = head
        
        for _ in range(k - 1):
            prev_left = prev_left.next
            null_checker = null_checker.next
            
        while null_checker.next:
            prev_right = prev_right.next
            null_checker = null_checker.next
        
        swap_nodes(prev_left, prev_right)
        return sentinel.next

The motivation for the "swap two nodes" template really comes from this problem. Coming up with the template is the harder part — now all we have to do is work on identifying which nodes precede the left and right nodes.

General

Problems

LC 203. Remove Linked List Elements (✓)

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        sentinel = ListNode(-1)
        sentinel.next = head
        prev = sentinel
        curr = prev.next
        
        while curr:
            if curr.val == val:
                prev.next = prev.next.next
            else:
                prev = curr
            curr = curr.next
        
        return sentinel.next

The key idea is that we only ever actually move prev when a non-val number is encountered; otherwise, we simply skip or "delete" nodes via prev.next = prev.next.next while constantly moving forward through the list with curr = curr.next.

LC 1290. Convert Binary Number in a Linked List to Integer (✓)

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        curr = head
        ans = curr.val
        
        while curr.next:
            ans = ans * 2 + curr.next.val
            curr = curr.next
            
        return ans

The idea behind the clever solution above is easier to understand if we first consider a simple base-10 number by itself: 4836. What this means in a base-10 system is the following (the powers of 10 indicate positional significance of the different numerals): $4\cdot 10^3 + 8\cdot 10^2 + 3\cdot 10^1 + 6\cdot 10^0 = (4836)_{10}$ .

How does this help with this problem? Well, consider how the number 4836 could be obtained if we encountered the digits one at a time, left to right:

ans = 4
    = 4 * 10 + 8      -> (48)
    = 48 * 10 + 3     -> (483)
    = 483 * 10 + 6    -> (4836)
    = 4836

The same thing is happening in this problem with respect to another base, namely base 2. For example, consider how the process above would look for the following number (in base 2): 101101:

ans = 1
    = 1 * 2 + 0     -> (2)
    = 2 * 2 + 1     -> (5)
    = 5 * 2 + 1     -> (11)
    = 11 * 2 + 0    -> (22)
    = 22 * 2 + 1    -> (45)
    = 45

The solution above is elegant in exploiting this instead of doing something else unnecessary like reversing the list and then updating the answer as we go along (which might be the first solution idea):

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        def reverse(node):
            prev = None
            curr = node
            while curr:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev
        
        curr = reverse(head)
        ans = 0
        pos = 0
        
        while curr:
            if curr.val == 1:
                ans += 2 ** pos
            curr = curr.next
            pos += 1
        
        return ans

LC 328. Odd Even Linked List (✓) ★★

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        odd = head
        even = odd.next
        even_list_head = even
        
        while even and even.next:
            odd.next = odd.next.next
            even.next = even.next.next
            odd = odd.next
            even = even.next
            
        odd.next = even_list_head
        return head

This is a great problem, but it is easy to overthink it and get bogged down in how the "node swapping" will work; in fact, that's the first problem! There is no node swapping! It's easy to fall into the trap of thinking we'll need to swap nodes to make the solution here work. A much more straightforward solution exists (i.e., the one above) if we can step outside the normal way of thinking here: what if we basically just created two lists, the odd list of the odd-index nodes and the even list of the even-index nodes? Then we could attach the even list to the odd list and call it a day.

And the idea above is completely possible. It just takes a little bit of imagination to execute it effectively. Specifically, what we have to be okay with (even though it may not seem okay in the moment) is effectively skipping or "deleting" the even-index nodes while dynamically creating the odd list and the same for the odd-index nodes while dynamically creating the even list.

Note that the while loop condition above is critical for the solution approach described above to work. We only care to continue building our lists so long as there are nodes that need to be repositioned; that is, we should only continue building our lists while an odd-indexed node appears after an even-indexed node. So long as this is true, we have work to do.

Matrices

Calculate value in a 2D matrix given its index

Remarks

index // n: This performs integer division of index by n, where the result is the number of times n fully goes into index. Why does this give us the row number? Because, for every row, there are n elements; hence, after every n elements, we move on to the next row.
index % n: This finds the remainder when index is divided by n, where this remainder corresponds to the column index because it tells us how many places into the current row we are.

def index_to_value(matrix, index):
    n = len(matrix[0])
    row_pos = index // n
    col_pos = index % n
    return matrix[row_pos][col_pos]

Examples

LC 74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def index_to_mat_val(index):
            row = index // n
            col = index % n
            
            return matrix[row][col]
            
        m = len(matrix)
        n = len(matrix[0])
        
        left = 0
        right = m * n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            val = index_to_mat_val(mid)
            
            if target < val:
                right = mid - 1
            elif target > val:
                left = mid + 1
            else:
                return True
            
        return False

Sliding window

Variable window size

Remarks

The general algorithm behind the sliding window pattern (variable width) is as follows:

Define window boundaries: Define pointers left and right that bound the left- and right-hand sides of the current window, respectively, where both pointers usually start at 0.
Add elements to window by moving right pointer: Iterate over the source array with the right bound to "add" elements to the window.
Remove elements from window by checking constraint and moving left pointer: Whenever the constraint is broken, "remove" elements from the window by incrementing the left bound until the constraint is satisfied again.

Note the usage of the non-strict inequality left <= right in the while loop — this makes sense for problems where a single-element window is valid; however, the inequality should be strict (i.e., left < right) for problems where a single-element window does not make sense.

Template with comments

def fn(arr):
    # initialize left boundary, window, and answer variables
    left = curr = ans = 0

    # initialize right boundary
    for right in range(len(arr)):

        # logic for adding element arr[right] to window
        curr += nums[right]

        # resize window if window condition/constraint is invalid
        while left <= right and WINDOW_CONDITION_BROKEN # (e.g., curr > k):
            
            # logic to remove element from window
            curr -= nums[left]
            
            # shift window
            left += 1

        # logic to update answer
        ans = max(ans, right - left + 1)
    
    return ans

def fn(arr):
    left = curr = ans = 0
    for right in range(len(arr)):
        curr += nums[right]
        while left <= right and WINDOW_CONDITION_BROKEN # (e.g., curr > k):
            curr -= nums[left]
            left += 1
        ans = max(ans, right - left + 1) # length of "valid" window
    return ans

Examples

Longest subarray of positive integer array with sum not greater than k (✓)

def find_length(nums, k):
    # early return (minor optimization)
    if k <= 0:
        return -1
    
    left = curr = ans = 0
    for right in range(len(nums)):
        curr += nums[right]
        while left <= right and curr > k:
            curr -= nums[left]
            left += 1
            
        ans = max(ans, right - left + 1)
        
    return ans

Note the important above of the non-strict inequality left <= right: if, say k = 8, and nums = [9,9,9], then the final answer should be 0, but if we use left < right, then the (incorrect) reported answer would be 1.

Time: $O(n)$ . The for loop can iterate a maximum number of $n$ times, where n = len(nums). The same is true for the while loop. Basically right is progressed $n$ units while left is progressed a maximum of $n$ units, meaning our overall time complexity is $O(2n) = O(n)$ .

Space: $O(1)$ . The space required does not scale with the input here, which means the space required is constant.

Longest substring of 1's given binary string and one possible 0 flip (✓)

def find_length(s):
    left = ans = curr = 0
    for right in range(len(s)):
        if s[right] == '0':
            curr += 1
            
        while left <= right and curr > 1:
            if s[left] == '0':
                curr -= 1
            left += 1
            
        ans = max(ans, right - left + 1)
    
    return ans

Above, curr denotes the current number of zeroes in the window.

Time: $O(n)$ . The right pointer moves $n$ units, where n = len(s), and left moves a maximum total of $n$ units, meaning the overall time complexity is $O(2n) = O(n)$ .

Space: $O(1)$ . The space used is constant proportional to the input.

LC 713. Subarray Product Less Than K (✓) ★

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k == 0:
            return 0

        left = ans = 0
        curr = 1
        for right in range(len(nums)):
            curr *= nums[right]
            while left <= right and curr >= k:
                curr /= nums[left]
                left += 1
                
            ans += (right - left + 1)
            
        return ans

For a valid sliding window [left, right] that satisfies the condition and constraints, note that adding right - left + 1 to ans effectively adds the total number of subarrays in the range [left, right] that end at right, inclusive.

This is a nifty trick you can use when the subarrays in question exhibit some sort of "monotonic" property; in this case, the product for positive integers uniformly increases as we add more positive integers to multiply (i.e., as the window becomes larger).

Time: $O(n)$ . The right pointer moves a maximum of $n$ units, where n = len(nums), and left moves a maximum of $n$ units as well, meaning our overall time complexity is $O(2n) = O(n)$ .

Space: $O(1)$ . The space used does not grow in proportion to the size of the input. It is constant.

LC 1004. Max Consecutive Ones III (✓) ★

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = curr = ans = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                curr += 1
            while left <= right and curr > k:
                if nums[left] == 0:
                    curr -= 1
                left += 1
            ans = max(ans, right - left + 1)
            
        return ans

The hardest part about this problem is arguably the clever manipulaton of the left pointer. Ensuring curr is only decremented when left is currently pointing at 0 and then incrementing the left counter is the way to go. Doing this out of order (e.g., trying to increment left before decrementing curr) can lead to some headaches.

LC 209. Minimum Size Subarray Sum (✓)

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [nums_l, nums_l+1, ..., nums_r-1, nums_r] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        MAX_NUMS_LENGTH = 10 ** 5 + 1
        left = 0
        curr = 0
        ans = MAX_NUMS_LENGTH
        
        for right in range(len(nums)):
            curr += nums[right]
            while left <= right and curr >= target:
                ans = min(ans, right - left + 1)
                curr -= nums[left]
                left += 1
            
        return 0 if ans == MAX_NUMS_LENGTH else ans

Sometimes the standard template needs to be modified slightly. This problem is clearly asking to be solved via sliding window, but the most natural way of solving the problem does not conform completely to the template. That's okay. Specifically, we want the condition of the window to be met before we remove any elements and/or update the answer.

LC 1208. Get Equal Substrings Within Budget (✓)

You are given two strings s and t of the same length. You want to change s to t. Changing the ith character of s to ith character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        def char_diff(char1, char2):
            return abs(ord(char1) - ord(char2))
        
        left = curr = ans = 0
        for right in range(len(t)):
            curr += char_diff(t[right], s[right])
            while left <= right and curr > maxCost:
                curr -= char_diff(t[left], s[left])
                left += 1
            
            ans = max(ans, right - left + 1)
            
        return ans

The main idea here is that s is purely for reference while the sliding window operates by traversing t.

LC 3090. Maximum Length Substring With Two Occurrences★★

Given a string s, return the maximum length of a substring such that it contains at most two occurrences of each character.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        lookup = defaultdict(int)
        left = ans = 0
        
        for right in range(len(s)):
            curr_char = s[right]
            lookup[curr_char] += 1
            while left <= right and lookup[curr_char] > 2:
                prev_char = s[left]
                lookup[prev_char] -= 1
                left += 1
                
            ans = max(ans, right - left + 1)
            
        return ans

The idea is effectively to use a hash map to track the frequency of characters as we encounter them — as soon as a character occurs more than 2 times (the right boundary), move the left boundry until a valid window is attained (subtracting out the character frequencies from the hash map along the way).

Note how easy it is to extend this solution to a number k >= 2:

class Solution:
    def maximumLengthSubstring(self, s: str, k: int) -> int:
        lookup = defaultdict(int)
        left = ans = 0
        
        for right in range(len(s)):
            curr_char = s[right]
            lookup[curr_char] += 1
            while left <= right and lookup[curr_char] > k:
                prev_char = s[left]
                lookup[prev_char] -= 1
                left += 1
                
            ans = max(ans, right - left + 1)
            
        return ans

That's pretty much the only change that's needed. A sliding window in conjunction with a hash map can be quite powerful.

LC 3. Longest Substring Without Repeating Characters (✓) ★★

Given a string s, find the length of the longest substring without repeating characters.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        lookup = defaultdict(int)
        left = ans = 0
        
        for right in range(len(s)):
            char = s[right]
            lookup[char] += 1
            while left <= right and lookup[char] > 1:
                lookup[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
            
        return ans

The solution above is a fairly classic example of how to use a hash map with a sliding window. The manner in which the left pointer is incremented after a duplicate character is encountered is characteristic of many sliding window problems, but the nature of this problem allows us to make a small optimization: as soon as we encounter a character that is a duplicate, instead of incrementing left one character at a time until that character's previous occurrence is encountered and skipped over, we use our hash map to track character indexes (not frequencies) and simply jump the left pointer just past the last index of the previously encountered duplicate character:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        lookup = {}
        left = ans = 0
        
        for right in range(len(s)):
            char = s[right]
            if char in lookup and lookup[char] >= left:
                left = lookup[char] + 1
            lookup[char] = right
            ans = max(ans, right - left + 1)
            
        return ans

The hardest part about the solution above is the change in thinking needed to implement the variable width sliding window effectively. There's no while loop and the conventional "sliding" isn't so much sliding as it is "jumping". Additionally, the condition and lookup[char] >= left is critical for the sliding window — it ensures the character is not just in the hash map but that its last occurrence is within the current window. Our solution would fail without this conditional check.

For example, consider s = "abba". When we encounter the last "a", the first "a" is in the hash map, but it is not in the current window. Mistakenly treating it like it's part of the current window means moving the left pointer just past this occurrence and mistakenly getting a right - left + 1 length of 3, which is not correct.

LC 3105. Longest Strictly Increasing or Strictly Decreasing Subarray (✓) ★

You are given an array of integers nums. Return the length of the longest subarray of nums which is either strictly increasing or strictly decreasing.

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        inc_window = 1
        dec_window = 1
        ans = 1
        
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                inc_window += 1
                dec_window = 1
            elif nums[i] < nums[i - 1]:
                dec_window += 1
                inc_window = 1
            else:
                inc_window = 1
                dec_window = 1
            
            ans = max(ans, inc_window, dec_window)
        
        return ans

This is a slightly unconventional variable-width sliding window problem due to how the sizes of the windows are being changed, namely incrementally being grown by 1 or being reset to 1 for each iteration. The solution above is a very nice single-pass solution.

The following solution looks like more like the standard variable-width sliding window approach even though it's not nearly as nice (or efficient since two passes are being made):

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        def longest_monotonic_sub(arr, comparison):
            left = 0
            ans = 1
            for right in range(1, len(arr)):
                prev = arr[right - 1]
                curr = arr[right]
                if left < right and (prev >= curr if comparison == 'inc' else prev <= curr):
                    left = right
                ans = max(ans, right - left + 1)    
            return ans
        return max(longest_monotonic_sub(nums, 'inc'), longest_monotonic_sub(nums, 'dec'))

Fixed window size

Method 1 (build window outside main loop)

Remarks

Window size greater than array size (possibility): There is a chance that the window size k is greater than the array size arr.length — if not properly accounted for, this could easily lead to index out of range errors (it's not accounted for in the pseudocode below). It is often not a bad idea to have a check for this before proceeding with the window creation operation.
Clarity: Method 1 appears to be somewhat cleaner than Method 2 despite having another for loop. The construction of the window and initialization of ans is unambiguous and easy to understand in Method 1. We start by building the window, we set the initial answer, and then we move the window while iterative updating the answer. It's easier to keep things clear and straight with this approach.

Template with commented code

def fn(arr, k):
    # some data to keep track of with the window (e.g., sum of elements)
    curr = 0

    # build the first window (of size k)
    for i in range(k):
        # do something with curr or other variables to build first window
        curr += arr[i]

    # initialize answer variable (might be equal to curr here depending on the problem)
    ans = curr
    for i in range(k, len(arr)):
        # add arr[i] to window
        curr += arr[i]
        # remove arr[i - k] from window
        curr -= arr[i - k]
        # update ans
        ans = max(ans, curr)

    return ans

def fn(arr, k):
    curr = 0
    for i in range(k):
        curr += arr[i]

    ans = curr
    for i in range(k, len(arr)):
        curr += arr[i]
        curr -= arr[i - k]
        ans = max(ans, curr)

    return ans

Examples

Max sum of subarray of size k (✓)

def largest_sum_length_k(nums, k):
    curr = 0
    for i in range(k):
        curr += nums[i]
        
    ans = curr
    for i in range(k, len(nums)):
        curr += nums[i]
        curr -= nums[i - k]
        ans = max(ans, curr)
        
    return ans

The idea here is that we first build the sum of the first window of size k. Then we continue onward by adding and removing elements from the k-size window while keeping track of the current window sum and comparing that to the maximum, the final of which we return as the ultimate answer.

LC 643. Maximum Average Subarray I (✓)

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        curr = ans = 0
        for i in range(k):
            curr += nums[i]
            
        ans = curr / k
        for i in range(k, len(nums)):
            curr += nums[i]
            curr -= nums[i - k]
            ans = max(ans, curr / k)
            
        return ans

LC 1456. Maximum Number of Vowels in a Substring of Given Length (✓)

Given a string s and an integer k.

Return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are (a, e, i, o, u).

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        curr = 0
        for i in range(k):
            if s[i] in vowels:
                curr += 1
                
        ans = curr
        for i in range(k, len(s)):
            new_char = s[i]
            old_char = s[i - k]
            
            if old_char in vowels and curr > 0:
                curr -= 1
                
            if new_char in vowels and curr < k:
                curr += 1
                
            ans = max(ans, curr)
            
        return ans

Method 2 (build window within main loop)

Remarks

Window size greater than array size (possibility): There is a chance that the window size k is greater than the array size arr.length — if not properly accounted for, this could easily lead to index out of range errors (it's not accounted for in the pseudocode below). It is often not a bad idea to have a check for this before proceeding with the window creation operation.
Initialization of ans: Sometimes it can be a little unclear as to how best to initialize the ans variable. For example, in LC 643 we are looking for a "maximum average subarray" which means initializing ans to, say, 0 does not make sense because the maximum average could be negative depending on what elements are present in the array. It makes more sense in this problem to have ans = float('-inf') as the initialization even though it does not feel all that natural.
Complicated logic: The logic for managing the window is actually a bit more complicated than that used in Method 1. Here, in Method 2, the window is really being constructed by adding arr[i] to the window until i == k. If our array only has k elements, then our updating of ans before we return can save us from possible errors, but the whole thing takes a bit more effort to wrap your head around.

Template with code comments

def fn(arr, k):
    # some data to keep track of with the window (e.g., sum of elements)
    curr = 0

    # initialize answer variable (initial value depends on problem)
    ans = float('-inf')
    for i in range(len(arr)):
        if i >= k:
            # update ans
            ans = max(curr, ans)
            # remove arr[i - k] from window
            curr -= arr[i - k]
        
        # add arr[i] to window
        curr += arr[i]

    # update ans
    ans = max(ans, curr)
    return ans

def fn(arr, k):
    curr = 0
    ans = float('-inf')
    for i in range(len(arr)):
        if i >= k:
            ans = max(curr, ans)
            curr -= arr[i - k]
        curr += arr[i]
    ans = max(ans, curr)
    return ans

Examples

Max sum of subarray of size k (✓)

def largest_sum_length_k(nums, k):
    curr = 0
    ans = float('-inf')
    for i in range(len(nums)):
        if i >= k:
            ans = max(curr, ans)
            curr -= nums[i - k]
        curr += nums[i]
    
    ans = max(ans, curr)
        
    return ans

The flow here is a bit unnatural compared to first building the k-size window, then initializing the answer variable, and then proceeding to slide the window. The solution above makes it clear it's possible to build out a solution all within the main loop, but sometimes it likely will not be preferable.

LC 643. Maximum Average Subarray I (✓)

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        curr = 0
        ans = float('-inf')
        for i in range(len(nums)):
            if i >= k:
                ans = max(ans, curr / k)
                curr -= nums[i - k]
            curr += nums[i]
            
        ans = max(ans, curr / k)
        return ans

The solution above is not the recommended approach. It's clear the flow above is rather unnatural. Oftentimes it is more natural to first build the window outside the main loop and then continue. But it is possible to do it all in one go, as shown above (though not recommended).

Stacks and queues

Stacks

Remarks

TBD

# declaration (Python list by default)
stack = []

# push
stack.append(1)
stack.append(2)
stack.append(3)

# pop
stack.pop() # 3
stack.pop() # 2

# peek
stack[-1] # 1

# empty check
not stack # False

# size check
len(stack) # 1

Examples

LC 20. Valid Parentheses (✓) ★

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

class Solution:
    def isValid(self, s: str) -> bool:
        lookup = {
            ')': '(',
            '}': '{',
            ']': '['
        }
        
        stack = []
        for char in s:
            if char in lookup:
                if not stack or lookup[char] != stack.pop():
                    return False
            else:
                stack.append(char)
        return not stack

LIFO pattern: The last (most recent) opening delimiter is the first to be deleted.

The "correct" order is determined by whatever the previous opening bracket was. Whenever there is a closing bracket, it should correspond to the most recent opening bracket. We can effectively test for this in an iterative fashion by maintaining a history (stack) of the encountered opening delimiters. As soon as we encounter a closing delimiter, if the element on top of the stack doesn't correspond (or if the stack is empty), then we know we cannot have a list of valid parentheses and we can return False; otherwise, the current character is an opening delimiter and we add it to the stack.

Once we've completed iterating through all characters, if the stack of opening delimiters is empty, then we know all delimiters have a valid correspondence, and we can return True.

LC 1047. Remove All Adjacent Duplicates In String (✓)

Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for char in s:
            if stack and stack[-1] == char:
                stack.pop()
            else:
                stack.append(char)
        return "".join(stack)

LIFO pattern: The last (most recent) character is the first to be deleted.

The example of s = "azxxzy" resolving to "ay" highlights the strategy we should use here, namely determining whether or not the current character ever equals the element on top of the stack. If so, then remove the element from the top of the stack and continue on (this effectively deletes both elements); otherwise, add the current element to the stack.

LC 844. Backspace String Compare (✓)

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build_str(r):
            stack = []
            for char in r:
                if char == '#':
                    if stack:
                        stack.pop()
                else:
                    stack.append(char)
            return "".join(stack)
        
        s_str = build_str(s)
        t_str = build_str(t)
        return s_str == t_str

LIFO property: Maintaining a history of characters seen and deleting the most recently seen ones when encounter # characters.

The stack-based solution is quick and easy since # characters almost literally allow us to backspace by removing (deleting) characters from the stack that maintains a history of the characters seen so far. A more complicated but elegant solution is a two-pointer approach.

LC 71. Simplify Path (✓)

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

The path starts with a single slash '/'.
Any two directories are separated by a single slash '/'.
The path does not end with a trailing '/'.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for portion in path.split('/'):
            if portion == '' or portion == '.':
                continue
            elif portion == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(portion)
        return '/' + '/'.join(stack)

FIFO property: Only ever add valid file/directory names to the stack. If you encounter .., then remove the most recently seen file or directory name. If you encounter other characters such as '' or '.', then it's a no-op and you should continue on with your processing. At the end, return a string joined with / separators (the first / needs to be manually inserted).

LC 1544. Make The String Great (✓)

Given a string s of lower and upper case English letters.

A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

class Solution:
    def makeGood(self, s: str) -> str:
        stack = []
        for char in s:
            if stack and abs(ord(stack[-1]) - ord(char)) == 32:
                stack.pop()
            else:
                stack.append(char)
        return "".join(stack)

FIFO property: The last character added to the stack is the first one out if its corresponding upper- or lower-case character is the one currently being considered.

LC 2390. Removing Stars From a String (✓)

You are given a string s, which contains stars *.

In one operation, you can:

Choose a star in s.
Remove the closest non-star character to its left, as well as remove the star itself.

Return the string after all stars have been removed.

Note:

The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        for i in range(len(s)):
            if s[i] == '*' and stack:
                stack.pop()
            else:
                stack.append(s[i])
        return "".join(stack)

LC 232. Implement Queue using Stacks (✓) ★★

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

class MyQueue:
    def __init__(self):
        self.enqueued = []
        self.dequeue = []
        self.front = None

    def push(self, x: int) -> None:
        if not self.enqueued:
            self.front = x
        self.enqueued.append(x)

    def pop(self) -> int:
        if not self.dequeue:
            while self.enqueued:
                self.dequeue.append(self.enqueued.pop())

        if self.dequeue:
            return self.dequeue.pop()
            
    def peek(self) -> int:
        if not self.dequeue:
            return self.front
        else:
            return self.dequeue[-1]
        
    def empty(self) -> bool:
        return len(self.enqueued) == 0 and len(self.dequeue) == 0

The main insight for solving this problem performantly is realizing that, since stacks are LIFO (last in first out), this means elements popped from the stack appear in reverse order compared to how they were entered. For example, suppose the values 1, 2, and 3 are pushed to a stack. Then popping them off one at a time yields 3, 2, and 1, in that order.

Hence, to start, we just keep pushing elements to a stack, self.enqueued. These are the elements that have been enqueued so far. As soon as we need to pop an element from the queue, this means we need to access and remove the element at the bottom of the self.enqueued stack. To do this, we use another stack, self.dequeue, to collect the values from self.enqueued in reverse order. The element to be popped from the queue is now at the top of the self.dequeue stack.

This strategy works beyond just a way "to start". Since all of the elements in self.dequeue are the elements originally in self.enqueued but reversed, this means we can pop an element from self.dequeue whenever we're asked to pop an element from the queue. So long as self.dequeue isn't empty! If, however, self.dequeue, is empty, then we'll need to again pop all the elements from self.enqueued so that self.dequeue will contain the elements in proper FIFO order.

The process outlined above for maintaining these stacks is the core of this question, but being able to effectively "peek" from the queue is also a problem worth mentioning. If self.dequeue is not empty, then peeking should simply be the element we would otherwise pop from the queue, which is the element at the top of the self.dequeue stack (we're using the "stack peek" operation in this case): self.dequeue[-1]. But what if self.dequeue is actually empty and we've just been pushing elements to the self.enqueued stack? The element we want is at self.enqueued[0], but accessing the element in this way is not a valid stack operation -- the element is at the bottom of the stack! The idea is to use another class variable, self.front, to keep track of whatever value is at the bottom of self.enqueued (i.e., bottom of this stack or front of the queue). We keep track of this by reassigning self.front whenever we're about to push an element to self.enqueued but self.enqueued is empty. This is how we can keep pushing elements to self.enqueued without losing the reference to the element at the front/bottom. Then, once we're asked to perform a "queue peek" operation, we can either return the element at the top of the self.dequeue stack if it's not empty or self.front if self.dequeue is empty.

LC 2434. Using a Robot to Print the Lexicographically Smallest String (✓) ★

You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty:

Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.
Remove the last character of a string t and give it to the robot. The robot will write this character on paper.

Return the lexicographically smallest string that can be written on the paper.

Approach 1 (frequency array and smallest remaining character helper function)

class Solution:
    def robotWithString(self, s: str) -> str:
        def smallest_remaining_char(freqs_arr):
            for i in range(len(freqs_arr)):
                if freqs_arr[i] != 0:
                    return chr(a_ORD + i)
            return 'z'
        
        a_ORD = 97 # ord('a') = 97, the ordinal value of 'a'
        freqs = [0] * 26
        for char in s:
            freqs[ord(char) - a_ORD] += 1
        
        t = []
        p = []
        for char in s:
            t.append(char)
            freqs[ord(t[-1]) - a_ORD] -= 1
            while t and t[-1] <= smallest_remaining_char(freqs):
                p.append(t.pop())
                
        return "".join(p)

The variable t should almost certainly be a stack that holds a "history" of the characters in s as we iterate through them. It doesn't take long to realize that the main challenge here is figuring out when to push a character onto the output string, p, which is a list of accumulated characters that is strategically assembled to satisfy the "lexicographically smallest" demand. The primary idea in this problem is to only pop characters from the stack t when we're guaranteed that doing so enables us to proceed in assembling the lexicographically smallest string.

When, then, should we pop a character from t? Only when there are no remaining characters that are lexicographically smaller than the character on top of the stack t. This means we need some kind of lookup. A lookup for what? The smallest character remaining from wherever we are in our process of iterating through all characters of s. To do this effectively, we need to keep a frequency count (the smallest character remaining at one point could get removed and there could subsequently be more of the same characters to take its place), which is most often done using a hash map. We could do that here, but using a frequency array is arguably cleaner since the characters we care about are 'a' through 'z', meaning our frequency array only needs to have 26 slots.

We assemble the frequency array as our first pass in our solution. The smallest_remaining_char function will always give us the current smallest remaining character from wherever we are when processing the string s (it's helpful to know that 'a''s ordinal value is 97, which we can helpfully use to maintain our frequency array).

Now, each time we process a character from s, we push it to the stack t, and decrement its count from the frequency array, freqs. All that really remains is to proceed as alluded to above, namely pop elements from t into p that are smaller or equal to the smallest element remaining in s.

Approach 2 (minimum remaining character lookup array, no frequency count)

class Solution:
    def robotWithString(self, s: str) -> int:
        n = len(s)
        t = []
        p = []
        min_char = [s[-1]] * n
        for i in range(n - 2, -1, -1):
            min_char[i] = min(s[i], min_char[i + 1])
            
        idx = 1
        for char in s:
            t.append(char)
            while idx < n and t and t[-1] <= min_char[idx]:
                p.append(t.pop())
            idx += 1
        
        while t:
            p.append(t.pop())
        
        return "".join(p)

The solution in Approach 1 was $O(26n) = O(n)$ whereas the solution above is $O(n)$ . The constant factor is much smaller even though both solutions belong to the same efficiency class. Regardless, the solution above still uses the main idea from Approach 1, namely we only ever pop characters from t when they're (lexicographically) smaller or equal to the characters remaining in s. The difference in this approach compared to that in Approach 1 is that we do not use a frequency count; instead, we precompute what the remaining minimum character will be from any character index in s:

min_char = [s[-1]] * n
for i in range(n - 2, -1, -1):
    min_char[i] = min(s[i], min_char[i + 1])

This is easiest to understand by means of an example. Suppose we had s = 'laptop'. Then min_char, after running the code above, would yield ['a', 'a', 'o', 'o', 'o', 'p']; that is, at index i = 0, the lexicographically smallest remaining character is 'a'. At position i = 1, the lexicographically smallest remaining character is also 'a'. At index i = 2, the lexicographically smallest remaining character is 'o'. And so forth. This allows us to effectively use the min_char array to determine when elements should be popped from t and placed in p.

LC 946. Validate Stack Sequences (✓) ★

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        pop_p = 0
        ref = []
        for num in pushed:
            ref.append(num)
            while ref and pop_p < len(popped) and ref[-1] == popped[pop_p]:
                ref.pop()
                pop_p += 1

        return pop_p == len(popped)

The key idea here is somewhat difficult to intuit at first. Basically, we're trying to see if the values in pushed have been pushed (with unspecified pops along the way) in such a way that the pops specified in popped is actually possible; that is, it's almost as if we're starting with an empty stack, and then we proceed to push values into the stack in the order in which they appear in pushed, and along the way, we intermittently pop values from the stack, where the order in which values are popped is preserved in popped.

Hence, one possible strategy is to keep a reference or history of values pushed so far. The LIFO nature of keeping a history naturally suggests a stack. We'll call it ref. Then we can basically iterate through all values in pushed, adding them to the ref stack until the element at the top of the ref stack equals the first element in popped. This means we should pop the value from ref, and it also means we need to move to the second or next value in popped. This way of keeping a reference to values in popped suggests usage of a pointer, pop_p in the solution code above.

We should keep popping elements from ref so long as they match the ones in popped. We only move on to the next value in pushed once this has been done. Our endpoint will naturally be when ref is exhausted and pop_p == len(popped) (this means the sequence specified is possible). If pop_p != len(popped), then this means not all values in popped were accounted for and thus the specification is not possible.

Note: The condition pop_p < len(popped) in the while loop is not strictly necessary since we're guaranteed that pushed is a permutation of popped and hence the same length. The condition pop_p < len(popped) is only ever violated once ref is empty and hence redundant; if, however, pushed were not necessarily a permutation of popped, then pop_p < len(popped) would be necessary (e.g., pushed = [1,2,3,4,5,6,7], popped = [5,6]). Nonetheless, it's best for the sake of clarity to leave this condition in (gains are minimal when excluding the condition).

LC 735. Asteroid Collision (✓)

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        history = []
        for asteroid in asteroids:
            history.append(asteroid)
            while len(history) > 1 and history[-2] > 0 and history[-1] < 0:
                prev = history[-2]
                curr = history[-1]
                if prev > abs(curr):
                    history.pop()
                elif prev < abs(curr):
                    curr = history.pop()
                    history.pop()
                    history.append(curr)
                else:
                    history.pop()
                    history.pop()
                    
        return history

The main challenge here is to implement the solution in as clean a manner as possible. The actual problem statement is simple enough, but laying out the solution carefully takes a bit of thought:

We should maintain a history of all asteroids we've seen. It only makes sense to consider removing asteroids from the history if the history has more than a single asteroid, hence the while loop condition len(history) > 1.
Since we'll be processing asteroids from left to right, asteroid collisions can only happen when the last asteroid in the history is going right and the current asteroid is going left; hence, we have the following condition after adding the current asteroid to the history: history[-2] > 0 and history[-1] < 0.
Finally, we can proceed with handling the core conditions of the problem:
- If the previous asteroid has a greater size than the current one, then the current asteroid gets exploded (i.e., removed from the history).
- If, however, the previous asteroid's size is actually smaller than the current one, then the previous asteroid needs to be removed. But the current one is at the top of the history; hence, we temporarily remove the top of the history in order to remove the previous asteroid that exploded (then we add the current asteroid back).
- The only other possibility would be for the asteroids to have the same size, in which case both asteroids explode, and they should both be removed from the history.

LC 155. Min Stack (✓)

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(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.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

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

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

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

    def getMin(self) -> int:
        return self.min_stack[-1]

The requirement is to implement a solution with $O(1)$ time complexity for each function (i.e., push, pop, top, and getMin), and this is a hint in itself. All stacks would generally be designed to make it possible for us to get the minimum (or maximum) if there were no tradeoffs. Of course there must be a tradeoff here, notably one of space. So how should we use space to make each function $O(1)$ , particularly the getMin function?

The answer is to maintain two stacks, the stack itself, self.stack, as well as a stack that only keeps track of the minimums so far, self.min_stack. This allows us to keep the stacks in lockstep and to perform normal stack operations as desired while at the same time making it easy to get minimums in $O(1)$ time.

Queues

Remarks

TBD

import collections

# declaration (Python deque from collections module)
queue = collections.deque()

# initialize with values (optional)
queue = collections.deque([1, 2, 3])

# enqueue
queue.append(4)
queue.append(5)

# dequeue
queue.popleft() # 1
queue.popleft() # 2

# peek left (next element to be removed)
queue[0] # 3

# peek right
queue[-1] # 5

# empty check
not queue # False

# size check
len(queue) # 3

Examples

LC 933. Number of Recent Calls (✓)

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

RecentCounter() Initializes the counter with zero recent requests.
int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

class RecentCounter:

    def __init__(self):
        self.queue = deque()

    def ping(self, t: int) -> int:
        self.queue.append(t)
        while self.queue[-1] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

The most recently added element will automatically be part of the number of "recent" calls. To determine all recent calls, we need to remove the previous calls not within the specified range of [t - 3000, t]. A queue is the right data structure for this.

LC 346. Moving Average from Data Stream (✓)

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

MovingAverage(int size) Initializes the object with the size of the window size.
double next(int val) Returns the moving average of the last size values of the stream.

class MovingAverage:

    def __init__(self, size: int):
        self.queue = deque()
        self.val_total = 0
        self.size = size

    def next(self, val: int) -> float:
        if len(self.queue) < self.size:
            self.queue.append(val)
            self.val_total += val
            return self.val_total / len(self.queue)
        else:
            self.val_total -= self.queue.popleft()
            self.queue.append(val)
            self.val_total += val
            return self.val_total / self.size

There's nothing to prevent us from keeping track of the total window sum, which we can effectively use the queue to adjust by subtracting elements out of the window (first in first out) and adding new elements to the window.

LC 225. Implement Stack using Queues (✓) ★★

Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue), as long as you use only a queue's standard operations.

The main idea in each approach below is effectively to "rotate" elements in some way so that the most recent element added is accessible from the front (since we can only pop elements in a queue from the first given its FIFO nature). Approach 1 is the intended solution on LeetCode (and probably what would be acceptable in an interview), but approaches 2 and 3 offer seam neat insights for clever optimizations.

Approach 1 (one queue, O(n) pushes with self-rotations)

class MyStack:
    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        self.queue.append(x)
        size = len(self.queue)
        while size > 1:
            self.queue.append(self.queue.popleft())
            size -= 1
        
    def pop(self) -> int:
        return self.queue.popleft()

    def top(self) -> int:
        return self.queue[0]

    def empty(self) -> bool:
        return len(self.queue) == 0

The key to solving a similar problem, namely LC 232. Implement Queue using Stacks, was to take advantage of the fact that popping elements from a stack meant obtaining them in reverse order compared to how they are added to the stack. This meant we could use two stacks effectively to simulate a queue, where we kept adding elements to one stack (the "enqueued" stack) and we'd pop elements from the other stack (the "dequeue" stack) once a dequeue operation was requested — the main trick was that we only popped all the elements from the "enqueued" stack to "dequeue" stack when a dequeue operation was requested and the dequeue stack was empty. This meant we could perform the operation in amortized $O(1)$ . That's not the case here.

Queues are FIFO so popping elements from the left in one queue and appending them to the right in another queue means elements would be added to the second queue in the same order they were added to the first queue. That is definitely not desirable. The main trick for this problem, which is easy to miss at first because it seems like there must be a more performant way to accomplish this (see Approach 2), is to use a single queue and rotate elements through the queue every time a new element is added so that the new element becomes the left-most element of the queue. Each "push" operation for the stack we're trying to implement requires appending an element to the queue and then rotating through all elements by popping from the left and appending the popped element to the right until the newly added element is the left-most element. For example, consider how the numbers 2, 7, 8, 4 would be added to the queue to simulate a stack:

# first element (2) pushed
[2]

# second element (7) pushed 
[2]       # start state
[2,7]     # 7 gets pushed
[7,2]     # 2 gets popped from the left and pushed to the right

# third element (8) pushed
[7,2]     # start state
[7,2,8]   # 8 gets pushed
[2,8,7]   # 7 gets popped from the left and pushed to the right
[8,7,2]   # 2 gets popped from the left and pushed to the right

# fourth element (4) pushed
[8,7,2]   # start state
[8,7,2,4] # 4 gets pushed
[7,2,4,8] # 8 gets popped from the left and pushed to the right
[2,4,8,7] # 7 gets popped from the left and pushed to the right
[4,8,7,2] # 2 gets popped from the left and pushed to the right

Each push operation for the stack ultimately results in all elements being stored in the deque in reverse order, which is the desired effect. The push operation costs $O(n)$ and is really the only complicated operation, but it can be a head scratcher if you haven't seen it before.

Approach 2 (two queues, amortized O(sqrt(n)) pushes with self-rotations and cache)

class MyStack:
    def __init__(self):
        self.cache = deque()
        self.storage = deque()

    def push(self, x: int) -> None:
        self.cache.append(x)
        size = len(self.cache)
        while size > 1:
            self.cache.append(self.cache.popleft())
            size -= 1
            
        if len(self.cache) * len(self.cache) > len(self.storage):
            while self.storage:
                self.cache.append(self.storage.popleft())
                
            self.cache, self.storage = self.storage, self.cache

    def pop(self) -> int:
        if self.cache:
            return self.cache.popleft()
        else:
            return self.storage.popleft()
        
    def top(self) -> int:
        if self.cache:
            return self.cache[0]
        else:
            return self.storage[0]
        
    def empty(self) -> bool:
        return len(self.cache) == 0 and len(self.storage) == 0

The approach above is based on this solution. The core idea of maintaining stack order by rotating through elements is still present from Approach 1. But it seemed like there must be a more performant way to push elements to our stack than requiring an $O(n)$ approach every time (i.e., rotating through all elements for each push).

The core of the solution above is the same as that in Approach 1 (i.e., rotating through elements), but now we're effectively trying to reduce the amount of rotating we have to do for each push. The idea is to maintain two queues, one that acts as a cache and one that acts as main storage. How does this help? Costly rotations arising from push operations will only be executed on the cache, and our goal will be to keep the size of cache small. When the size of cache exceeds the square root of the size of storage, the following will happen:

All of the elements in storage will be popped and appended to cache.
The variable designations will be swapped so now cache is empty and storage has all elements in the stack.

Important to note is that both cache and storage will always be maintained in LIFO order, with cache holding the newest elements at the top of the stack and storage holding the oldest. An example that illustrates the mechanics of how this works will be most helpful. Suppose we're trying to push the following elements to our stack: 1, 2, 3, 4, 5, 6, 7, 8. This is how the process would look:

##### PUSHING (1)
cache = []    # start state
storage = []  # start state

cache = [1]   # after adding 1
storage = []

# len(cache) * len(cache) = 1 * 1 = 1 > 0 = len(storage)  [YES, transfer and reassign]
# self.storage is empty so the empty pop doesn't happen: self.cache.append(self.storage.popleft())
# we still end up swapping/reassigning cache and storage
cache = []
storage = [1]


##### PUSHING (2)
cache = []      # start state
storage = [1]

cache = [2]    # after pushing 2
storage = [1]

# len(cache) * len(cache) = 1 * 1 = 1 > 1 = len(storage) [NO, terminate push op]


##### PUSHING (3)
cache = [2]      # start state
storage = [1]

cache = [2,3]    # after pushing 3
cache = [3,2]    # after rotating
storage = [1]

# len(cache) * len(cache) = 2 * 2 = 4 > 1 = len(storage) [YES, transfer and reassign]
cache = [3,2,1] # pop left all elements in storage and append to cache
storage = []    # pop ALL elements from storage from the left and append to cache until empty

cache = []        # swap and reassign
storage = [3,2,1]


##### PUSHING (4)
cache = []        # start state
storage = [3,2,1]

cache = [4]       # after pushing 4
storage = [3,2,1]

# len(cache) * len(cache) = 1 * 1 = 1 > 3 = len(storage) [NO, terminate push op]


##### PUSHING (5)
cache = [4]         # start state
storage = [3,2,1]

cache = [4,5]       # after pushing 5
cache = [5,4]       # after rotating
storage = [3,2,1]

# len(cache) * len(cache) = 2 * 2 = 4 > 3 = len(storage) [YES, transfer and reassign]
cache = [5,4,3,2,1] # pop left all elements in storage and append to cache
storage = []        # pop ALL elements from storage from the left and append to cache until empty

cache = []            # swap and reassign
storage = [5,4,3,2,1]


##### PUSHING (6)
cache = []            # start state
storage = [5,4,3,2,1]

cache = [6]           # after pushing 6
storage = [5,4,3,2,1]

# len(cache) * len(cache) = 1 * 1 = 1 > 5 = len(storage) [NO, terminate push op]


##### PUSHING (7)
cache = []              # start state
storage = [5,4,3,2,1]

cache = [6,7]           # after pushing 7
cache = [7,6]           # after rotating
storage = [5,4,3,2,1]

# len(cache) * len(cache) = 2 * 2 = 4 > 5 = len(storage) [NO, terminate push op]


##### PUSHING (8)
cache = [7,6]               # start state
storage = [5,4,3,2,1]

cache = [7,6,8]             # after pushing 8
cache = [8,7,6]             # after rotating
storage = [5,4,3,2,1]

# len(cache) * len(cache) = 3 * 3 = 6 > 5 = len(storage) [YES, transfer and reassign]
cache = [8,7,6,5,4,3,2,1]   # pop left all elements in storage and append to cache
storage = []                # pop ALL elements from storage from the left and append to cache until empty

cache = []                  # swap and reassign
storage = [8,7,6,5,4,3,2,1]

The mechanics of the process illustrated above show how cache always maintains the top elements of the stack until its size limit (the square root of the size of storage) has been exceeded. Then all elements from storage are transfered to cache so as to maintain the LIFO order of the stack. Then cache and storage are swapped/reassigned so that cache is now empty again. Hence, storage is the main storage for the stack and keeps growing indefinitely while cache, on the other hand, is sort of an intermediary device that's used to make sure storage grows in size as efficient as possible.

As this post notes:

push works in $O(\sqrt{n})$ amortized time. There are two cases: if $|\texttt{cache}| < \sqrt{|\texttt{storage}|}$ , then push takes $O(\sqrt{n})$ time. If $|\texttt{cache}| \geq \sqrt{|\texttt{storage}|}$ , then push takes $O(n)$ time, but after this operation cache will be empty. It will take $O(\sqrt{n})$ time before we get to this case again, so the amortized time is $O(n/\sqrt{n})=O(\sqrt{n})$ time.

Approach 3 (dynamic number of deques, O(1) operations)

class MyStack:
    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        new_queue = deque()
        new_queue.append(x)
        new_queue.append(self.queue)
        self.queue = new_queue
        
    def pop(self) -> int:
        pop_val = self.queue.popleft()
        self.queue = self.queue.popleft()
        return pop_val

    def top(self) -> int:
        return self.queue[0]

    def empty(self) -> bool:
        return len(self.queue) == 0

The solution above, inspired by Stefan Pochmann's, shows it is possible to implement MyStack using only $O(1)$ operations if we get really creative (even though this may be thought of as "cheating" in some sense because we use an unlimited number of deques). This solution takes advantage of the fact that Python is fundamentally a reference-based language: adding a queue object into another does not copy the entire contents — this is an $O(1)$ operation since a linked list is used under the hood (for Python deques).

To illustrate exactly how and why the solution above works, considering pushing the following elements to our stack: 1, 2, 3. Below, we'll let D represent a deque collection:

# starting state
self.queue = D()


# pushing 1
new_queue = D(1) # after pushing 1
          = D(1, D()) # after pushing self.queue

self.queue = D(1, D()) # end state after pushing x


# pushing 2
new_queue = D(2) # after pushing 2
          = D(2, D(1, D())) # after pushing self.queue

self.queue = D(2, D(1, D())) # end state after pushing 2


# pushing 3
new_queue = D(3) # after pushing 3
          = D(3, D(2, D(1, D()))) # after pushing self.queue

self.queue = D(3, D(2, D(1, D()))) # end state after pushing 3

The process illustrated above shows how we always have access to the most recently added element (desirable for stacks because of the LIFO processing). Popping an element is also easy. Consider the final state of the example above: popping an element from the left (a queue operation) of self.queue means popping the left-most element of D(3, D(2, D(1, D()))), which is the integer 3, as desired. After this pop, we have self.queue = D(D(2, D(1, D()))), which is not desirable because now if we pop left then we'll get a deque and not an integer, as desired and required. But this is not much of an issue because all we have to do is reassign self.queue to be the left-most popped element (after popping the 3, the deque only consists of one element, the deque with everything else in the stack): self.queue = D(2, D(1, D())). Now we can pop left to get the 2 and reassign by popping left again to get D(1, D()). Finally, we can pop left to get the 1 and reassign by popping left again to end up back where we started: D().

LC 649. Dota2 Senate (✓)

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.

Given a string representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        r_sen = deque()
        d_sen = deque()
        
        for i in range(len(senate)):
            if senate[i] == 'R':
                r_sen.append(i)
            else:
                d_sen.append(i)
        
        while r_sen and d_sen:
            banning, banned = min(r_sen[0], d_sen[0]), max(r_sen[0], d_sen[0])
            if r_sen[0] == banning:
                r_sen.append(r_sen.popleft() + n)
                d_sen.popleft()
            else:
                d_sen.append(d_sen.popleft() + n)
                r_sen.popleft()
        
        return 'Radiant' if len(r_sen) > 0 else 'Dire'

This is quite the difficult problem, one where using queues is not at all obvious at first. The solution above (not due to me) is quite brilliant. The core idea, which will be reinforced/illustrated by means of an example in just a moment, is to create two queues, one for each set of senators. Why?

We can safely assume that senators will always act in a greedy way (i.e., they will always ban the senator of the opposing party if there is one). How do we know how to keep track of the senators and their banning decisions? Without queues, that becomes a more difficult question to answer. With queues, however, this becomes a much more straightforward question: we do a first pass of senate and assemble queues of indexes for both parties, the Radiant senators, r_sen, and the Dire senators d_sen.

While both queues are non-empty, we compare their leftmost entries. Indexes naturally correspond to positions for the senators (i.e., the smaller index comes first); hence, the senator with the smaller index of the two will be the senator who does the banning while the senator with the larger of the indexes gets banned. The banned senator can simply be popped from the queue (popped from the left), but the senator who does the banning will have to wait for the next round (given the problem's circular nature). A clever solution to ensure the senator who does the banning is actually involved in the next round is to pop the banning senator from the queue (pop left), and then to push that same senator to the back of the same queue but this time with a larger index to indicate this senator comes later. The easiest way to adroitly perform this index manipulation is just by adding n to the index that already exists, where n is the size of the original senate string.

Whichever queue ends up being non-empty is the victorious senate party.

Note: As can be seen in the solution above, we don't actually need to declare the banned variable. We can remove it without issue since it is not used (it was only included to illustrate the explanation above).

Monotonic stacks

Remarks

TBD

TBD

Examples

LC 739. Daily Temperatures (✓)

Given an array of integers temperatures that 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.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [None] * n
        stack = []
        
        for i in range(n):
            val_A = temperatures[i]
            # try to find the next larger temperature, val_B,
            # for the current temperature, val_A
            while stack and temperatures[stack[-1]] < val_A:
                idx_val_B = stack.pop()
                ans[idx_val_B] = i - idx_val_B
            stack.append(i)
        
        # remaining temperatures, val_A, have no next larger temperature, val_B
        while stack:
            idx_val_A = stack.pop()
            ans[idx_val_A] = 0
            
        return ans