Fancy Sequence: Lazy Math with Modular Inverse

Fancy Sequence is LeetCode problem 1622. You need to design a data structure that supports three operations on a sequence of numbers: append a value, addAll to add an increment to every element, and multAll to multiply every element by a factor. A fourth operation, getIndex, retrieves the current value at a given index, modulo 10^9 + 7.

The naive approach is to loop through the entire sequence for every addAll or multAll call. That blows up to O(n) per operation. The real challenge is making all four operations run in O(1) time.

Why this problem matters

Fancy Sequence tests whether you can combine two ideas that rarely show up together: lazy propagation and modular arithmetic. Lazy propagation is a technique you might know from segment trees, where you defer updates and apply them only when you need the actual value. Modular inverse is a number theory concept that lets you "undo" multiplication under a prime modulus.

Problems that blend data structure design with math are rare on LeetCode. That rarity is exactly what makes this one valuable. If you can solve it cleanly, you understand both the design pattern and the math well enough to handle harder variants.

The approach

The key insight is that every combination of addAll and multAll operations can be represented as a single linear transformation: value = value * m + a, where m is the cumulative multiplier and a is the cumulative addend.

When you call multAll(x), both the multiplier and the addend get scaled: m = m * x and a = a * x. When you call addAll(x), only the addend changes: a = a + x.

When you append a new element, you record a "snapshot" of the current global (m, a) at that moment. Later, when you call getIndex(i), you compute the net transformation that happened between the snapshot and the current global state. To find the net multiplier, you need to divide the current m by the snapshot m. Under a prime modulus, division becomes multiplication by the modular inverse.

The modular inverse of x modulo a prime p is pow(x, p - 2, p), courtesy of Fermat's little theorem. This lets you compute current_m / snapshot_m as current_m * pow(snapshot_m, p - 2, p).

class Fancy:
    def __init__(self):
        self.MOD = 10**9 + 7
        self.seq = []
        self.add = 0
        self.mult = 1
        self.snap_add = []
        self.snap_mult = []

    def append(self, val):
        self.seq.append(val)
        self.snap_add.append(self.add)
        self.snap_mult.append(self.mult)

    def addAll(self, inc):
        self.add = (self.add + inc) % self.MOD

    def multAll(self, m):
        self.add = self.add * m % self.MOD
        self.mult = self.mult * m % self.MOD

    def getIndex(self, idx):
        if idx >= len(self.seq):
            return -1
        sa = self.snap_add[idx]
        sm = self.snap_mult[idx]
        inv_sm = pow(sm, self.MOD - 2, self.MOD)
        net_mult = self.mult * inv_sm % self.MOD
        net_add = (self.add - sa * net_mult) % self.MOD
        return (self.seq[idx] * net_mult + net_add) % self.MOD

Step-by-step walkthrough

Here is what happens at each stage:

1. append(2): The sequence is [2]. The global tracker is (add=0, mult=1). We save a snapshot (0, 1) for index 0.

2. addAll(3): The global add becomes 3. We do not touch the sequence array at all. Every element that existed before this call will pick up the +3 when we eventually read it.

3. append(7): The sequence is [2, 7]. We save the current tracker (3, 1) as the snapshot for index 1. Because index 1 was appended after the addAll, the +3 should not apply to it. The snapshot ensures that.

4. multAll(2): The global mult becomes 2. The global add becomes 3 * 2 = 6 (the addend is also scaled by the multiplication, which preserves the correct linear transformation).

5. getIndex(0): We compute the net transformation from snapshot (0, 1) to current (6, 2). Net mult = 2 * inv(1) = 2. Net add = 6 - 0 * 2 = 6. Result = 2 * 2 + 6 = 10.

6. getIndex(1): Snapshot for index 1 is (3, 1). Net mult = 2 * inv(1) = 2. Net add = 6 - 3 * 2 = 0. Result = 7 * 2 + 0 = 14.

The beauty of this approach is that addAll and multAll are both O(1), regardless of how many elements are in the sequence.

Complexity analysis

The getIndex call involves computing pow(sm, p - 2, p), which is O(log p) via fast exponentiation. Since p is fixed at 10^9 + 7, that is about 30 multiplications, effectively constant. The space is O(n) for storing the sequence and the per-element snapshots.

Edge cases to watch for

• getIndex out of bounds. If idx >= len(seq), return -1. Do not forget this check.
• multAll(0). Multiplying everything by zero is valid. After this, every existing element becomes 0 (modulo the prime). The modular inverse of the snapshot multiplier still works correctly because the snapshot multiplier was nonzero when the element was appended.
• Overflow. All arithmetic must be done modulo 10^9 + 7. In Python this is handled naturally by the % operator, but in C++ or Java you need to be careful with intermediate products.
• Large number of operations. The problem allows up to 10^5 calls. The brute force O(n) approach will time out. The lazy approach handles this easily.
• Consecutive multAll and addAll calls. The order matters. addAll(3) followed by multAll(2) gives a different result than the reverse. The global tracker handles this correctly because multAll scales the existing add value.

The building blocks

This problem sits at the intersection of two patterns:

Lazy propagation. Instead of applying an operation to every element immediately, you record it and apply it later, only when needed. This is the same idea behind lazy propagation in segment trees, where range updates are deferred until a query forces them to be resolved. Here, the "segment tree" is replaced by a simple pair of global accumulators.

Modular inverse via Fermat's little theorem. When working modulo a prime p, dividing by x is the same as multiplying by x^(p-2). This is essential for computing the net multiplier between two snapshots. Without it, you would need to store the full history of operations and replay them for each query, which defeats the purpose of lazy tracking.

The combination is powerful: lazy tracking compresses an arbitrary sequence of add and multiply operations into a single (add, mult) pair, and modular inverse lets you compute the difference between any two such pairs in constant time.

From understanding to recall

The math in this problem is not deep, but it is easy to mess up. The relationship between addAll and multAll (where multiplication scales the existing addend) is the kind of detail that slips away after a few days. You might remember that snapshots are involved, but forget exactly how to compute the net transformation at query time.

The fix is the same as always: write the solution from scratch, wait a few days, and do it again. The first time, you will probably need to re-derive the formula for net_add. By the third repetition, the formula (global_add - snap_add * net_mult) % MOD will feel natural. Spaced repetition turns fragile understanding into reliable recall.

This problem also reinforces a broader principle: when a brute force approach does too much repeated work, look for a way to defer the work and batch it later. That mental model, "defer and resolve on demand," is the common thread connecting lazy propagation in segment trees, prefix sums, and this Fancy Sequence trick.

Related posts

• Design Add and Search Words - Another design problem where the data structure choice drives the solution
• LRU Cache - The classic design problem that pairs a hash map with a linked list
• Evaluate Reverse Polish Notation - Stack-based evaluation, another pattern where deferred computation is key