LeetCode 446: Arithmetic Slices II - Subsequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 446: Arithmetic Slices II - Subsequence?

In LeetCode 446: Arithmetic Slices II - Subsequence, you’re given an array of integers nums, and your task is to count the total number of arithmetic subsequences—subsequences (not necessarily contiguous) with at least three elements where the difference between consecutive elements is constant. For example, in [2, 4, 6, 8, 10], subsequences like [2, 4, 6] (diff = 2) or [4, 6, 8, 10] (diff = 2) count, totaling 7 valid slices. It’s like finding all the rhythmic patterns hidden in a list of numbers.

Problem Statement

• Input: nums (List[int])—array of integers.
• Output: int—number of arithmetic subsequences with length ≥ 3.
• Rules:
• Subsequence: any sequence derivable by deleting elements without changing order.
• Arithmetic: constant difference between consecutive elements.
• Length must be at least 3.

Constraints

• 1 <= nums.length <= 1000.
• -2^31 <= nums[i] <= 2^31 - 1.

Examples to Get Us Started

• Input: nums = [2,4,6,8,10]
• Output: 7 (Subsequences: [2,4,6], [2,4,6,8], [2,4,6,8,10], [2,6,10], [4,6,8], [4,6,8,10], [6,8,10]).
• Input: nums = [7,7,7,7,7]
• Output: 16 (Many combinations of 3, 4, 5 sevens).
• Input: nums = [1,2,4]
• Output: 0 (No length ≥ 3 arithmetic subsequence).

Understanding the Problem: Finding the Rhythms

To solve LeetCode 446: Arithmetic Slices II - Subsequence in Python, we need to count all subsequences of length 3 or more with a fixed difference, where elements can be non-consecutive. A naive approach—listing all subsequences—would be O(2^n), impractical for n = 1000. Instead, we can use the arithmetic property to build solutions incrementally. We’ll explore:

• Best Solution (DP with Hash Map): O(n²) time, O(n²) space—smart and scalable.
• Alternative Solution (Brute Force): O(2^n) time, O(n) space—clear but slow.

Let’s dive into the DP solution—it’s the rhythm finder we need.

Best Solution: Dynamic Programming with Hash Map

Why This Is the Best Solution

The DP with hash map approach is the top pick because it’s O(n²) time and O(n²) space, efficiently counting arithmetic subsequences by tracking differences at each index. It uses a list of hash maps, where each map stores the count of subsequences ending at that index with a specific difference. It’s like keeping a musical score, noting every beat pattern as you go—brilliant and fast!

How It Works

Here’s the strategy:

• Step 1: Create a DP array where dp[i] is a hash map: {diff: count of subsequences ending at nums[i]}.
• Step 2: For each index i:
• Look back at j < i.
• Compute diff = nums[i] - nums[j].
• Add subsequences ending at j with diff, plus new pairs.
• Step 3: Sum counts for subsequences of length ≥ 3.
• Why It Works:
• Builds longer sequences from shorter ones.
• Hash map tracks all differences efficiently.

Step-by-Step Example

Example: nums = [2,4,6,8,10]

• DP Setup: dp = [{}, {}, {}, {}, {}].
• Process:
• i=1 (4):
• j=0: diff = 4-2 = 2, dp[1][2] = 1 (pair [2,4]).
• i=2 (6):
• j=0: diff = 6-2 = 4, dp[2][4] = 1.
• j=1: diff = 6-4 = 2, dp[2][2] = 1 + dp[1][2] = 2 ([2,4,6]).
• Count += 1 ([2,4,6]).
• i=3 (8):
• j=0: diff = 8-2 = 6, dp[3][6] = 1.
• j=1: diff = 8-4 = 4, dp[3][4] = 1.
• j=2: diff = 8-6 = 2, dp[3][2] = 2 + dp[2][2] = 4 ([2,4,6,8], [4,6,8]).
• Count += 2.
• i=4 (10):
• j=0: diff = 10-2 = 8, dp[4][8] = 1.
• j=1: diff = 10-4 = 6, dp[4][6] = 1.
• j=2: diff = 10-6 = 4, dp[4][4] = 1.
• j=3: diff = 10-8 = 2, dp[4][2] = 4 + dp[3][2] = 8 ([2,4,6,8,10], [4,6,8,10], …).
• Count += 4.
• Result: 7 (all length ≥ 3 subsequences).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return 0

        # dp[i] maps diff -> count of subsequences ending at i
        dp = [{} for _ in range(len(nums))]
        total = 0

        # Iterate over all pairs
        for i in range(1, len(nums)):
            for j in range(i):
                diff = nums[i] - nums[j]

                # Count from previous subsequences
                count = dp[j].get(diff, 0)
                total += count

                # Update dp[i] with new subsequence
                dp[i][diff] = dp[i].get(diff, 0) + count + 1

        return total

• Line 3-4: Early exit for small arrays.
• Line 7: Initialize dp as list of hash maps.
• Line 10-17: Double loop:
• Compute diff for pair (j, i).
• Add existing subsequences with diff to total.
• Update dp[i][diff] with new count (pair + extensions).
• Line 19: Return total count.
• Time Complexity: O(n²)—all pairs.
• Space Complexity: O(n²)—hash map entries.

It’s like a pattern tracker on steroids!

Alternative Solution: Brute Force Enumeration

Why an Alternative Approach?

The brute force method enumerates all subsequences—O(2^n) time, O(n) space—checking each for arithmetic properties. It’s slow but straightforward, like manually listing every possible rhythm in the array. Great for small n or intuition-building!

How It Works

• Step 1: Generate all subsequences (2^n).
• Step 2: Filter for length ≥ 3 and arithmetic.
• Step 3: Count valid ones.

Step-by-Step Example

Example: nums = [2,4,6]

• Subsequences: [], [2], [4], [6], [2,4], [2,6], [4,6], [2,4,6].
• Check: [2,4,6] (diff = 2).
• Result: 1.

Code for Brute Force

Copy codeclass Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        def is_arithmetic(seq):
            if len(seq) < 3:
                return False
            diff = seq[1] - seq[0]
            for i in range(2, len(seq)):
                if seq[i] - seq[i-1] != diff:
                    return False
            return True

        # Generate all subsequences
        n = len(nums)
        count = 0
        for mask in range(1, 1 << n):
            subseq = [nums[i] for i in range(n) if mask & (1 << i)]
            if is_arithmetic(subseq):
                count += 1

        return count

• Time Complexity: O(2^n)—exponential.
• Space Complexity: O(n)—subsequence storage.

It’s a slow rhythm finder!

Comparing the Two Solutions

• DP with Hash Map (Best):
• Pros: O(n²), efficient, scalable.
• Cons: Complex logic.
• Brute Force (Alternative):
• Pros: O(2^n), simple concept.
• Cons: Impractical for n > 20.

DP wins hands down.

Edge Cases and More Examples

• Input: [1] → 0.
• Input: [1,3,5] → 1.
• Input: [1,2] → 0.

DP handles all efficiently.

Complexity Recap

• DP: Time O(n²), Space O(n²).
• Brute Force: Time O(2^n), Space O(n).

DP is the champ.

Key Takeaways

• DP: Build patterns smartly.
• Brute Force: Check everything.
• Python Tip: Hash maps boost DP—see [Python Basics](/python/basics).

Final Thoughts: Catch Those Slices

LeetCode 446: Arithmetic Slices II - Subsequence in Python is a hard-hitting DP adventure. The hash map solution is your fast pattern detector, while brute force is a slow explorer. Want more DP fun? Try LeetCode 413: Arithmetic Slices or LeetCode 300: Longest Increasing Subsequence. Ready to count some slices? Head to Solve LeetCode 446 on LeetCode and crack the code today—your coding rhythm is on point!