LeetCode 413: Arithmetic Slices Solution in Python – A Step-by-Step Guide

What Is LeetCode 413: Arithmetic Slices?

In LeetCode 413: Arithmetic Slices, you’re given an integer array nums (e.g., [1, 2, 3, 4]), and you need to count how many contiguous subarrays are arithmetic—meaning the difference between consecutive elements is constant (e.g., 1, 2, 3 has a difference of 1). A subarray must have at least 3 elements to qualify as a slice. For [1, 2, 3, 4], there are 3 slices: [1, 2, 3], [2, 3, 4], and [1, 2, 3, 4]. Your task is to return the total number of such slices.

Problem Statement

• Input: An integer array nums.
• Output: An integer—the number of arithmetic slices (subarrays of length ≥ 3).
• Rules:
• Arithmetic: Same difference between consecutive elements.
• Subarray must be contiguous and have at least 3 elements.

Constraints

• 1 <= nums.length <= 5000.
• -1000 <= nums[i] <= 1000.

Examples

• Input: nums = [1,2,3,4]
• Output: 3 ([1,2,3], [2,3,4], [1,2,3,4]).
• Input: nums = [1,3,5,7]
• Output: 3 ([1,3,5], [3,5,7], [1,3,5,7]).
• Input: nums = [1,2,4]
• Output: 0 (no arithmetic slices).

Understanding the Problem: Counting Steady Steps

To solve LeetCode 413: Arithmetic Slices in Python, we need to count all contiguous subarrays of length 3 or more where the difference between consecutive elements stays the same. A brute-force idea might be to check every possible subarray—but with up to 5000 elements, that’s too slow! Instead, we’ll use:

• Best Solution (Dynamic Programming with Constant Space): O(n) time, O(1) space—counts slices cleverly.
• Alternative Solution (Sliding Window): O(n) time, O(1) space—scans for arithmetic runs.

Let’s dive into the DP solution with a clear, step-by-step explanation.

Best Solution: Dynamic Programming with Constant Space

Why This Is the Best Solution

The dynamic programming with constant space method is the top pick because it’s fast—O(n) time, O(1) space—and brilliantly simple once you see it. It uses a single variable to track how many new slices end at each position, building on the previous count without needing a big array. It’s like counting the steps in a dance, adding up new moves as the rhythm holds!

How It Works

Think of the array as a line of dancers stepping in sync:

• Step 1: Track Differences:
• For each position, check if the current difference matches the previous one (e.g., 2-1 = 3-2).
• Step 2: Count Slices Ending Here:
• If a streak continues (e.g., [1, 2, 3]), count new slices ending at the current number.
• For length k, new slices = k-2 (e.g., length 3 → 1 slice, length 4 → 2 slices).
• Step 3: Accumulate Total:
• Add new slices to a running total.
• Step 4: Why This Works:
• Each position builds on the last, counting only new slices.
• Constant space by using one variable for the streak.
• It’s like spotting each new chunk of a steady beat!

Step-by-Step Example

Example: nums = [1,2,3,4]

• Start: Total = 0, dp = 0 (slices ending at previous position).
• i=2: [1,2,3], diff 1-2 = 2-3 = -1, length 3, dp = 1 (new slice [1,2,3]), Total = 1.
• i=3: [1,2,3,4], diff 2-3 = 3-4 = -1, length 4, dp = 2 ([2,3,4], [1,2,3,4]), Total = 1 + 2 = 3.
• Result: 3.

Example: nums = [1,2,3,8]

• i=2: [1,2,3], diff 1, dp = 1, Total = 1.
• i=3: [2,3,8], diff 1 ≠ 5, dp = 0, Total = 1.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        # Step 1: Handle edge case
        if len(nums) < 3:
            return 0

        # Step 2: Initialize variables
        total = 0  # Total number of slices
        dp = 0     # Slices ending at previous position

        # Step 3: Loop through array
        for i in range(2, len(nums)):
            # Check if arithmetic with previous two
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                dp = dp + 1    # New slices ending here
                total += dp    # Add to total
            else:
                dp = 0         # Reset streak

        return total

• Line 4-5: If length < 3, no slices possible, return 0.
• Line 8-9: Set up:
• total: Running sum of all slices.
• dp: Number of slices ending at the last position.
• Line 12-17: Loop from index 2:
• Line 13: Check if diff matches (e.g., 3-2 = 2-1).
• Line 14-15: If yes, increment dp (new slice), add to total (e.g., dp=1, total=1).
• Line 16-17: If no, reset dp (streak breaks).
• Line 19: Return total count.
• Time Complexity: O(n)—one pass through array.
• Space Complexity: O(1)—just two variables.

This is like counting dance steps with a single tally!

Alternative Solution: Sliding Window

Why an Alternative Approach?

The sliding window method scans the array for continuous arithmetic segments, counting slices within each run. It’s O(n) time and O(1) space too—more explicit but less elegant than DP. It’s like sliding a window over the numbers, spotting steady rhythms as you go!

How It Works

Picture it as sliding a frame:

• Step 1: Find arithmetic runs (e.g., [1,2,3,4]).
• Step 2: Count slices in each run (length k → (k-2)*(k-1)/2).
• Step 3: Sum all slices across runs.

Step-by-Step Example

Example: nums = [1,2,3,4]

• Window: [1,2,3,4], length 4.
• Slices: (4-2)*(3)/2 = 3 ([1,2,3], [2,3,4], [1,2,3,4]).
• Result: 3.

Example: nums = [1,2,3,8]

• Window: [1,2,3], length 3, slices = 1.
• Next: [8], length 1, slices = 0.
• Result: 1.

Code for Sliding Window Approach

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

        total = 0
        start = 0

        while start < len(nums) - 2:
            # Find end of arithmetic segment
            diff = nums[start + 1] - nums[start]
            end = start + 1
            while end + 1 < len(nums) and nums[end + 1] - nums[end] == diff:
                end += 1
            length = end - start + 1
            if length >= 3:
                # Number of slices = (length-2)*(length-1)/2
                total += (length - 2) * (length - 1) // 2
            start = end

        return total

• Time Complexity: O(n)—one pass with window.
• Space Complexity: O(1)—few variables.

It’s a rhythmic window slider!

Comparing the Two Solutions

• DP with Constant Space (Best):
• Pros: O(n), O(1), elegant and fast.
• Cons: Less explicit.
• Sliding Window (Alternative):
• Pros: O(n), O(1), clear segments.
• Cons: More steps.

DP wins for simplicity.

Additional Examples and Edge Cases

• [1,2]: 0 (too short).
• [1,3,5,7,9]: 6.
• [1,2,4]: 0.

DP handles all.

Complexity Breakdown

• DP: Time O(n), Space O(1).
• Sliding Window: Time O(n), Space O(1).

DP’s sleek.

Key Takeaways

• DP: Count on the fly!
• Sliding Window: Scan the rhythm!
• Arithmetic: Steps matter.
• Python Tip: Loops are key—see [Python Basics](/python/basics).

Final Thoughts: Slice Those Steps

LeetCode 413: Arithmetic Slices in Python is a number-stepping adventure. DP with constant space counts it smoothly, while sliding window scans it clearly. Want more array fun? Try LeetCode 53: Maximum Subarray or LeetCode 446: Arithmetic Slices II - Subsequence. Ready to slice? Head to Solve LeetCode 413 on LeetCode and count those steps today!