#1622

Hard

LeetCode Problem Workspace

Fancy Sequence

Implement a Fancy sequence supporting append, addAll, and multAll operations efficiently using cumulative math design techniques.

math design segment tree

Problem Statement

Design a Fancy sequence API that supports dynamic numeric operations. Implement a class Fancy with append, addAll, multAll, and getIndex methods, managing sequences where each operation affects all or some elements efficiently.

Specifically, append(val) adds a value to the end of the sequence, addAll(inc) increments all elements by a number, multAll(m) multiplies all elements by a number, and getIndex(idx) retrieves the current value at a specific index. Optimize the implementation to handle up to 10^5 operations without recomputing the full sequence each time.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 <= 105
At most 105 calls total will be made to append, addAll, multAll, and getIndex.

Solution Approach

Use cumulative multipliers and additive offsets

Maintain two arrays: one for the cumulative multipliers applied up to each append and one for the cumulative sums adjusted by the current multiplier. This lets you compute any element's current value with constant-time arithmetic instead of iterating the entire sequence.

Implement lazy updates for addAll and multAll

Instead of updating all existing elements on every addAll or multAll, store the total additive and multiplicative effects separately. Apply these lazily when getIndex is called, ensuring operations are efficient even for long sequences.

Handle modular arithmetic for large values

Because repeated multiplications and additions can grow numbers rapidly, perform all operations modulo a large prime (e.g., 10^9+7) to prevent overflow while preserving correctness. This ensures the Fancy sequence remains accurate across many operations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity per operation is O(1) for append, addAll, multAll, and getIndex due to cumulative tracking. Space complexity is O(n) for storing the sequence and cumulative multipliers.

What Interviewers Usually Probe

Candidate optimizes getIndex using cumulative multipliers instead of iterating over the entire sequence.
Candidate identifies that naive full sequence updates will exceed time limits with 10^5 operations.
Candidate uses modular arithmetic to handle potential integer overflow and maintain correct results.

Common Pitfalls or Variants

Common pitfalls

Updating every element on addAll or multAll leads to TLE for large sequences.
Neglecting modular arithmetic can result in integer overflow and incorrect answers.
Incorrectly tracking cumulative multipliers or sums may return wrong getIndex values.

Follow-up variants

Implement a similar sequence API but supporting range queries and updates instead of single-element getIndex.
Optimize Fancy sequence operations for floating-point numbers with precision constraints.
Design a Fancy sequence variant that supports undoing the last operation efficiently.

FAQ

What is the optimal approach for Fancy Sequence to handle many operations?

Use cumulative multipliers and adjusted sums to allow append, addAll, multAll, and getIndex operations in constant time.

Why can't I update all elements on addAll or multAll directly?

Direct updates take O(n) per operation, leading to timeouts for sequences with up to 10^5 operations.

How does modular arithmetic help in Fancy Sequence?

It prevents integer overflow during repeated multiplications and additions while preserving correctness of results.

Can getIndex be computed in O(1) with this approach?

Yes, by using cumulative multipliers and adjusted sums, getIndex accesses are constant time without traversing the sequence.

How does the Math plus Design pattern appear in Fancy Sequence?

The problem combines math operations (add, multiply) with careful design of data tracking arrays for efficiency.

terminal

Solution

Solution 1

#### Python3

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

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

MOD = 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)

Continue Practicing

#1352 product of the last k numbers #2080 range frequency queries #1157 online majority element in subarray