HardNo. 0446

Arithmetic Slices II - Subsequence — LeetCode 446 Python Solution

Topics
Array, Dynamic Programming
Reading time
2 min

The problem

Given an integer array nums, return the number of all the arithmetic subsequences of nums. A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

Example

Input
nums = [2,4,6,8,10]
Output
7
Explanation
All arithmetic subsequence slices are:

Python solution

PythonSolution
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        f = [defaultdict(int) for _ in nums]
        ans = 0
        for i, x in enumerate(nums):
            for j, y in enumerate(nums[:i]):
                d = x - y
                ans += f[j][d]
                f[i][d] += f[j][d] + 1
        return ans

Complexity

Time
O(n·m) (typical)
Space · auxiliary
O(n·m)or optimized

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 446. Arithmetic Slices II - Subsequence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0413Arithmetic SlicesMedium
0045Jump Game IIMedium
0053Maximum SubarrayMedium
0055Jump GameMedium
0063Unique Paths IIMedium
0064Minimum Path SumMedium

Frequently asked questions

How hard is LeetCode 446. Arithmetic Slices II - Subsequence?

LeetCode 446. Arithmetic Slices II - Subsequence is rated Hard on LeetCode.

What topics does LeetCode 446. Arithmetic Slices II - Subsequence cover?

LeetCode 446. Arithmetic Slices II - Subsequence is tagged Array and Dynamic Programming on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.