In a previous post, we computed the mean hitting time of a state in a Markov chain by conditioning on the first transition $X_1$, a trick we’ll call one-step recursion. In this post, we’ll apply the same trick to compute $E[N]$. We’ll work with a general probability $p$ of heads, and only at the end plug in $p = 1/2$ for the fair-coin case.

There’s one big difference in style between this post and the previous one. In the previous post, we were careful to justify each step rigorously, naming the law of total expectation, the Markov property, time-homogeneity, and so on. This post leans much more heavily on intuition.

We won’t write the chain $\mathcal{X} = \lbrace X_0, X_1, \dots\rbrace$ out explicitly, and we won’t invoke the law of total expectation or the Markov property by name. Instead, we’ll just reason directly about what conditional expectations like $E[N \mid HT]$ “should” equal, leaning on the simple observation that observing a tail wipes out any in-progress streak.

Once we have the answer, we’ll go back and look at the problem through the rigorous Markov chain lens. We’ll see that the intuitive manipulations were really the same mean hitting time recursion from the previous post in disguise.

Why bother working intuitively first? Terry Tao has a wonderful short essay, There’s more to mathematics than rigour and proofs, where he describes mathematical maturity as a three-stage progression.

First comes a “pre-rigorous” stage, where you work by intuition and informal manipulation. Then a “rigorous” stage, where you learn to be careful and precise. And finally a “post-rigorous” stage, where intuition comes back, but now you trust it because you know any informal step could be made rigorous if you had to.

Both intuition and rigour matter, and neither replaces the other. Intuition is what lets you guess the right identity, pick a productive way to condition, or notice that two problems are really the same problem in disguise. Rigour is what lets you trust the answer once you have it. The previous post was an exercise in rigour; this one is an exercise in intuition.

Setup and notation

Let $p \in (0, 1)$ be the probability of heads on a single flip. We want $E[N]$, the expected number of flips until we see two heads in a row.

To set up the one-step recursion, we’ll introduce a few conditional expectations, each one indexed by the prefix of flips we’ve already observed:

• $E[N \mid H]$: the expected number of flips until we see two heads in a row given that the first flip has already happened and was heads.
• $E[N \mid T]$: same idea, but the first flip was tails. Because the flips are independent, then the random process of flipping the coin is memoryless, such that $E[N \mid T] = E[N]$.
• $E[N \mid HH]$: the expected number of flips until we see two heads in a row given that the first two flips have already happened and were both heads. Because we’ve already seen two heads, $E[N \mid HH] = 0$.
• $E[N \mid HT]$: the expected number of flips until we see two heads in a row given that the first flip was heads and the second was tails. Again, because the coin flips are indepndent, when we see a tails on the second flip, the streak resets, such that $E[N \mid HT] = E[N]$.

One-step recursion

Now we condition on the first flip. With probability $p$ it’s heads, and with probability $1-p$ it’s tails:

The leading $1$ counts the first flip itself, and the rest counts the expected number of additional flips after that first flip.

From the previous section, $E[N \mid T] = E[N]$, and we can expand $E[N \mid H]$ in $\eqref{EN}$:

From the previous section, $E[N \mid HH] = 0$ and $E[N \mid HT] = E[N]$. So,

Plugging $\eqref{ENH2}$ into $\eqref{EN}$,

That’s one linear equation in one unknown, $E[N]$. Solving for $E[N]$ yields $E[N] = \frac{1 + p}{p^2}$. For a fair coin with $p = 1/2$, $E[N] = 6$. That is, on average, we need to flip the fair coin 6 times to see two heads in a row.

Markov chain interpretation

Equations $\eqref{EN}$ and $\eqref{ENH1}$ are mean hitting time recursions on a 3-state Markov chain. The states are:

• $S_0$: “no head pending”; either we haven’t flipped yet, or the most recent flip was a tail.
• $S_1$: “one head pending”; the most recent flip was a head, but we haven’t seen two in a row yet.
• $S_2$: “two heads in a row”; absorbing.

The transitions are:

• From $S_0$: go to $S_1$ with probability $p$, stay at $S_0$ with probability $1-p$.
• From $S_1$: go to $S_2$ with probability $p$, go back to $S_0$ with probability $1-p$.
• From $S_2$: stay at $S_2$ with probability $1$.

Using the $\tau_{ij}$ notation from the previous post, the mean hitting times of $S_2$ from $S_0$ and $S_1$ are

and equations $\eqref{EN}$ and $\eqref{ENH1}$ are exactly the mean hitting time recursion $\tau_{iS_2} = 1 + \sum_k p_{ik} \cdot \tau_{kS_2}$ (with $\tau_{S_2 S_2} = 0$) instantiated at $i = S_0$ and $i = S_1$. The “memoryless restart” identities $E[N \mid T] = E[N]$ and $E[N \mid HT] = E[N]$ are just the chain’s transitions back into $S_0$.

Conclusion

The same one-step recursion that handled the random walk on a square in the previous post handles this coin-flipping problem too. The only thing that changes is the underlying Markov chain. A 4-state walk on a square gets replaced by a 3-state absorbing chain that tracks the current head streak.

The closed form $E[N] = (1 + p)/p^2$ also generalizes nicely. If you want $k$ heads in a row instead of $2$, you get a $(k+1)$-state absorbing chain, and the same one-step recursion gives you a closed-form mean hitting time of the absorbing state.

This post lays out a clean way to think about graphs using a pointer-style interpretation and then shows it in action by reversing a linked list.

Preliminaries

We will treat a graph as a collection of nodes, where each node can have multiple outgoing directed edges to other nodes. A minimal Python representation might look like this:

1
2
3
4
class Node:
    def __init__(self, val: int, neighbors: list):
        self.val = val
        self.neighbors = neighbors

Each node stores a list of references to its neighboring nodes. The key is how we interpret assignments involving these references.

Creating pointers to nodes

Consider the following snippet:

1
2
3
4
5
6
class Node:
    def __init__(self, val: int, neighbors: list):
        self.val = val
        self.neighbors = neighbors

X = Node(0, [])

The snippet above is represented visually in Fig. 1, where the node contains the value $0$ and the pointer $X$ points to this node. Note that $X$ itself is not a node and is just a pointer.

Next, let’s add the pointer Y to this snippet:

1
2
3
4
5
6
7
class Node:
    def __init__(self, val: int, neighbors: list):
        self.val = val
        self.neighbors = neighbors

X = Node(0, [])
Y = X

This does not copy anything. It simply makes Y refer to the same Node as X. Visually, this is shown in Fig. 2.

Adding neighbors to nodes

Now consider:

1
2
3
4
5
6
7
class Node:
    def __init__(self, val: int, neighbors: list):
        self.val = val
        self.neighbors = neighbors

X = Node(0, [Node(1, []), Node(2, []), Node(3, [])])
Y = X

This new setup is shown in Fig. 3. We can see that node $0$ has 3 children: nodes $1, 2,$ and $3$.

Moving pointers to nodes

We can then move pointers X and Y to nodes $1$ and $3$ respectively as follows:

1
2
3
4
5
6
7
8
9
class Node:
    def __init__(self, val: int, neighbors: list):
        self.val = val
        self.neighbors = neighbors

X = Node(0, [Node(1, []), Node(2, []), Node(3, [])])
Y = X
X = X.neighbors[0]
Y = Y.neighbors[2]

This movement of pointers is shown in Fig. 4.

We can then change the values of the nodes that the $X$ and $Y$ pointers reference:

1
2
3
4
5
6
7
8
9
10
11
class Node:
    def __init__(self, val: int, neighbors: list):
        self.val = val
        self.neighbors = neighbors

X = Node(0, [Node(1, []), Node(2, []), Node(3, [])])
Y = X
X = X.neighbors[0]
Y = Y.neighbors[2]
X.val = 7
Y.val = 23

This new configuration is shown in Fig. 5.

Unfortunately, after moving pointers $X$ and $Y$, we can’t make them reference node $0$ again because this would require nodes $7$ and $23$ in Fig. 5 having directed edges pointing at node $0$. So, we can only move pointers along the direction indicated by the directed edges in a graph.

In fact, from the perspective of pointer $X$, only node $7$, the node that pointer $X$ is referencing, exists. All other nodes do not exist. This is because there are no outgoing directed edges from node $7$.

Similarly, from the perspective of pointer $Y$, only node $23$ exists because there are no outgoing directed edges from node $23$.

A concrete example: reversing a linked list

We can see how this mental model is useful via an example. Consider the linked list shown in Fig. 6.

A linked list is just a very restricted graph: each node has exactly one outgoing edge (traditionally called next instead of children[0]):

1
2
3
4
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

We want to reverse this linked list so that it looks like Fig. 7.

We can perform this reversal sequentially as follows. First, we introduce three pointers: prev, curr, and next by writing prev = None, curr = head, and next = head.next:

Note that we replaced A with head to keep this implementation general: Next, move curr’s arrow to point to prev instead of curr.next by writing curr.next = prev:

Then, move the prev, curr, and next pointers 1 step forward by writing prev = curr, curr = next, and next = next.next:

Repeat this process until the next pointer references None:

Once the next pointer references None, we are done. In Python, we would implement this logic as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # edge case
    if head is None:
        return head

    # first iteration
    prev = None
    curr = head
    nxt = head.next
    curr.next = prev

    # second iteration onwards
    while nxt is not None:
        prev = curr
        curr = nxt
        nxt = nxt.next
        curr.next = prev
    return curr

# Build A -> B -> C -> None
head = ListNode("A", ListNode("B", ListNode("C")))
head_reversed = reverseList(head)

# Print result
curr = head_reversed
while curr:
    print(curr.val, end=" -> ")
    curr = curr.next
print("None")

Why this mental model matters

This pointer-style interpretation clarifies several subtle points:

• Assignments (=) move references, not data.
• Graph structure lives inside objects, not variables.
• Mutations affect all references to the same node.
• Traversal through a graph is just repeatedly “moving the pointer”.
• Algorithms like reversal are just systematic edge rewiring.

Without this model, it’s easy to get lost in the details of what Python is doing.

Summary

You can think of graph manipulation in Python as a sequence of pointer operations:

• head = X: move pointer to node X
• head.childN = Y: create or update an edge from X to Y

Everything else including DFS, BFS, cycle detection, even linked list reversal, is built on top of these two ideas.

At each vertex, you play the following game: flip a fair coin and move to the neighboring vertex in clockwise order if it lands Heads and in counter-clockwise order if it lands Tails. For example, suppose you are standing at vertex $B$ and flip the coin. If it lands Heads, move to vertex $C$ and if it lands Tails, move to vertex $A$.

You repeat this game at each vertex, consuming 1 second of time each time you move from one vertex to another. You also play this game for an infinite amount of time.

This random walk on the square can be naturally represented using the discrete-time and time-homogeneous Markov chain (MC) shown in Fig. 1.

Two questions naturally arise from this random walk:

1. Starting at vertex $A$, how long does it take, on average, to reach vertex $D$?
2. Starting at vertex $A$, how long does it take, on average, to return to vertex $A$?

We answer these questions using the concepts of mean hitting time and mean return time. Most explanations of mean hitting and return times found online, such as the one on this page, tend to be “hand-wavy”, where they skip some important steps. In this post, I aim to be as clear and precise as possible when deriving expressions for the mean hitting and return times.

Writing this post would not have been possible without the help of Misha Lavrov, who answered my related questions Why are these absorption probabilities equal? and How can I derive a general expression for the mean return time in a Markov chain?.

Mean hitting time

We now answer the first question.

Let the MC shown in Fig. 1 be represented by the random process $\mathcal X = \lbrace X_0, X_1, X_2, \dots \rbrace$, where $X_n \in \lbrace A, B, C, D\rbrace$ for each $n \in \lbrace 0, 1, \dots\rbrace$. Then, for each state $i$, let

be the hitting time of state $i$ as measured from time $k$. For example, for the sample trajectory $B, C, B, C, D, C, A, \dots$, $T_A(0) = 6, T_A(1) = 5, T_D(0) = 4,$ and $T_D(2) = 2$.

It can be verified that for each state $i$, if $X_0 \neq i$, $T_i(0) = 1 + T_i(1)$. Moreover, $T_i(0) \mid X_0 = j$ is the hitting time of state $i$ starting from state $j$ at time $0$. This identity will be useful for the derivations that follow.

In the special case that $i = D$ and $j = A$, $T_D(0) \mid X_0 = A$ is the hitting time of state $D$ starting from state $A$ at time $0$. So, we want to compute $\tau_{AD} = E[T_D(0) \mid X_0 = A]$, the average time required to reach vertex $D$ from vertex $A$ starting at time $0$. We derive an expression for $\tau_{AD}$ as follows.

where

• $\eqref{tauAD-1} \to \eqref{tauAD-2}$ follows from $T_D(0) = 1 + T_D(1)$ (assuming $X_0 \neq D$).
• $\eqref{tauAD-2} \to \eqref{tauAD-3}$ by linearity of the conditional expectation.
• $\eqref{tauAD-3} \to \eqref{tauAD-4}$ follows from the law of total expectation.

Next, the expression $E[E[T_D(1) \mid X_0 = A, X_1]]$ in $\eqref{tauAD-4}$ expands to

where

• $\eqref{exptauAD-1} \to \eqref{exptauAD-2}$ follows from the Markov property.
• $\eqref{exptauAD-2} \to \eqref{exptauAD-3}$ by defining $p_{As} = \Pr(X_1 = s \mid X_0 = A)$ because the MC in Fig. 1 is time-homogeneous.
• $\eqref{exptauAD-3} \to \eqref{exptauAD-4}$ follows again from the MC being time-homogeneous. Intuitively, the MC being time-homogeneous implies that the underlying random process starting from time $1$ with $X_1=s$ behaves like a fresh copy of the chain starting from time $0$ with $X_0 = s$. For a more rigorous version of this reasoning, see this answer.

To summarize,

where $\eqref{tauAD-5} \to \eqref{tauAD-6}$ follows because $\tau_{DD} = E[T_D(0) \mid X_0 = D] = 0$ and $p_{AA} = p_{AC} = 0$. Then, generalizing $\eqref{tauAD-5}$,

where $\eqref{tauBD-1} \to \eqref{tauBD-2}$ follows because $p_{BB} = \tau_{DD} = 0$. Next,

where $\eqref{tauCD-1} \to \eqref{tauCD-2}$ follows because $p_{CA} = p_{CC} = \tau_{DD} = 0$. Notice that $\tau_{AD} = \tau_{CD}$. This makes sense since both vertices $A$ and $C$ have the exact same transitions to vertex $D$ (they are symmetric). Hence, this leaves us with two equations and two unknowns:

Solving these two equations together yields $\tau_{AD} = \tau_{CD} = 3$ and $\tau_{BD} = 4$. That is, the average time required to go from vertices $A$ or $C$ to vertex $D$ is $3$ seconds, while the average time required to go from vertex $B$ to $D$ is $4$ seconds.

Mean return time

We now answer the second question, which was “Starting at vertex $A$, how long does it take, on average, to return to vertex $A$?”, using the concept of mean return time.

First, for each state $i$, let

be the return time of state $i$ as measured from time $k$. For example, for the sample trajectory $B, C, B, C, D, C, A, \dots$, $R_B(0) = 2$ and $R_C(1) = 2$.

It can be shown that $R_i(0) = 1 + T_i(1)$ for each state $i$, which will be useful for the derivations that follow.

In the special case that $i = A$ and $k = 0$, we want to compute $r_A = E[R_A(0) \mid X_0 = A]$, the average time required to return to vertex $A$ from vertex $A$ starting at time $0$. We derive an expression for $r_A$ as follows.

Next, using a similar set of steps as the ones shown in the previous section, the expression $E[E[T_A(1) \mid X_0 = A, X_1]]$ in $\eqref{rA-4}$ expands to $\sum_{s \in \lbrace A, B, C, D\rbrace} p_{As} \cdot \tau_{sA}$ such that

which is the expression for $r_A$ that we wanted to derive. By definition, $\tau_{AA} = 0$, and we can compute $\tau_{BA}, \tau_{CA},$ and $\tau_{DA}$ using the method described in the previous section to obtain $\tau_{BA} = \tau_{DA} = 3$ and $\tau_{CA} = 4$. Hence,

That is, the average time required to return to vertex $A$, starting from vertex $A$, is $4$ seconds.

Appendix

So far, we assumed that all 4 states in Fig. 1 are transient. That is, none of the states transition to themselves with probability $1$. An interesting phenomenon occurs when this is no longer the case. Consider the MC shown in Fig. 2.

If we now try to compute the mean hitting and return times, we face a problem: all these values are infinite. For example, the quantities $\tau_{Ds} = E[T_s(0) \mid X_0 = D]$ and $\tau_{Cs} = E[T_s(0) \mid X_0 = C]$ are infinite for every $s \in \lbrace A, B, C\rbrace$ and $s \in \lbrace A, B, D\rbrace$, respectively, because states $C$ and $D$ are recurrent.

Then, if we try to compute $\tau_{ij} = E[T_j(0) \mid X_0 = i]$ for any $i \neq j$, we see that $\tau_{ij}$ is infinite because

where $\tau_{sj}$ is infinite when $s = C$ or $s = D$ (the cases when $p_{iC}$ = 0 when $s = C$ or $p_{iD} = 0$ when $s = D$ can also be accounted for). To avoid these infinite values, we can make use of the fact that $\tau_{DD} = \tau_{CC} = 0$ and instead compute $\tau_{s(CD)} = E[T_{C,D}(0) \mid X_0 = s]$, where $T_{C,D}(0) = \min \lbrace n \ge 0 \mid X_{n} = C \, \textrm{or} \, X_{n} = D \rbrace$. $\tau_{s(CD)}$ will always be finite for each $s \in \lbrace A, B, C, D\rbrace$ because $X_n$ will reach states $C$ or $D$ for some $n$ with probability $1$.

It is interesting to note that the possibility that mean hitting times can be infinite when considering hitting individual recurrent states (rather than all of them collectively) motivates the need for classifying states into recurrent and transient classes, as explained here.

Preliminaries

First, recall that the $n$th number in the Fibonnaci sequence $F_n : \mathbb N \to \mathbb N$ is

In Python, we would compute $F_n$ as follows:

1
2
3
4
5
6
7
def fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Evaluating fib(100) takes several minutes on my PC and if I try to evaluate fib(1200), I get a RecursionError: maximum recursion depth exceeded, suggesting a stack overflow. Clearly, computing $F_n$ requires a non-trivial amount of computations.

Number of additions

The only operation required to compute $F_n$ is addition, so determining the time complexity of computing $F_n$ requires determining how many additions are needed to compute $F_n$.

Notice that to compute $F_n$, we decompose it into exactly $F_n$ ones and then sum them together. For example, $F_5 = 5$ is decomposed as

If $F_n$ is the sum of $F_n$ terms, then $F_n - 1$ additions are required to compute $F_n$. Interestingly, the number of additions required to compute $F_n$ is itself a Fibonacci sequence!

We could stop here, but this does not answer our original question. Specifically, although we know that $F_n - 1$ additions are required to compute $F_n$, we don’t know how $F_n$ is a function of $n$. In other words, we don’t know a closed-form expression for $F_n$, so we can’t conclude what the time complexity of computing $F_n$ is. Can we derive one?

A closed-form expression for $F_n$

There are many ways to derive a closed-form expression for $F_n$. My favorite way is using ordinary generating functions (OGFs). An OGF allows us to convert a linear recurrencce relation, like the one given in $\eqref{fib-seq}$, into an algebraic equation. OGFs are to linear recurrence relations what the Laplace Transform is to linear ordinary differential equations (ODEs).

Once this algebraic equation is manipulated into a certain form, its inverse is identified to obtain the closed-form expression, as done for the Laplace Transform of linear ODEs.

One of the most famous examples of OGFs is the Z-transform. Given a sequence $x_n$ for $n \in \mathbb N$, the Z-transform of $x_n$ is defined as

Hence, to determine a closed-form expression for $F_n$, we compute its Z-transform, $F(z)$, re-arrange terms into a specific form, and then identify the inverse Z-transform to obtain the closed-form expression. For convenience, we will let $F_0 = 0$ to be able to use the one-sided Z-transform.

Recall from $\eqref{fib-seq}$ that for $n > 2$, $F_n = F_{n-1} + F_{n-2}$ and the initial conditions are $F_0 = 0$ and $F_1 = F_2 = 1$. Computing the one-sided Z-transform of both sides of this recurrence relation yields

We now want to decompose $\eqref{fib-z}$ into a sum of fractions using a partial fractions decomposition.

It can be shown that

where

are the golden ratio and its conjugate, respectively. By inspection of $\eqref{fib-z-trans}$, we can deduce that the inverse Z-transform of this expression is

which is the closed-form expression of $F_n$ that we were looking for. $\eqref{binet-formula}$ is also known as Binet’s formula.

It is important to note that this method of obtaining a closed-form expression for $F_n$ only worked because we implicitly assumed that the Z-transform of $F_n$, $F(z)$, exists.

We assumed so because the expression $F_n = F_{n-1} + F_{n-2}$ given in $\eqref{fib-seq}$ represents a 2nd order all-pole IIR filter, which we know has a Z-transform.

More generally, if a recurrence relation does not have the form of an FIR or IIR filter, then it is necessary to verify beforehand that its Z-transform exists.

Conclusion

Because $\varphi > \psi$, then $F_n = O(\varphi^n)$. To summarize, the number of additions required to compute the $n$th Fibonnaci term grows exponentially at a rate of the golden ratio $\varphi$.

Personally, I found this problem interesting for several reasons:

1. We discovered that the number of additions required to compute $F_n$ is itself a Fibonnaci sequence.
2. Deriving the closed-form expression for $F_n$ involved solving a linear recurrence relation using OGFs, specifically the Z-transform.
3. We found that $F_n$ can be computed as a function of the golden ratio $\varphi$ and its conjugate $\psi$.

In this post, I provide a curated list of data structures that appear frequently enough in a diverse set of problems that they deserve to be formally recognized in your toolkit.

Inverse array (index map)

Standard arrays map an index to an item. An inverse array conceptually does the reverse: it maps an item to its corresponding index (or indices).

In practice, an Inverse Array is almost always implemented using a hash map, where the key is the element from the array and the value is the index (or indices) where the element is found.

If we don’t care about the index and just need to know if an element exists, a hash set serves the same purpose.

The primary use case for an inverse array is efficient lookups. Without an inverse array, checking if an element exists or finding its location requires scanning the array, which is an $O(n)$ operation. With an inverse array, this becomes an $O(1)$ operation.

Example: The “Two Sum” problem

Consider the classic problem Two Sum: Given an array of integers and a target, return indices of the two numbers such that they add up to target. The brute force approach involves looping through every pair, which has a time complexity of $O(n^2)$.

In contrast, using the inverse array approach, we can iterate through each num in the array, calculate the complement = target - num needed to hit the target, and then quickly check the inverse array to see if that complement has already been visited.

In Python, this problem can be solved as follows:

1
2
3
4
5
6
7
8
9
def twoSum(nums, target):
    inverse_array = {} # Map value -> index

    for i, num in enumerate(nums):
        complement = target - num
        if complement in inverse_array:
            return [inverse_array[complement], i]
        inverse_array[num] = i

See 1. Two Sum for details.

Histogram (frequency map)

A histogram is used to count the frequency of unique elements within a collection. It maps each unique element in a collection of items to the number of times it occurs in the collection.

If the items in the collection are generic, we use a hash map to implement the histogram, where keys are the unique elements and values are the counts.

If the elements are instead within a small, known range (e.g., lowercase English letters or a finite number of integers), we can use a fixed-size array or list for better performance. The index represents the item, and the value at that index represents the count.

Histograms are essential for problems involving anagrams, duplicates, or substring constraints.

Example: Valid anagram

Given two strings s and t, return true if t is an anagram of s.

An anagram implies both strings possess the exact same characters with the exact same frequencies. We build a histogram for s and a histogram for t and compare them.

In Python, this would be implemented as follows:

1
2
3
4
5
from collections import Counter

def isAnagram(s, t):
    # Counter is a built-in Python Histogram
    return Counter(s) == Counter(t)

See 242. Valid Anagram for details.

Inverse Histogram (frequency buckets)

While a standard histogram maps an item in a collection to the frequency of occurence in the collection, an inverse histogram maps a frequency of occurrence in a collection to one or more items in the collection.

Because multiple items can share the same frequency, this is not a one-to-one function. It maps an integer (frequency) to a list of items that appear that many times.

This is typically implemented as a list of lists (often called “buckets”) in Python, where the index of the outer list represents the frequency.

This structure is the backbone of the Bucket Sort algorithm. It allows you to find items based on their frequency in $O(n)$ time, avoiding the $O(n \log n)$ cost of sorting the entire array.

Example: Top $K$ frequent elements

Given an integer array nums and an integer k, return the k most frequent elements.

Instead of sorting a dictionary by value, we map frequencies to items. We then iterate backwards from the highest possible frequency (the length of the array) to find the most common items.

See 347. Top K Frequent Elements for details.

In Python, given a collection items and its histogram hist, an inverse histogram can be computed as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def compute_inv_hist(items, hist):
    # We need to create len(items) + 1 distinct lists because an item in the collection
    # can appear at most len(items) number of times, but because Python uses 0-based
    # indexing, then the last index will be len(inv_hist) - 1 NOT len(inv_hist). For
    # example, if items = [5, 5, 5, 5], then hist = {5: 4} and
    # inv_hist = [[], [], [], [], [5]].
    #
    # This also means that the first element of inv_hist will always be an empty list,
    # because each value in the histogram "hist" will always be at least 1.
    #
    # Finally, we can't write "inv_hist = [[]] * (len(items) + 1)" because this will
    # create (len(items) + 1) references to the same list, while we need (len(items) + 1)
    # distinct copies
    inv_hist = [[] for _ in range(len(items) + 1)]
    for item, freq in hist.items():
        inv_hist[freq].append(item)
    return inv_hist

Monotonic stack

A monotonic stack is a specialized stack data structure that maintains its elements in a specific sorted order, either increasing or decreasing.

Standard stacks simply push and pop. A monotonic stack adds logic before pushing a new element. That is, when pushing this new element, if it violates the monotonic property (e.g. the new element is bigger than the element at the top of the decreasing stack), keep popping elements off the stack until the monotonic property is restored or the stack is empty. Finally, push the new element.

The monotonic stack is useful for “next greater element” or “next smaller element” problems. It allows you to find the nearest element to the left or right that is larger or smaller than the current element in $O(n)$ time.

Example: Daily Temperatures

See 739. Daily Temperatures for details.

The purpose of this post is to provide a clear and comprehensive derivation of these two implementations.

Preliminaries

Consider the transfer function $H(z)$ of a general discrete-time IIR filter, such that

Note that $H(z)$ consists of an all-zero IIR filter (i.e., an FIR filter) cascaded with an all-pole IIR filter, such that

where

corresponds to the all-zero IIR filter and

corresponds to the all-pole IIR filter. We now map $H_b(z)$ and $H_a(z)$ to their corresponding difference equations in the time domain as follows.

where $u_b[k], y_b[k],$ and $b_0,\dots,b_{N-1}$ are the input, output, and $N$ feedforward coefficients, respectively, associated with the all-zero IIR filter and $u_a[k], y_a[k],$ and $a_1,\dots,a_M$ are the input, output, and $M$ feedback coefficients, respectively, associated with the all-pole IIR filter.

To summarize, the input $u_b[k]$ and output $y_b[k]$ of the all-zero IIR filter $H_b(z)$ are related by the difference equation,

and the input $u_a[k]$ and output $y_a[k]$ of the all-pole IIR filter $H_a(z)$ are related by the difference equation,

Direct Form I

In a DF1 implementation of an IIR filter, the input $u[k]$ is passed into the all-zero filter $H_b(z)$ first and the output of the all-zero filter is input to the all-pole filter $H_a(z)$ to produce the output $y[k]$. In other words, $u_b[k] = u[k]$, $y_b[k] = u_a[k]$, and $y_a[k] = y[k]$ for each $k$ such that

Note that the terms $u[k - 1],\dots,u[k-(N-1)]$ and $y[k - 1],\dots,y[k-M]$ are obtained from memory from a previous iteration. Hence, the DF1 structure requires memory for $N - 1 + M$ floating-point numbers.

Direct Form II

In a DF2 implementation of an IIR filter, the input $u[k]$ is passed into the all-pole filter $H_a(z)$ first and the output of the all-pole filter is input to the all-zero filter $H_b(z)$ to produce the output $y[k]$.

In contrast to the DF1 structure, the order of the all-pole and all-zero IIR filters are reversed. Moreover, $u_a[k] = u[k]$, $y_a[k] = u_b[k]$, and $y_b[k] = y[k]$ for each $k$ such that

Note that the terms $u_b[k - 1],\dots,u_b[k-M],\dots,u_b[k-(N-1)]$ are obtained from memory from a previous iteration.

In contrast to the DF1 structure, which requires memory for $N - 1 + M$ floating-point numbers, the DF2 structure requires memory for only $\max(N-1, M)$ floating-point numbers. Because $\max(N-1, M) < N - 1 + M$ when $N - 1 > 0$ and $M > 0$, then the DF2 structure requires less memory than the DF1 structure.

Transposed Direct Form I and Direct Form II

For a derivation of the Transposed Direct Form I and Direct Form II structures, see Transposed Direct Form I and Direct Form II implementations of IIR filters.

This problem belongs to a family of problems known as squaring the square. What I particularly like about this problem is that the problem statement can be understood by anyone of almost any age, and that this problem admits some elegant solutions.

First, note that “partitioning a square” means to tile the square with other squares that are not necessarily of the same size. For example, Fig. 1 shows how to partition a square into $n = 1, 4, 9,$ and $16$ squares.

We see from Fig. 1 that a square can always be partitioned into $n$ squares of the same size when $n$ is a perfect square (i.e. its positive or negative square root is an integer). Hence, we have solved the problem for the case when $n \geq 6$ and $n$ is a perfect square. What remains is the case when $n \geq 6$ but $n$ is not a perfect square.

Looking closely at Fig. 1, we see that to go from $n = 1$ squares to $n = 4$ squares, we applied a “split” operation. That is, we partitioned a square into $4$ squares of equal size. This increases the total number of squares in the partition by $3$.

So, we can partition a square into $n = 4, 7, 10, 13, \dots$ by repeatedly applying this “split” operation to one of the squares in the $n = 4$ square, as shown in Fig. 2.

Similarly, looking again at Fig. 1, we see that to go from $n = 4$ squares to $n = 1$ square, we applied a “merge” operation, which is the inverse of the “split” operation. That is, we replcaed $4$ neighboring squares with a single square. This decreased the total number of squares in the partition by $3$.

We can apply this “merge” operation to the case of $n=9$ squares to obtain a partition that consists of $n = 6$ squares, as shown in Fig. 3.

We can then repeatedly apply the “split” operation on one of the squares in the $6$-partition square to obtain the sequence $n = 6, 9, 12, 15,\dots$. To summarize, we have found the following sequences of partitions:

The only sequence remaining is $n = 8, 11, 14, 17, \dots$. This sequence can be obtained by paritioning a square into $8$ squares and then repeatedly applying the “split” operation. We can partition a square into $8$ squares by applying the “merge” operation to one of the $3 \times 3$ sub-squares in the $n = 16$ partition, as shown in Fig. 4.

We can then repeatedly apply the “split” operation to one of the squares in this $8$-partition to obtain the desired sequence, which concludes the solution to this problem.

Suppose that you’re working on a large codebase in your favorite editor, and suppose that you want to find out how many lines of code a particular class in this codebase takes up.

To do this, you find the first line of code that the class starts on, say line $7$, and then you find the last line of code that the class ends on, say line $373$. You then compute $373 - 7 = 366$ and conclude that this class takes up $366$ lines of code.

However, the correct answer is actually $367$ lines of code, since the last line, line $373$, was not counted in the original answer.

This is an example of a fencepost error. The word “fencepost” comes from one of the simplest examples where fencepost errors occur:

If you build a fence that is $10$ feet long with posts spaced $1$ foot apart, and assuming that each fence section consists of $2$ posts, how many posts do you need to build the fence?

If we divide $10$ feet of fence by $1$ foot per fence section, then we obtain $10$ fence sections. However, each fence section consists of $2$ posts, so while there will be $10$ fence sections, there will be $11$ posts.

We can resolve the fencepost error in the example above by writing down the sequence of lines of code as

Then, because two sequences have the same length if there exists a bijection between them, we can determine the length $N$ of $\eqref{loc_seq}$ by finding a bijection between it and the sequence $1,2,\dots,N$ as follows,

Hence, the length $N$ of $\eqref{loc_seq}$ is $367$.

More formally, consider the integers $r$ and $a$ such that $a > r$. What is the length of the sequence $r, r+1, r+2, \dots, a$? That is, how many integers are there in this sequence?

As done above, the length of this sequence can be determined by finding a bijection between this sequence and the sequence $1,2,\dots,N$, where $N \in \mathbb N$ is the length of the sequence and $N > 1$, as follows,

where $\eqref{gen_seq2}$ is obtained from $\eqref{gen_seq1}$ by subtracting $r$ from each element in $\eqref{gen_seq2}$ and $\eqref{gen_seq3}$ is obtained from $\eqref{gen_seq2}$ by adding $1$ to each element in $\eqref{gen_seq2}$. Hence, the length of the sequence $r,r+1,r+2,\dots,a$ is $(a-r) + 1$.

We can generalize this reasoning to the more general sequence $r,r+b,r+2b,\dots,a$, such that the difference between consecutive elements in the sequence is $b \in \mathbb N$ instead of $1$ as assumed above and $a = r + q \cdot b$ for some $q \in \mathbb N$.

The length of this more general sequence can be obtained as follows,

Hence, the length of the sequence $r,r+b,r+2b,\dots,a$ is $\frac{a-r}{b} + 1$. It is interesting to note that because $a = r + q \cdot b$, then $a, r, q,$ and $b$ can be interpreted as the dividend, remainder, quotient, and divisor, respectively, when $a$ is divided by $b$ via Euclidean division.

This general case is useful when determining how many “points” there are in a given interval. For example, suppose that you are trying to run a numerical simulation over time. You have the desired total simulation time $T > 0$ and a fixed time step size $\Delta t > 0$. Given this information, you would like to compute how many points in time that the simulation will step through, denoted $N$.

That is, you would like to determine the length of the sequence $0, \Delta t, 2\Delta t, \dots, T$. As done above, we can determine the length of this sequence by finding a bijection between this sequence and the sequence $1,\dots,N$, where $N \in \mathbb N$, as follows:

where $\eqref{sim_seq2}$ is obtained from $\eqref{sim_seq1}$ by dividing each element in the sequence by $\Delta t$ and $\eqref{sim_seq3}$ is obtained from $\eqref{sim_seq2}$ by adding $1$ to each element in the sequence. Hence, the number of time points that this simulation will step through is $\frac{T}{\Delta t} + 1$.

To summarize, to compute the correct number of numbers in a sequence and avoid fencepost errors, do the following:

1. Given the end-points of the sequence, write down the full sequence that you would like to count. Be sure to avoid including any numbers that you do not want to count.
2. Transform the sequence from step 1 into the canonical sequence $1,\dots,N$, where $N \in \mathbb N$.
3. The amount of numbers in the sequence is $N$.

Fencepost errors occur when the sequence that is written down in step 1 includes numbers that should not be counted or does not include numbers that should be counted.

For further reading on fencepost errors, see this article.