LeetCode 1622 - Fancy Sequence

The problem asks us to design a mutable sequence data structure that supports four operations efficiently: 1. Append a v

leetcodehardmathdesignsegment-treenumber-theory

LeetCode Problem 1622

Difficulty: 🔴 Hard
Topics: Math, Design, Segment Tree, Number Theory

Solution

Problem Understanding

The problem asks us to design a mutable sequence data structure that supports four operations efficiently:

  1. Append a value to the sequence.
  2. Add a constant value to every element currently in the sequence.
  3. Multiply every element currently in the sequence by a constant.
  4. Retrieve the value at a specific index.

All returned values must be taken modulo 10^9 + 7.

The key difficulty is that the sequence can grow to as many as 10^5 operations, and the operations addAll and multAll affect every existing element. A naive implementation that explicitly updates every number each time would quickly become too slow.

The sequence evolves over time. When we call addAll or multAll, only the elements already present in the sequence are affected. Future appended elements should not inherit past operations. This detail is extremely important.

For example:

append(2)      -> [2]
addAll(3)      -> [5]
append(7)      -> [5, 7]

The newly appended 7 does not receive the previous +3.

The constraints strongly suggest that we need near constant time operations:

  • Up to 10^5 total operations
  • Each operation must be efficient
  • Repeated full-array updates are not feasible

Another important observation is that all updates are linear transformations of the form:

x -> a*x + b

Both addition and multiplication can be represented this way:

addAll(inc): x -> x + inc
multAll(m):  x -> m*x

This observation leads directly to the optimal solution.

Important edge cases include:

  • Calling getIndex with an out-of-range index
  • Multiple chained multiplications and additions
  • Multiplication by zero
  • Large intermediate values requiring modular arithmetic
  • Appending values after many global operations

All arithmetic must consistently use modulo 10^9 + 7.

Approaches

Brute Force Approach

The most straightforward solution is to store the entire sequence directly.

  • append(val) pushes val into the array.
  • addAll(inc) iterates through every element and adds inc.
  • multAll(m) iterates through every element and multiplies by m.
  • getIndex(idx) returns the value if the index exists.

This approach is correct because every operation directly modifies the underlying sequence exactly as described.

However, it is far too slow. If we perform 10^5 operations and many of them are addAll or multAll, each requiring O(n) updates, the total runtime can degrade to O(n^2).

Optimal Approach

The key insight is that every global operation can be represented as a linear transformation:

x -> mul*x + add

Instead of updating every stored element, we maintain two global parameters:

  • global_mul
  • global_add

These describe the transformation applied to every stored value.

When we append a new value, we store a normalized version of it so that future transformations can still be applied correctly.

Suppose the current transformation is:

x -> global_mul*x + global_add

If we append value v, we want:

global_mul*stored + global_add = v

Solving for stored:

stored = (v - global_add) / global_mul

Since division under modulo arithmetic requires modular inverse:

stored = (v - global_add) * inverse(global_mul)

Now all future updates can be lazily represented by adjusting only global_mul and global_add.

This gives near constant time operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per update O(n) Explicitly updates all elements
Optimal O(1) amortized O(n) Uses lazy affine transformations

Algorithm Walkthrough

  1. Initialize an empty array called values.

This array will not store the literal visible sequence values. Instead, it stores normalized values that can later be transformed using the current global transformation. 2. Maintain two global variables:

global_mul = 1
global_add = 0

These represent the affine transformation currently applied to every stored element. 3. For append(val):

The visible value should become exactly val at insertion time.

Since all stored values are interpreted through:

visible = stored * global_mul + global_add

we reverse the transformation:

stored = (val - global_add) * inverse(global_mul)

Store this normalized value into the array. 4. For addAll(inc):

Every visible value becomes:

x -> x + inc

So we simply update:

global_add += inc
  1. For multAll(m):

Every visible value becomes:

x -> x * m

Expanding the current transformation:

x -> (global_mul*x + global_add) * m

Therefore:

global_mul *= m
global_add *= m
  1. For getIndex(idx):

If the index is invalid, return -1.

Otherwise reconstruct the visible value:

visible = stored * global_mul + global_add

Return the result modulo 10^9 + 7.

Why it works

The invariant is that every stored number represents a normalized value before the current global transformation is applied.

At all times:

visible_value = stored_value * global_mul + global_add

All updates preserve this invariant. Since addition and multiplication compose into affine transformations, we can defer updates lazily and reconstruct values correctly whenever needed.

Python Solution

class Fancy:

    MOD = 10**9 + 7

    def __init__(self):
        self.values = []
        self.global_mul = 1
        self.global_add = 0

    def mod_inverse(self, x: int) -> int:
        return pow(x, self.MOD - 2, self.MOD)

    def append(self, val: int) -> None:
        normalized = (
            (val - self.global_add)
            * self.mod_inverse(self.global_mul)
        ) % self.MOD

        self.values.append(normalized)

    def addAll(self, inc: int) -> None:
        self.global_add = (self.global_add + inc) % self.MOD

    def multAll(self, m: int) -> None:
        self.global_mul = (self.global_mul * m) % self.MOD
        self.global_add = (self.global_add * m) % self.MOD

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.values):
            return -1

        return (
            self.values[idx] * self.global_mul
            + self.global_add
        ) % self.MOD

# Your Fancy object will be instantiated and called as such:
# obj = Fancy()
# obj.append(val)
# obj.addAll(inc)
# obj.multAll(m)
# param_4 = obj.getIndex(idx)

The implementation closely follows the affine transformation idea.

The constructor initializes:

  • The normalized storage array
  • The multiplicative transformation
  • The additive transformation

The mod_inverse helper computes modular inverse using Fermat's Little Theorem:

x^(MOD-2) mod MOD

This works because 10^9 + 7 is prime.

The append method reverses the current transformation so the inserted element appears exactly as requested.

The addAll method only changes the additive component of the transformation.

The multAll method scales both the multiplicative and additive components because multiplication distributes across the entire affine expression.

The getIndex method reconstructs the current visible value lazily.

Go Solution

package main

const MOD int64 = 1_000_000_007

type Fancy struct {
	values    []int64
	globalMul int64
	globalAdd int64
}

func Constructor() Fancy {
	return Fancy{
		values:    []int64{},
		globalMul: 1,
		globalAdd: 0,
	}
}

func modPow(base, exp int64) int64 {
	result := int64(1)

	for exp > 0 {
		if exp&1 == 1 {
			result = (result * base) % MOD
		}

		base = (base * base) % MOD
		exp >>= 1
	}

	return result
}

func modInverse(x int64) int64 {
	return modPow(x, MOD-2)
}

func (this *Fancy) Append(val int) {
	normalized := (
		(int64(val)-this.globalAdd+MOD)%MOD *
			modInverse(this.globalMul),
	) % MOD

	this.values = append(this.values, normalized)
}

func (this *Fancy) AddAll(inc int) {
	this.globalAdd = (this.globalAdd + int64(inc)) % MOD
}

func (this *Fancy) MultAll(m int) {
	this.globalMul = (this.globalMul * int64(m)) % MOD
	this.globalAdd = (this.globalAdd * int64(m)) % MOD
}

func (this *Fancy) GetIndex(idx int) int {
	if idx >= len(this.values) {
		return -1
	}

	result := (
		this.values[idx]*this.globalMul +
			this.globalAdd,
	) % MOD

	return int(result)
}

/**
 * Your Fancy object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Append(val);
 * obj.AddAll(inc);
 * obj.MultAll(m);
 * param_4 := obj.GetIndex(idx);
 */

The Go solution mirrors the Python implementation closely.

The major Go-specific differences are:

  • Explicit use of int64 to avoid overflow
  • Manual modular exponentiation implementation
  • Slice handling instead of Python lists
  • No built-in modular inverse helper

Go requires careful type conversion between int and int64 during arithmetic.

Worked Examples

Example 1

Operations:

append(2)
addAll(3)
append(7)
multAll(2)
getIndex(0)
addAll(3)
append(10)
multAll(2)
getIndex(0)
getIndex(1)
getIndex(2)

Initial state:

Variable Value
values []
global_mul 1
global_add 0

Step 1: append(2)

Normalized value:

(2 - 0) / 1 = 2
Variable Value
values [2]
global_mul 1
global_add 0

Visible sequence:

[2]

Step 2: addAll(3)

Variable Value
values [2]
global_mul 1
global_add 3

Visible sequence:

[2*1 + 3] = [5]

Step 3: append(7)

Normalize:

(7 - 3) / 1 = 4
Variable Value
values [2, 4]
global_mul 1
global_add 3

Visible sequence:

[5, 7]

Step 4: multAll(2)

Variable Value
values [2, 4]
global_mul 2
global_add 6

Visible sequence:

[2*2+6, 4*2+6]
= [10, 14]

Step 5: getIndex(0)

2*2 + 6 = 10

Return 10.

Step 6: addAll(3)

Variable Value
values [2, 4]
global_mul 2
global_add 9

Visible sequence:

[13, 17]

Step 7: append(10)

Normalize:

(10 - 9) / 2
= 1 * inverse(2)

Stored value becomes modular representation of 1/2.

Step 8: multAll(2)

Variable Value
values [2, 4, 500000004]
global_mul 4
global_add 18

Visible sequence:

26, 34, 20

Returned values:

getIndex(0) = 26
getIndex(1) = 34
getIndex(2) = 20

Complexity Analysis

Measure Complexity Explanation
Time O(1) amortized Each operation performs constant work
Space O(n) Stores all appended values

The only potentially expensive operation is modular inverse computation during append. Using fast exponentiation, modular inverse requires O(log MOD) time, which is effectively constant because MOD is fixed.

Therefore all operations are effectively constant time for the problem constraints.

Test Cases

# Provided example
fancy = Fancy()
fancy.append(2)
fancy.addAll(3)
fancy.append(7)
fancy.multAll(2)

assert fancy.getIndex(0) == 10  # example check

fancy.addAll(3)
fancy.append(10)
fancy.multAll(2)

assert fancy.getIndex(0) == 26  # first element
assert fancy.getIndex(1) == 34  # second element
assert fancy.getIndex(2) == 20  # third element

# Out of bounds access
fancy = Fancy()
assert fancy.getIndex(0) == -1  # empty sequence

# Single append
fancy = Fancy()
fancy.append(5)
assert fancy.getIndex(0) == 5  # basic insertion

# Multiple additions
fancy = Fancy()
fancy.append(1)
fancy.addAll(2)
fancy.addAll(3)
assert fancy.getIndex(0) == 6  # 1 + 2 + 3

# Multiple multiplications
fancy = Fancy()
fancy.append(2)
fancy.multAll(3)
fancy.multAll(4)
assert fancy.getIndex(0) == 24  # 2 * 3 * 4

# Mixed operations
fancy = Fancy()
fancy.append(3)
fancy.addAll(5)
fancy.multAll(2)
assert fancy.getIndex(0) == 16  # (3 + 5) * 2

# Append after transformations
fancy = Fancy()
fancy.addAll(5)
fancy.multAll(3)
fancy.append(7)
assert fancy.getIndex(0) == 7  # new append unaffected by old ops

# Large chain
fancy = Fancy()
for i in range(1000):
    fancy.append(i)

for _ in range(100):
    fancy.addAll(1)
    fancy.multAll(2)

assert fancy.getIndex(0) >= 0  # stress test

# Modulo behavior
fancy = Fancy()
fancy.append(10**9)
fancy.multAll(100)
assert fancy.getIndex(0) == (10**9 * 100) % (10**9 + 7)
Test Why
Provided example Validates official behavior
Empty sequence lookup Ensures out-of-range handling
Single append Verifies base insertion
Repeated additions Tests additive accumulation
Repeated multiplications Tests multiplicative accumulation
Mixed operations Ensures affine composition correctness
Append after transforms Verifies normalization logic
Large stress test Ensures scalability
Large modulo values Verifies modular arithmetic correctness

Edge Cases

One important edge case is accessing an invalid index. Since the sequence size changes dynamically, it is easy to accidentally read beyond the array bounds. The implementation explicitly checks whether idx >= len(values) and returns -1 immediately.

Another tricky case is appending elements after many global transformations. A naive implementation might accidentally apply old operations to newly inserted elements. The normalization step prevents this problem by reversing the current affine transformation before storage.

A third important case involves very large values and repeated operations. Without modulo arithmetic, numbers would quickly overflow standard integer ranges. Every arithmetic operation in the implementation is reduced modulo 10^9 + 7, guaranteeing correctness and preventing overflow issues.

Multiplication by zero is another subtle case. Once global_mul becomes zero, all previous elements collapse to the same value. The affine representation still handles this correctly because subsequent operations continue transforming the collapsed values consistently.