Fancy Sequence

Hard

#1491Time: - `append(val)`: O(1) amortized time. - `addAll(inc)`: O(N) time, where N is the current size of the sequence. - `multAll(m)`: O(N) time. - `getIndex(idx)`: O(1) time.Space: O(N), where N is the number of elements in the sequence (i.e., the number of `append` calls).

Patterns

Math Design

Data structures

Segment Tree

Prompt

Write an API that generates fancy sequences using the append, addAll, and multAll operations.

Implement the Fancy class:

Fancy() Initializes the object with an empty sequence.
void append(val) Appends an integer val to the end of the sequence.
void addAll(inc) Increments all existing values in the sequence by an integer inc.
void multAll(m) Multiplies all existing values in the sequence by an integer m.
int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo 10⁹ + 7. If the index is greater or equal than the length of the sequence, return -1.

Example 1:

Input
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
Output
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

Explanation
Fancy fancy = new Fancy();
fancy.append(2);   // fancy sequence: [2]
fancy.addAll(3);   // fancy sequence: [2+3] -> [5]
fancy.append(7);   // fancy sequence: [5, 7]
fancy.multAll(2);  // fancy sequence: [5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // return 10
fancy.addAll(3);   // fancy sequence: [10+3, 14+3] -> [13, 17]
fancy.append(10);  // fancy sequence: [13, 17, 10]
fancy.multAll(2);  // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20

Constraints:

1 <= val, inc, m <= 100
0 <= idx <= 10⁵
At most 10⁵ calls total will be made to append, addAll, multAll, and getIndex.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the described operations using a list. For append, we add the element to the list. For addAll and multAll, we iterate through the entire list and apply the operation to each element individually. getIndex is a simple lookup.

Algorithm

Use a dynamic array (like ArrayList in Java) to store the numbers of the sequence.
append(val): Add the integer val to the end of the list.
addAll(inc): Iterate through every element in the list and add inc to it.
multAll(m): Iterate through every element in the list and multiply it by m. Remember to take the result modulo 10^9 + 7 at each step to prevent overflow.
getIndex(idx): If the index is valid, return the element at that index. Otherwise, return -1.

Walkthrough

In this naive approach, we maintain a list of numbers, for example, a java.util.ArrayList<Long>. The append operation is efficient, simply adding an element to the end of the list. However, the addAll and multAll operations require us to traverse the entire list, updating each element one by one. While simple to conceive and implement, this leads to poor performance when the sequence is long and these update operations are called frequently.

1import java.util.ArrayList;2import java.util.List;3 4class Fancy {5    private List<Long> seq;6    private final int MOD = 1_000_000_007;7 8    public Fancy() {9        seq = new ArrayList<>();10    }11    12    public void append(int val) {13        seq.add((long) val);14    }15    16    public void addAll(int inc) {17        for (int i = 0; i < seq.size(); i++) {18            seq.set(i, (seq.get(i) + inc) % MOD);19        }20    }21    22    public void multAll(int m) {23        for (int i = 0; i < seq.size(); i++) {24            seq.set(i, (seq.get(i) * m) % MOD);25        }26    }27    28    public int getIndex(int idx) {29        if (idx >= seq.size()) {30            return -1;31        }32        return seq.get(idx).intValue();33    }34}

Complexity

Time

- `append(val)`: O(1) amortized time. - `addAll(inc)`: O(N) time, where N is the current size of the sequence. - `multAll(m)`: O(N) time. - `getIndex(idx)`: O(1) time.

Space

O(N), where N is the number of elements in the sequence (i.e., the number of `append` calls).

Trade-offs

Pros

Very simple to understand and implement.
append and getIndex operations are fast.

Cons

The addAll and multAll operations are very slow, with a time complexity linear in the size of the sequence.
This approach will likely result in a 'Time Limit Exceeded' (TLE) error for large inputs, given the problem constraints.

A highly efficient approach is to use lazy propagation. Instead of updating every element for addAll and multAll, we track the cumulative effect of these operations using two variables: a multiplicative factor mult and an additive factor add. When a value is appended, it's 'normalized' by reversing the current cumulative operations. When getIndex is called, we apply the current cumulative operations to the stored normalized value to get the correct result. This makes addAll, multAll, and getIndex O(1) operations.

Algorithm

Maintain a list seq for the numbers, and two global state variables, add (initially 0) and mult (initially 1).
These variables track the cumulative transformation x -> x * mult + add.
append(val): To counteract the global transformations that haven't been applied to val, store a 'normalized' value. Calculate v_base = (val - add) * modInverse(mult) and append v_base to seq. All calculations are modulo 10^9 + 7.
addAll(inc): Update the additive factor: add = (add + inc) % MOD.
multAll(m): Update both factors: mult = (mult * m) % MOD and add = (add * m) % MOD.
getIndex(idx): Retrieve the normalized value v_base from seq. Apply the current global transformation to get the final value: result = (v_base * mult + add) % MOD.
A helper function for modular exponentiation is needed to compute the modular multiplicative inverse.

Walkthrough

The key insight is that any sequence of additions and multiplications can be combined into a single linear transformation of the form f(x) = x * M + A. We can maintain these cumulative factors, mult (M) and add (A), globally.

When addAll(inc) is called, the transformation x*mult + add becomes (x*mult + add) + inc, which simplifies to x*mult + (add + inc). So, we just update add.
When multAll(m) is called, x*mult + add becomes (x*mult + add) * m, which is x*(mult*m) + (add*m). We update both mult and add.
The tricky part is append(val). A new value val should not be affected by past operations. We store a 'base' value v_base such that when the current global transformation is applied, it yields val. That is, v_base * mult + add = val. Solving for v_base, we get v_base = (val - add) * modInverse(mult). This is the value we store.
For getIndex(idx), we retrieve the stored v_base and apply the current global transformation: (v_base * mult + add) % MOD.

This requires calculating the modular multiplicative inverse, which can be done efficiently using Fermat's Little Theorem (a^(p-2) mod p) since the modulus 10^9 + 7 is prime.

1import java.util.ArrayList;2import java.util.List;3 4class Fancy {5    private final long MOD = 1_000_000_007L;6    private List<Long> seq;7    private long add; // Cumulative additive factor8    private long mult; // Cumulative multiplicative factor9 10    public Fancy() {11        this.seq = new ArrayList<>();12        this.add = 0L;13        this.mult = 1L;14    }15 16    // Modular exponentiation to calculate (base^exp) % MOD17    private long power(long base, long exp) {18        long res = 1;19        base %= MOD;20        while (exp > 0) {21            if (exp % 2 == 1) res = (res * base) % MOD;22            base = (base * base) % MOD;23            exp /= 2;24        }25        return res;26    }27 28    // Modular multiplicative inverse using Fermat's Little Theorem29    private long modInverse(long n) {30        return power(n, MOD - 2);31    }32 33    public void append(int val) {34        long tempVal = val;35        // Normalize the value before storing36        // We need v_base such that: v_base * mult + add = val37        // v_base = (val - add) / mult38        tempVal = (tempVal - add + MOD) % MOD; // Handle negative results from subtraction39        tempVal = (tempVal * modInverse(mult)) % MOD;40        seq.add(tempVal);41    }42 43    public void addAll(int inc) {44        add = (add + inc) % MOD;45    }46 47    public void multAll(int m) {48        mult = (mult * m) % MOD;49        add = (add * m) % MOD;50    }51 52    public int getIndex(int idx) {53        if (idx >= seq.size()) {54            return -1;55        }56        // Apply the cumulative transformations to the stored base value57        long val = seq.get(idx);58        val = (val * mult) % MOD;59        val = (val + add) % MOD;60        return (int) val;61    }62}

Complexity

Time

- `append(val)`: O(log MOD) due to the modular inverse calculation (which uses modular exponentiation). - `addAll(inc)`: O(1). - `multAll(m)`: O(1). - `getIndex(idx)`: O(1).

Space

O(N), where N is the number of `append` calls, to store the normalized sequence.

Trade-offs

Pros

Extremely efficient, with addAll, multAll, and getIndex all being constant time operations.
This approach will pass within the time limits for the given constraints.

Cons

The logic is more complex, involving modular arithmetic, modular inverse, and the concept of normalizing values.
Requires careful implementation to handle potential overflows by using long for intermediate calculations and applying the modulo operator correctly.

Solutions

Solution

1class Node { Node left ; Node right ; int l ; int r ; int mid ; long v ; long add ; long mul = 1 ; public Node ( int l , int r ) { this . l = l ; this . r = r ; this . mid = ( l + r ) >> 1 ; } } class SegmentTree { private Node root = new Node ( 1 , ( int ) 1 e5 + 1 ); private static final int MOD = ( int ) 1 e9 + 7 ; public SegmentTree () { } public void modifyAdd ( int l , int r , int inc ) { modifyAdd ( l , r , inc , root ); } public void modifyAdd ( int l , int r , int inc , Node node ) { if ( l > r ) { return ; } if ( node . l >= l && node . r <= r ) { node . v = ( node . v + ( node . r - node . l + 1 ) * inc ) % MOD ; node . add = ( node . add + inc ) % MOD ; return ; } pushdown ( node ); if ( l <= node . mid ) { modifyAdd ( l , r , inc , node . left ); } if ( r > node . mid ) { modifyAdd ( l , r , inc , node . right ); } pushup ( node ); } public void modifyMul ( int l , int r , int m ) { modifyMul ( l , r , m , root ); } public void modifyMul ( int l , int r , int m , Node node ) { if ( l > r ) { return ; } if ( node . l >= l && node . r <= r ) { node . v = ( node . v * m ) % MOD ; node . add = ( node . add * m ) % MOD ; node . mul = ( node . mul * m ) % MOD ; return ; } pushdown ( node ); if ( l <= node . mid ) { modifyMul ( l , r , m , node . left ); } if ( r > node . mid ) { modifyMul ( l , r , m , node . right ); } pushup ( node ); } public int query ( int l , int r ) { return query ( l , r , root ); } public int query ( int l , int r , Node node ) { if ( l > r ) { return 0 ; } if ( node . l >= l && node . r <= r ) { return ( int ) node . v ; } pushdown ( node ); int v = 0 ; if ( l <= node . mid ) { v = ( v + query ( l , r , node . left )) % MOD ; } if ( r > node . mid ) { v = ( v + query ( l , r , node . right )) % MOD ; } return v ; } public void pushup ( Node node ) { node . v = ( node . left . v + node . right . v ) % MOD ; } public void pushdown ( Node node ) { if ( node . left == null ) { node . left = new Node ( node . l , node . mid ); } if ( node . right == null ) { node . right = new Node ( node . mid + 1 , node . r ); } if ( node . add != 0 || node . mul != 1 ) { Node left = node . left , right = node . right ; left . v = ( left . v * node . mul + ( left . r - left . l + 1 ) * node . add ) % MOD ; right . v = ( right . v * node . mul + ( right . r - right . l + 1 ) * node . add ) % MOD ; left . add = ( left . add * node . mul + node . add ) % MOD ; right . add = ( right . add * node . mul + node . add ) % MOD ; left . mul = ( left . mul * node . mul ) % MOD ; right . mul = ( right . mul * node . mul ) % MOD ; node . add = 0 ; node . mul = 1 ; } } } class Fancy { private int n ; private SegmentTree tree = new SegmentTree (); public Fancy () { } public void append ( int val ) { ++ n ; tree . modifyAdd ( n , n , val ); } public void addAll ( int inc ) { tree . modifyAdd ( 1 , n , inc ); } public void multAll ( int m ) { tree . modifyMul ( 1 , n , m ); } public int getIndex ( int idx ) { return idx >= n ? - 1 : tree . query ( idx + 1 , idx + 1 ); } } /** * Your Fancy object will be instantiated and called as such: * Fancy obj = new Fancy(); * obj.append(val); * obj.addAll(inc); * obj.multAll(m); * int param_4 = obj.getIndex(idx); */

1const int MOD = 1e9 + 7 ; class Node { public: Node * left ; Node * right ; int l ; int r ; int mid ; long long v ; long long add ; long long mul ; Node ( int l , int r ) { this -> l = l ; this -> r = r ; this -> mid = ( l + r ) >> 1 ; this -> left = this -> right = nullptr ; v = add = 0 ; mul = 1 ; } }; class SegmentTree { private: Node * root ; public: SegmentTree () { root = new Node ( 1 , 1e5 + 1 ); } void modifyAdd ( int l , int r , int inc ) { modifyAdd ( l , r , inc , root ); } void modifyAdd ( int l , int r , int inc , Node * node ) { if ( l > r ) return ; if ( node -> l >= l && node -> r <= r ) { node -> v = ( node -> v + ( node -> r - node -> l + 1 ) * inc ) % MOD ; node -> add = ( node -> add + inc ) % MOD ; return ; } pushdown ( node ); if ( l <= node -> mid ) modifyAdd ( l , r , inc , node -> left ); if ( r > node -> mid ) modifyAdd ( l , r , inc , node -> right ); pushup ( node ); } void modifyMul ( int l , int r , int m ) { modifyMul ( l , r , m , root ); } void modifyMul ( int l , int r , int m , Node * node ) { if ( l > r ) return ; if ( node -> l >= l && node -> r <= r ) { node -> v = ( node -> v * m ) % MOD ; node -> add = ( node -> add * m ) % MOD ; node -> mul = ( node -> mul * m ) % MOD ; return ; } pushdown ( node ); if ( l <= node -> mid ) modifyMul ( l , r , m , node -> left ); if ( r > node -> mid ) modifyMul ( l , r , m , node -> right ); pushup ( node ); } int query ( int l , int r ) { return query ( l , r , root ); } int query ( int l , int r , Node * node ) { if ( l > r ) return 0 ; if ( node -> l >= l && node -> r <= r ) return node -> v ; pushdown ( node ); int v = 0 ; if ( l <= node -> mid ) v = ( v + query ( l , r , node -> left )) % MOD ; if ( r > node -> mid ) v = ( v + query ( l , r , node -> right )) % MOD ; return v ; } void pushup ( Node * node ) { node -> v = ( node -> left -> v + node -> right -> v ) % MOD ; } void pushdown ( Node * node ) { if ( ! node -> left ) node -> left = new Node ( node -> l , node -> mid ); if ( ! node -> right ) node -> right = new Node ( node -> mid + 1 , node -> r ); if ( node -> add || node -> mul != 1 ) { long add = node -> add , mul = node -> mul ; Node * left = node -> left ; Node * right = node -> right ; left -> v = ( left -> v * mul + ( left -> r - left -> l + 1 ) * add ) % MOD ; right -> v = ( right -> v * mul + ( right -> r - right -> l + 1 ) * add ) % MOD ; left -> add = ( left -> add * mul + add ) % MOD ; right -> add = ( right -> add * mul + add ) % MOD ; left -> mul = ( left -> mul * mul ) % MOD ; right -> mul = ( right -> mul * mul ) % MOD ; node -> add = 0 ; node -> mul = 1 ; } } }; class Fancy { public: int n ; SegmentTree * tree ; Fancy () { n = 0 ; tree = new SegmentTree (); } void append ( int val ) { ++ n ; tree -> modifyAdd ( n , n , val ); } void addAll ( int inc ) { tree -> modifyAdd ( 1 , n , inc ); } void multAll ( int m ) { tree -> modifyMul ( 1 , n , m ); } int getIndex ( int idx ) { return idx >= n ? - 1 : tree -> query ( idx + 1 , idx + 1 ); } }; /** * Your Fancy object will be instantiated and called as such: * Fancy* obj = new Fancy(); * obj->append(val); * obj->addAll(inc); * obj->multAll(m); * int param_4 = obj->getIndex(idx); */

1MOD = int ( 1e9 + 7 ) class Node : def __init__ ( self , l , r ): self . left = None self . right = None self . l = l self . r = r self . mid = ( l + r ) >> 1 self . v = 0 self . add = 0 self . mul = 1 class SegmentTree : def __init__ ( self ): self . root = Node ( 1 , int ( 1e5 + 1 )) def modifyAdd ( self , l , r , inc , node = None ): if l > r : return if node is None : node = self . root if node . l >= l and node . r <= r : node . v = ( node . v + ( node . r - node . l + 1 ) * inc ) % MOD node . add += inc return self . pushdown ( node ) if l <= node . mid : self . modifyAdd ( l , r , inc , node . left ) if r > node . mid : self . modifyAdd ( l , r , inc , node . right ) self . pushup ( node ) def modifyMul ( self , l , r , m , node = None ): if l > r : return if node is None : node = self . root if node . l >= l and node . r <= r : node . v = ( node . v * m ) % MOD node . add = ( node . add * m ) % MOD node . mul = ( node . mul * m ) % MOD return self . pushdown ( node ) if l <= node . mid : self . modifyMul ( l , r , m , node . left ) if r > node . mid : self . modifyMul ( l , r , m , node . right ) self . pushup ( node ) def query ( self , l , r , node = None ): if l > r : return 0 if node is None : node = self . root if node . l >= l and node . r <= r : return node . v self . pushdown ( node ) v = 0 if l <= node . mid : v = ( v + self . query ( l , r , node . left )) % MOD if r > node . mid : v = ( v + self . query ( l , r , node . right )) % MOD return v def pushup ( self , node ): node . v = ( node . left . v + node . right . v ) % MOD def pushdown ( self , node ): if node . left is None : node . left = Node ( node . l , node . mid ) if node . right is None : node . right = Node ( node . mid + 1 , node . r ) left , right = node . left , node . right if node . add != 0 or node . mul != 1 : left . v = ( left . v * node . mul + ( left . r - left . l + 1 ) * node . add ) % MOD right . v = ( right . v * node . mul + ( right . r - right . l + 1 ) * node . add ) % MOD left . add = ( left . add * node . mul + node . add ) % MOD right . add = ( right . add * node . mul + node . add ) % MOD left . mul = ( left . mul * node . mul ) % MOD right . mul = ( right . mul * node . mul ) % MOD node . add = 0 node . mul = 1 class Fancy : def __init__ ( self ): self . n = 0 self . tree = SegmentTree () def append ( self , val : int ) -> None : self . n += 1 self . tree . modifyAdd ( self . n , self . n , val ) def addAll ( self , inc : int ) -> None : self . tree . modifyAdd ( 1 , self . n , inc ) def multAll ( self , m : int ) -> None : self . tree . modifyMul ( 1 , self . n , m ) def getIndex ( self , idx : int ) -> int : return - 1 if idx >= self . n else self . tree . query ( idx + 1 , idx + 1 ) # 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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem