Arithmetic Slices II (All Subsequences)

▶

Steps

setup

Initialize dp array and total count

Create an array dp of length n, where each element is an empty hash map to store counts of subsequences by difference. Initialize total count to zero.

💡 This sets up the data structure to track counts of arithmetic subsequences ending at each index by their difference.

Line:

n = len(nums)
dp = [defaultdict(int) for _ in range(n)]
total = 0

💡 We need a separate map for each index to track subsequences ending there with various differences.

fill_row

Start outer loop with i=1

Begin processing index i=1 (nums[1] = 4). Prepare to compare with all previous indices j < i.

💡 We will find differences between nums[1] and previous elements to update dp[1].

Line:

for i in range(n):
    for j in range(i):

💡 Each i extends subsequences ending at j by checking differences.

compare

Calculate difference for j=0, i=1

Calculate difference diff = nums[1] - nums[0] = 4 - 2 = 2. Retrieve count_at_j = dp[0][2] which is 0 since dp[0] is empty.

💡 Difference identifies the arithmetic progression pattern; count_at_j tells how many subsequences with this diff end at j.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 No subsequences with diff=2 end at index 0 yet, so count_at_j is zero.

fill_cells

Update dp[1][2] and total count

Update dp[1][2] by adding count_at_j + 1 = 0 + 1 = 1. total remains 0 because count_at_j is 0 (no subsequences extended).

💡 Adding 1 accounts for the new pair (nums[0], nums[1]) which may form subsequences later.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Pairs are stored but not counted towards total since subsequences must have length >= 3.

fill_row

Start outer loop with i=2

Begin processing index i=2 (nums[2] = 6). Prepare to compare with all previous indices j < i.

💡 We will find differences between nums[2] and previous elements to update dp[2].

Line:

for i in range(n):
    for j in range(i):

💡 Each i extends subsequences ending at j by checking differences.

compare

Calculate difference for j=0, i=2

Calculate diff = nums[2] - nums[0] = 6 - 2 = 4. Retrieve count_at_j = dp[0][4] which is 0.

💡 No subsequences with diff=4 end at index 0 yet.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 We will add a new pair (2,6) with diff=4.

fill_cells

Update dp[2][4] and total count

Update dp[2][4] = 0 + 1 = 1. total remains 0 because count_at_j is 0.

💡 Store the new pair (2,6) for future subsequence extensions.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Pairs are building blocks for longer subsequences.

compare

Calculate difference for j=1, i=2

Calculate diff = nums[2] - nums[1] = 6 - 4 = 2. Retrieve count_at_j = dp[1][2] = 1.

💡 There is 1 subsequence ending at index 1 with diff=2, so we can extend it.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 Extending existing subsequences increases total count.

fill_cells

Update dp[2][2] and total count

Update dp[2][2] = dp[2][2] + count_at_j + 1 = 0 + 1 + 1 = 2. Add count_at_j = 1 to total, total becomes 1.

💡 We add 1 for the new pair (4,6) and count_at_j for extending subsequences ending at j=1.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Extending subsequences increases total count by the number of subsequences extended.

fill_row

Start outer loop with i=3

Begin processing index i=3 (nums[3] = 8). Prepare to compare with all previous indices j < i.

💡 We will find differences between nums[3] and previous elements to update dp[3].

Line:

for i in range(n):
    for j in range(i):

💡 Each i extends subsequences ending at j by checking differences.

compare

Calculate difference for j=0, i=3

Calculate diff = nums[3] - nums[0] = 8 - 2 = 6. Retrieve count_at_j = dp[0][6] = 0.

💡 No subsequences with diff=6 end at index 0 yet.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 We will add a new pair (2,8) with diff=6.

fill_cells

Update dp[3][6] and total count

Update dp[3][6] = 0 + 1 = 1. total remains 1 because count_at_j is 0.

💡 Store the new pair (2,8) for future subsequence extensions.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Pairs are building blocks for longer subsequences.

compare

Calculate difference for j=1, i=3

Calculate diff = nums[3] - nums[1] = 8 - 4 = 4. Retrieve count_at_j = dp[1][4] = 0 (dp[1] has only diff=2).

💡 No subsequences with diff=4 end at index 1 yet.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 We will add a new pair (4,8) with diff=4.

fill_cells

Update dp[3][4] and total count

Update dp[3][4] = 0 + 1 = 1. total remains 1 because count_at_j is 0.

💡 Store the new pair (4,8) for future subsequence extensions.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Pairs are building blocks for longer subsequences.

compare

Calculate difference for j=2, i=3

Calculate diff = nums[3] - nums[2] = 8 - 6 = 2. Retrieve count_at_j = dp[2][2] = 2.

💡 There are 2 subsequences ending at index 2 with diff=2, so we can extend them.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 Extending existing subsequences increases total count.

fill_cells

Update dp[3][2] and total count

Update dp[3][2] = 0 + 2 + 1 = 3. Add count_at_j = 2 to total, total becomes 3.

💡 We add 1 for the new pair (6,8) and count_at_j for extending subsequences ending at j=2.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Extending subsequences increases total count by the number of subsequences extended.

fill_row

Start outer loop with i=4

Begin processing index i=4 (nums[4] = 10). Prepare to compare with all previous indices j < i.

💡 We will find differences between nums[4] and previous elements to update dp[4].

Line:

for i in range(n):
    for j in range(i):

💡 Each i extends subsequences ending at j by checking differences.

compare

Calculate difference for j=0, i=4

Calculate diff = nums[4] - nums[0] = 10 - 2 = 8. Retrieve count_at_j = dp[0][8] = 0.

💡 No subsequences with diff=8 end at index 0 yet.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 We will add a new pair (2,10) with diff=8.

fill_cells

Update dp[4][8] and total count

Update dp[4][8] = 0 + 1 = 1. total remains 3 because count_at_j is 0.

💡 Store the new pair (2,10) for future subsequence extensions.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Pairs are building blocks for longer subsequences.

compare

Calculate difference for j=1, i=4

Calculate diff = nums[4] - nums[1] = 10 - 4 = 6. Retrieve count_at_j = dp[1][6] = 0 (dp[1] has only diff=2).

💡 No subsequences with diff=6 end at index 1 yet.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 We will add a new pair (4,10) with diff=6.

fill_cells

Update dp[4][6] and total count

Update dp[4][6] = 0 + 1 = 1. total remains 3 because count_at_j is 0.

💡 Store the new pair (4,10) for future subsequence extensions.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Pairs are building blocks for longer subsequences.

compare

Calculate difference for j=2, i=4

Calculate diff = nums[4] - nums[2] = 10 - 6 = 4. Retrieve count_at_j = dp[2][4] = 1.

💡 There is 1 subsequence ending at index 2 with diff=4, so we can extend it.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 Extending existing subsequences increases total count.

fill_cells

Update dp[4][4] and total count

Update dp[4][4] = 0 + 1 + 1 = 2. Add count_at_j = 1 to total, total becomes 4.

💡 We add 1 for the new pair (6,10) and count_at_j for extending subsequences ending at j=2.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Extending subsequences increases total count by the number of subsequences extended.

compare

Calculate difference for j=3, i=4

Calculate diff = nums[4] - nums[3] = 10 - 8 = 2. Retrieve count_at_j = dp[3][2] = 3.

💡 There are 3 subsequences ending at index 3 with diff=2, so we can extend them.

Line:

diff = nums[i] - nums[j]
count_at_j = dp[j][diff]

💡 Extending existing subsequences increases total count.

fill_cells

Update dp[4][2] and total count

Update dp[4][2] = 0 + 3 + 1 = 4. Add count_at_j = 3 to total, total becomes 7.

💡 We add 1 for the new pair (8,10) and count_at_j for extending subsequences ending at j=3.

Line:

dp[i][diff] += count_at_j + 1
total += count_at_j

💡 Extending subsequences increases total count by the number of subsequences extended.

reconstruct

Return total count

All pairs and subsequences processed. Return total = 7, the count of arithmetic subsequences of length >= 3.

💡 The total accumulated during iteration counts all valid arithmetic subsequences.

Line:

return total

💡 The algorithm efficiently counts subsequences without enumerating them.

from collections import defaultdict

def numberOfArithmeticSlices(nums):
    n = len(nums)  # STEP 1
    dp = [defaultdict(int) for _ in range(n)]  # STEP 1
    total = 0  # STEP 1
    for i in range(n):  # STEP 2,5,10,17
        for j in range(i):  # STEP 2,5,10,17
            diff = nums[i] - nums[j]  # STEP 3,6,8,11,13,15,18,20,22,24
            count_at_j = dp[j][diff]  # STEP 3,6,8,11,13,15,18,20,22,24
            dp[i][diff] += count_at_j + 1  # STEP 4,7,9,12,14,16,19,21,23,25
            total += count_at_j  # STEP 4,7,9,12,14,16,19,21,23,25
    return total  # STEP 26

if __name__ == '__main__':
    print(numberOfArithmeticSlices([2,4,6,8,10]))  # 7

📊

Arithmetic Slices II (All Subsequences) - Watch the Algorithm Execute, Step by Step

Watching each update to dp and the total count reveals how subsequences are counted without enumerating them explicitly, which is the key to efficient solution.

Item 0 - wt:0 val:2

i\w	0
i=0	{}
i=1	{}
i=2	{}
i=3	{}
i=4	{}

Item 1 - wt:0 val:4

i\w	0
i=0	{}
i=1	{}
i=2	{}
i=3	{}
i=4	{}

Processing i=1

Item 1 - wt:2 val:4

i\w	0
i=0	{}
i=1	{}
i=2	{}
i=3	{}
i=4	{}

dp[0] empty for diff=2

Item 1 - wt:2 val:4

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{}
i=3	{}
i=4	{}

dp[1][2] = 1

Item 2 - wt:0 val:6

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{}
i=3	{}
i=4	{}

Processing i=2

Item 2 - wt:4 val:6

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{}
i=3	{}
i=4	{}

dp[0] empty for diff=4

Item 2 - wt:4 val:6

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"4":1}
i=3	{}
i=4	{}

dp[2][4] = 1

Item 2 - wt:2 val:6

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"4":1}
i=3	{}
i=4	{}

dp[1][2] = 1

Item 2 - wt:2 val:6

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{}
i=4	{}

dp[2][2] = 2

Item 3 - wt:0 val:8

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{}
i=4	{}

Processing i=3

Item 3 - wt:6 val:8

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{}
i=4	{}

dp[0] empty for diff=6

Item 3 - wt:6 val:8

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"6":1}
i=4	{}

dp[3][6] = 1

Item 3 - wt:4 val:8

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"6":1}
i=4	{}

dp[1] no diff=4

Item 3 - wt:4 val:8

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"4":1,"6":1}
i=4	{}

dp[3][4] = 1

Item 3 - wt:2 val:8

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"4":1,"6":1}
i=4	{}

dp[2][2] = 2

Item 3 - wt:2 val:8

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{}

dp[3][2] = 3

Item 4 - wt:0 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{}

Processing i=4

Item 4 - wt:8 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{}

dp[0] no diff=8

Item 4 - wt:8 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{"8":1}

dp[4][8] = 1

Item 4 - wt:6 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{"8":1}

dp[1] no diff=6

Item 4 - wt:6 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{"6":1,"8":1}

dp[4][6] = 1

Item 4 - wt:4 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{"6":1,"8":1}

dp[2][4] = 1

Item 4 - wt:4 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{"4":2,"6":1,"8":1}

dp[4][4] = 2

Item 4 - wt:2 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{"4":2,"6":1,"8":1}

dp[3][2] = 3

Item 4 - wt:2 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{"2":4,"4":2,"6":1,"8":1}

dp[4][2] = 4

Item 4 - wt:0 val:10

i\w	0
i=0	{}
i=1	{"2":1}
i=2	{"2":2,"4":1}
i=3	{"2":3,"4":1,"6":1}
i=4	{"2":4,"4":2,"6":1,"8":1}

Final dp and answer

Key Takeaways

✓ The dp array of hash maps efficiently counts arithmetic subsequences by difference without enumerating them.

This insight is hard to see from code alone because the counting logic is implicit in the map updates.

✓ Each dp[i][diff] accumulates counts from dp[j][diff] for all j < i, showing how subsequences extend step-by-step.

Visualizing this dependency clarifies why the order of iteration matters and how subsequences build up.

✓ Pairs (length 2 subsequences) are stored but not counted towards the total; only extensions of these pairs contribute to the final count.

This distinction explains why total only increases by count_at_j and not by the '+1' added to dp[i][diff].

Practice

1. You are given a binary tree where each node contains an integer value (which can be negative). You need to find the maximum sum of values along any path in the tree, where a path can start and end at any node and must be connected through parent-child links. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Depth-first search with dynamic programming on trees, tracking maximum gains from subtrees and updating a global maximum path sum

B. Divide and conquer by splitting the tree into subtrees and combining their maximum sums without considering paths crossing the root

C. Breadth-first search to find the longest path and sum node values along it

D. Greedy traversal selecting the maximum child at each node without backtracking

Solution

1. Step 1: Understand the problem constraints

   The path can start and end at any node, and may include both left and right children of a node, so a simple greedy or BFS approach won't capture all possibilities.

2. Step 2: Identify the correct algorithmic pattern

   Dynamic programming on trees with DFS allows computing maximum gains from left and right subtrees and updating a global maximum path sum that includes paths passing through the current node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP on trees with global tracking handles negative values and arbitrary path start/end [OK]

Hint: DP on trees tracks max gains and global max path sum [OK]

Common Mistakes:

• Greedy misses paths crossing nodes
• BFS doesn't handle arbitrary start/end
• Divide and conquer misses cross-root paths

2. Given the following code for the House Robber III problem, what is the final returned value when called with the tree below? Tree structure: ``` 3 / \ 2 3 \ \ 3 1 ```

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[0] + right[0]
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob(root))

easy

A. 6

B. 9

C. 8

D. 7

Solution

1. Step 1: Trace dfs on leaf nodes

   Leaf nodes 3 and 1 return (0,3) and (0,1) respectively.

2. Step 2: Compute dfs for internal nodes

   Node 2: rob_node = 2 + 0 + 0 = 2, not_rob_node = max(0,3) + 0 = 3; returns (3,2). Node 3 (right child): rob_node = 3 + 0 + 0 = 3, not_rob_node = 0 + max(0,1) = 1; returns (1,3). Root 3: rob_node = 3 + 3 + 1 = 7, not_rob_node = max(3,2) + max(1,3) = 3 + 3 = 6.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Maximum is max(6,7) = 7 [OK]

Hint: Trace bottom-up dp states carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Confusing rob and not_rob states at nodes

3. You are given an undirected graph with n nodes. The task is to find the shortest path length that visits every node at least once. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A bottom-up dynamic programming approach using bitmasking to represent visited nodes and states.

B. A depth-first search (DFS) that explores all permutations of node visits without memoization.

C. A simple breadth-first search (BFS) without tracking visited subsets of nodes.

D. A greedy algorithm that always moves to the nearest unvisited node until all nodes are visited.

Solution

1. Step 1: Understand the problem constraints

   The problem requires visiting all nodes with the shortest path, which is a variant of the Traveling Salesman Problem (TSP) on a graph.

2. Step 2: Identify the suitable algorithmic pattern

   Greedy or simple BFS/DFS without tracking visited subsets cannot guarantee optimality or efficiency. Bitmask DP efficiently encodes visited nodes and uses state transitions to find the shortest path.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask DP is the classic approach for shortest path visiting all nodes [OK]

Hint: Bitmask DP tracks visited subsets optimally [OK]

Common Mistakes:

• Assuming greedy is optimal
• Ignoring visited subsets in BFS
• Trying DFS without memoization

4. Examine the following buggy code snippet for shortest path visiting all nodes. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line setting base cases: dp[i][1 << i] = 0

B. Line updating next_mask: next_mask = mask ^ (1 << v)

C. Line with dp initialization: dp = [[float('inf')] * (1 << n) for _ in range(n)]

D. Line updating dp[v][next_mask]: dp[v][next_mask] = dp[u][mask] + 1

Solution

1. Step 1: Identify how visited nodes are tracked

   Visited nodes are represented by a bitmask. To add a visited node, bitwise OR (|) must be used.

2. Step 2: Spot the incorrect bitmask operation

   The code uses XOR (^) instead of OR (|) to update next_mask, which can incorrectly unset bits and cause wrong states or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Using XOR breaks the visited set semantics [OK]

Hint: Visited mask update must use OR, not XOR [OK]

Common Mistakes:

• Using XOR instead of OR for mask update
• Forgetting to initialize dp base cases
• Not checking dp[u][mask] == inf before continuing

5. Suppose the problem is modified so that caps can be assigned to multiple people (i.e., caps are no longer unique). Which of the following algorithmic changes correctly adapts the solution to count the number of ways to assign caps without uniqueness constraints?

hard

A. Remove bitmask tracking and use simple multiplication of counts per person

B. Keep bitmask DP but allow assigning the same cap multiple times by not checking mask bits

C. Use a DP over persons only, multiplying the number of caps each person can wear

D. Use a nested loop over persons and caps without bitmask, summing ways for each person independently

Solution

1. Step 1: Understand the uniqueness constraint removal

   Without uniqueness, caps can be reused freely, so no need to track assigned caps with bitmasks.

2. Step 2: Simplify counting approach

   Counting ways reduces to multiplying the number of caps each person can wear, as assignments are independent.

3. Step 3: Why other options fail

   Bitmask DP is unnecessary and incorrect if caps can be reused; summing independently without multiplication misses combinations.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing bitmask and multiplying counts per person matches problem relaxation [OK]

Hint: No uniqueness -> no bitmask needed, multiply counts [OK]

Common Mistakes:

• Trying to keep bitmask DP unnecessarily
• Summing instead of multiplying counts