LeetCode 446: Arithmetic Slices II - Subsequence Solution

Master LeetCode problem 446 (Arithmetic Slices II - Subsequence), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

446. Arithmetic Slices II - Subsequence

Hard

Array Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming along with a hashmap to keep track of the number of arithmetic subsequences ending at each index. We iterate through the array and for each pair of elements, we calculate the difference and update the hashmap accordingly. We can then use this information to calculate the total number of arithmetic subsequences.

Algorithm:

Initialize a hashmap dp to store the number of arithmetic subsequences ending at each index.
Initialize a variable total to keep track of the total number of arithmetic subsequences.
Iterate through the array.
For each element at index i, iterate through all elements before i to calculate the difference diff with the element at index j.
If there exists a subsequence ending at j with difference diff, increment dp[i] by the count of such subsequences.
Add dp[j] to dp[i] (since we can append the current element to any valid subsequence ending at j to form a new subsequence ending at i).
Update total by adding dp[i].
Return total.

Time Complexity: O(n^2) Space Complexity: O(n)

Solution Code

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int total = 0;
        
        Map<Integer, Integer>[] dp = new Map[n];
        
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                long diff = (long)nums[i] - nums[j];
                if (diff <= Integer.MIN_VALUE || diff > Integer.MAX_VALUE) continue;
                
                int diffInt = (int)diff;
                int sum = dp[j].getOrDefault(diffInt, 0);
                int original = dp[i].getOrDefault(diffInt, 0);
                
                dp[i].put(diffInt, original + sum + 1);
                total += sum;
            }
        }
        
        return total;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 446 (Arithmetic Slices II - Subsequence)?

This page provides optimized solutions for LeetCode problem 446 (Arithmetic Slices II - Subsequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 446 (Arithmetic Slices II - Subsequence)?

The time complexity for LeetCode 446 (Arithmetic Slices II - Subsequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 446 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 446 in Java, C++, or Python.

Back to LeetCode Solutions