446. Arithmetic Slices II - Subsequence

HardArrayDynamic Programming
Leetcode Link

Problem Description

The problem is about finding the total count of arithmetic subsequences in a given array nums. A subsequence is defined as a sequence that can be derived from the original array by deleting some or no elements without changing the order of the remaining elements. The question specifies arithmetic subsequences which are described by two key characteristics:

  1. They must contain at least three elements.
  2. The difference between consecutive elements must be the same throughout the subsequence (this is known as the common difference in arithmetic sequences).

For example, [1, 3, 5] is an arithmetic subsequence with a common difference of 2, and [1, 1, 1] is also an arithmetic subsequence with a common difference of 0. However, a sequence like [1, 2, 4] is not arithmetic since the differences between the consecutive elements are not equal (1 and 2, respectively).

The goal is to find the number of such subsequences in the given array nums.

Intuition

When solving this type of problem, it's important to recognize that a straightforward approach to generating all possible subsequences and checking whether each is arithmetic would be inefficient, likely leading to an exponential time complexity. Instead, we should strive for a dynamic programming approach that builds on the solution of smaller subproblems.

The intuition is to use dynamic programming to keep track of the count of arithmetic subsequence slices ending at each index with a given common difference. We create an array f of dictionaries, with each dictionary at index i holding counts of subsequences that end at nums[i] categorized by their common differences.

As we iterate through nums, we consider each pair of indices (i, j) such that i > j. The common difference d is calculated as nums[i] - nums[j]. Then, we update our dynamic programming array f and count as follows:

  1. The number of arithmetic subsequences ending at i with a common difference d is incremented by the count of subsequences ending at j with the same difference (found in f[j][d]) plus one (for the new subsequence formed by just including nums[i] and nums[j]).
  2. The overall number of arithmetic subsequences (stored in ans) is increased by f[j][d], since we can extend any subsequence ending at j with nums[i] to form a new valid subsequence.

The use of a dictionary enables us to keep track of different common differences efficiently, and by iterating over all pairs (i, j) where i > j, we ensure that we consider all valid subsequences that could be formed.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The provided Python solution uses dynamic programming with an implementation that optimizes the process of counting arithmetic subsequences.

These are the key components of the implementation:

  1. Dynamic Programming Array (f): An array of dictionaries is used to store the state of the dynamic programming algorithm. This array f has the same length as the input array nums, where each index i of f has a corresponding dictionary. In this dictionary, keys represent the common differences of arithmetic subsequences that end at nums[i], and values represent the number of such subsequences.

  2. Counting Arithmetic Subsequences: The algorithm iterates through the input array nums using two nested loops to consider each pair (i, j) where i > j as potential end points for an arithmetic subsequence. The difference d = nums[i] - nums[j] is computed for each pair.

  3. Updating State and Counting Slices (ans): For each pair (i, j), the algorithm does two things:

    • It updates the state in f[i][d] by adding f[j][d] + 1 to it. The extra +1 accounts for a new subsequence formed by including just nums[i] and nums[j].
    • It increases the overall count (ans) by f[j][d]. Each entry in f[j] represents a valid subsequence that ends at nums[j] and can be extended by nums[i] to form a new subsequence.

In summary, the solution involves iterating over pairs of elements to calculate possible common differences and uses dynamic programming to store the count of arithmetic subsequences up to the current index, avoiding the inefficiency of checking each possible subsequence individually. The final variable ans holds the count of all valid arithmetic subsequences of length three or more across the entire array nums.

Since this approach avoids redundant calculations by reusing previously computed results, it allows for an efficient calculation of the total number of arithmetic subsequences in the input array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's illustrate the solution approach using a small example array nums = [2, 4, 6, 8, 10].

  1. Initializing Dynamic Programming Array (f): We start by creating an array of dictionaries, f, where each index will store dictionaries. Initially, all dictionaries are empty since no subsequences have been computed yet.

  2. Counting Arithmetic Subsequences:

    • For i = 1 (nums[1] = 4), we look backward for j < i:

      • At j = 0 (nums[0] = 2), the common difference d = 4 - 2 = 2.
      • The count at f[1][d] is initially 0. We increment it by f[0][2] + 1 (0 + 1 since f[0][2] does not exist yet) to account for the subsequence [2, 4].
      • However, this subsequence is not yet long enough to increment our answer, as we need at least three elements for an arithmetic subsequence.

    • For i = 2 (nums[2] = 6), we again look backward for j < i:

      • For j = 1 (nums[1] = 4), d = 6 - 4 = 2. We increment f[2][2] by f[1][2] + 1 which is 1 + 1 = 2 (the [2, 4, 6] subsequence and just [4, 6]).
      • For j = 0 (nums[0] = 2), d = 6 - 2 = 4. This common difference does not align with the subsequences formed up to i = 2, so no update is made to ans.
      • Our overall count ans is increased by f[1][2] which is 1, as [2, 4, 6] is a valid arithmetic subsequence.

    • For i = 3 (nums[3] = 8), we look backward again for j < i:

      • For j = 2 (nums[2] = 6), d = 8 - 6 = 2. Increment f[3][2] by f[2][2] + 1 which becomes 2 + 1 = 3 (we can form [4, 6, 8], [2, 6, 8], and just [6, 8]).
      • For j = 1, d = 2, we again increment f[3][2] and ans by f[1][2].
      • Our count ans is updated with the sum of f values for d = 2 for j = 1 and j = 2 which gives us 3 more valid subsequences ([2, 4, 8], [4, 6, 8], [2, 6, 8]).

    • Continuing this process for i = 4 (nums[4] = 10), we find the subsequences ending with 10 and update f and ans accordingly.

  3. Final Count (ans): By the end of our iteration, ans would include the count of all valid arithmetic subsequences of at least three elements. In our case, the subsequences are [2, 4, 6], [2, 4, 6, 8], [2, 4, 8], [4, 6, 8], [2, 6, 8], [2, 4, 6, 8, 10], [2, 4, 6, 10], [2, 4, 8, 10], [2, 6, 8, 10], [4, 6, 8, 10], so ans would be 7.

By reusing previously computed results for overlapping subproblems, the efficient dynamic programming solution allows us not to recalculate every potential subsequence, leading to a more optimized approach for counting the total number of arithmetic subsequences.

Solution Implementation

1from typing import List
2from collections import defaultdict
3
4class Solution:
5    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
6        # Initialize a list of dictionaries for each number in `nums`
7        # Each dictionary will hold the count of arithmetic sequences ending with that number
8        arithmetic_count = [defaultdict(int) for _ in nums]
9
10        # Initialize the answer to 0
11        total_count = 0
12
13        # Iterate over each pair (i, x) where `i` is the index and `x` is the number
14        for i, current_num in enumerate(nums):
15            # Iterate over all the numbers before the current number
16            for j, prev_num in enumerate(nums[:i]):
17                # Calculate the difference between the current and previous number
18                difference = current_num - prev_num
19
20                # Add the count of arithmetic sequences ending at index `j` with the same difference to the answer
21                total_count += arithmetic_count[j][difference]
22
23                # Add or increment the count of arithmetic sequences ending at index `i` with the same difference
24                # It will be 1 more than the count at index `j` since `i` extends the sequence from `j` by one more element
25                arithmetic_count[i][difference] += arithmetic_count[j][difference] + 1
26
27        # Return the total count of all arithmetic sequences found in `nums`
28        return total_count
29
1class Solution {
2    public int numberOfArithmeticSlices(int[] nums) {
3        // Total number of elements in the input array.
4        int n = nums.length;
5        // Array of maps to store the count of arithmetic slices ending at each index.
6        Map<Long, Integer>[] countMaps = new Map[n];
7        // Initialize each map in the array.
8        Arrays.setAll(countMaps, element -> new HashMap<>());
9        // Variable to store the final answer.
10        int totalCount = 0;
11
12        // Iterate through each element in the array starting from the second element.
13        for (int i = 0; i < n; ++i) {
14            // For each element, check all previous elements to calculate the differences.
15            for (int j = 0; j < i; ++j) {
16                // Calculate the difference between the current and previous elements.
17                Long diff = 1L * nums[i] - nums[j];
18                // Get the current count of arithmetic slices with the same difference ending at index j.
19                int count = countMaps[j].getOrDefault(diff, 0);
20                // Accumulate the total number of found arithmetic slices.
21                totalCount += count;
22                // Update the countMap for the current element (index i).
23                // Increment the count of the current difference by the count from the previous index plus 1 for the new slice.
24                countMaps[i].merge(diff, count + 1, Integer::sum);
25            }
26        }
27
28        // Return the accumulated count of all arithmetic slices found in the array.
29        return totalCount;
30    }
31}
32
1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6    int numberOfArithmeticSlices(std::vector<int>& numbers) {
7        int count = numbers.size(); // Count of numbers in the vector.
8        std::vector<std::unordered_map<long long, int>> arithmeticCount(count);
9        // The vector 'arithmeticCount' will store maps to keep the count of
10        // how many times a particular arithmetic difference has appeared up to
11        // the current index.
12
13        int totalSlices = 0; // This will hold the total number of arithmetic slices.
14
15        for (int i = 0; i < count; ++i) {
16            for (int j = 0; j < i; ++j) {
17                // Compute the difference 'diff' of the current pair of numbers.
18                long long diff = static_cast<long long>(numbers[i]) - numbers[j];
19                // The number of sequences ending with 'j' that have a common difference 'diff'.
20                int sequencesEndingWithJ = arithmeticCount[j][diff];
21                // Increment the total number of arithmetic slices found so far by this number.
22                totalSlices += sequencesEndingWithJ;
23                // Increment the count of the number of sequences with difference 'diff'
24                // ending at 'i' by the number of such sequences ending at 'j' + 1
25                arithmeticCount[i][diff] += sequencesEndingWithJ + 1;
26                // The '+1' is for the new sequence formed by 'j' and 'i' themselves.
27            }
28        }
29        return totalSlices;
30    }
31};
32
1function numberOfArithmeticSlices(nums: number[]): number {
2    // Length of the input array
3    const length = nums.length;
4
5    // Array of maps to store the count of arithmetic slice endings at each index with a certain difference
6    const arithmeticMap: Map<number, number>[] = new Array(length).fill(0).map(() => new Map());
7
8    // Final count of arithmetic slices
9    let totalCount = 0;
10
11    // Iterate over all the pairs of elements in the array
12    for (let i = 0; i < length; ++i) {
13        for (let j = 0; j < i; ++j) {
14            // Compute the difference between the current pair of numbers
15            const difference = nums[i] - nums[j];
16
17            // Retrieve the count of slices ending at index j with the computed difference
18            const count = arithmeticMap[j].get(difference) || 0;
19
20            // Increment the total count by the number of slices found
21            totalCount += count;
22
23            // Update the map for the current index i, adding the count calculated above to the existing count
24            // and account for the new slice formed by i and j
25            arithmeticMap[i].set(difference, (arithmeticMap[i].get(difference) || 0) + count + 1);
26        }
27    }
28
29    // Return the final count of arithmetic slices
30    return totalCount;
31}
32
Not Sure What to Study? Take the 2-min Quiz

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

The given Python code defines a method numberOfArithmeticSlices, which calculates the number of arithmetic slices in a list of numbers. It does this by using dynamic programming with a list of default dictionaries to track the arithmetic progressions.

Time Complexity:

The time complexity of the method can be determined by analyzing the nested loops and the operations performed within those loops. The outer loop runs for n iterations, where n is the length of the list nums. The inner loop runs i times for each iteration of the ith element in the outer loop:

  • The outer loop: O(n), iterating through each element of nums.
  • The inner loop: Up to O(n), iterating through elements up to i, which on average would be O(n/2) for each iteration of the outer loop.
  • Within the inner loop:
    • The operation d = x - y is O(1).
    • The lookup and update operations on the default dictionaries f[j][d] and f[i][d] are average-case O(1), assuming hash table operations.

Therefore, the correct time complexity is derived from the total iterations of the inner loop across all iterations of the outer loop, which is:

  • O(1 + 2 + 3 + ... + (n - 1))
  • This equals O(n(n - 1) / 2)
  • Hence, the time complexity simplifies to O(n^2).

Space Complexity:

The space complexity can be analyzed by looking at the data structures used:

  • The list f contains n defaultdicts, one for each element in nums.
  • Each defaultdict can have up to i different keys, where i is the index of the outer loop, leading to O(n^2) in the worst case because each arithmetic progression can have a different common difference.

Thus, the space complexity is O(n^2) based on the storage used by the f list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«