446. Arithmetic Slices II - Subsequence
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:
- They must contain at least three elements.
- 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:
- The number of arithmetic subsequences ending at
i
with a common differenced
is incremented by the count of subsequences ending atj
with the same difference (found inf[j][d]
) plus one (for the new subsequence formed by just includingnums[i]
andnums[j]
). - The overall number of arithmetic subsequences (stored in
ans
) is increased byf[j][d]
, since we can extend any subsequence ending atj
withnums[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.
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:
-
Dynamic Programming Array (
f
): An array of dictionaries is used to store the state of the dynamic programming algorithm. This arrayf
has the same length as the input arraynums
, where each indexi
off
has a corresponding dictionary. In this dictionary, keys represent the common differences of arithmetic subsequences that end atnums[i]
, and values represent the number of such subsequences. -
Counting Arithmetic Subsequences: The algorithm iterates through the input array
nums
using two nested loops to consider each pair(i, j)
wherei > j
as potential end points for an arithmetic subsequence. The differenced = nums[i] - nums[j]
is computed for each pair. -
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 addingf[j][d] + 1
to it. The extra+1
accounts for a new subsequence formed by including justnums[i]
andnums[j]
. - It increases the overall count (
ans
) byf[j][d]
. Each entry inf[j]
represents a valid subsequence that ends atnums[j]
and can be extended bynums[i]
to form a new subsequence.
- It updates the state in
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example array nums = [2, 4, 6, 8, 10]
.
-
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. -
Counting Arithmetic Subsequences:
-
For
i = 1 (nums[1] = 4)
, we look backward forj < i
:- At
j = 0 (nums[0] = 2)
, the common differenced = 4 - 2 = 2
. - The count at
f[1][d]
is initially 0. We increment it byf[0][2] + 1
(0 + 1 sincef[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.
- At
-
For
i = 2 (nums[2] = 6)
, we again look backward forj < i
:- For
j = 1 (nums[1] = 4)
,d = 6 - 4 = 2
. We incrementf[2][2]
byf[1][2] + 1
which is1 + 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 toi = 2
, so no update is made toans
. - Our overall count
ans
is increased byf[1][2]
which is1
, as[2, 4, 6]
is a valid arithmetic subsequence.
- For
-
For
i = 3 (nums[3] = 8)
, we look backward again forj < i
:- For
j = 2 (nums[2] = 6)
,d = 8 - 6 = 2
. Incrementf[3][2]
byf[2][2] + 1
which becomes2 + 1 = 3
(we can form[4, 6, 8]
,[2, 6, 8]
, and just[6, 8]
). - For
j = 1
,d = 2
, we again incrementf[3][2]
andans
byf[1][2]
. - Our count
ans
is updated with the sum off
values ford = 2
forj = 1
andj = 2
which gives us 3 more valid subsequences ([2, 4, 8]
,[4, 6, 8]
,[2, 6, 8]
).
- For
-
Continuing this process for
i = 4 (nums[4] = 10)
, we find the subsequences ending with10
and updatef
andans
accordingly.
-
-
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]
, soans
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
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 i
th element in the outer loop:
- The outer loop:
O(n)
, iterating through each element ofnums
. - The inner loop: Up to
O(n)
, iterating through elements up toi
, which on average would beO(n/2)
for each iteration of the outer loop. - Within the inner loop:
- The operation
d = x - y
isO(1)
. - The lookup and update operations on the default dictionaries
f[j][d]
andf[i][d]
are average-caseO(1)
, assuming hash table operations.
- The operation
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
containsn
defaultdicts, one for each element innums
. - Each defaultdict can have up to
i
different keys, wherei
is the index of the outer loop, leading toO(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.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!