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
Binary search
Dynamic programming
- Memoization (top-down)
- Tabulation (bottom-up)
Graphs
Heaps
- Initialize heap in O(n) time
Linked lists
Matrices
- Calculate value in a 2D matrix given its index
Sliding window
- Variable window size
- Fixed window size
Stacks and queues
Trees
Two pointers
Miscellaneous

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

TBD

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 arr[mid] > target:
            right = mid - 1
        elif arr[mid] < target:
            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
            val = nums[mid]
            
            if target < val:
                right = mid - 1
            elif target > val:
                left = mid + 1
            else:
                return mid
            
        return -1

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

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 ]

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

Greedy (looking for minimum)

Remarks

TBD

TBD

Examples

TBD

Greedy (looking for maximum)

Remarks

TBD

TBD

Examples

TBD

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

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.

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.

Heaps

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.

import heapq
class SeatManager:

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

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

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


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(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)
    return ans

Examples

Longest subarray of positive integer array with sum not greater than k (✓)

def longest_subarray(nums, k):
    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

Longest substring of 1's given binary string and one possible 0 flip (✓)

def longest_bin_substring(s):
    left = curr = ans = 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.

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 is effectively adding the total number of subarrays in the range [left, right] that end at right, inclusive.

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