hard Arithmetic Slices II - Subsequence

Problem Statement

Given an array of integers nums, return the number of arithmetic subsequences of nums.

If any integer array consists of at least three elements and if the difference between any two consecutive elements is the same, it is called arithmetic.

• For example [3, 6, 9, 12] is arithmetic sequences.

A subsequence of an array is a sequence that can be formed by eliminating some or no elements from the array.

Examples

1. Example 1:

   • Input: nums = [1, 2, 3, 4]
   • Expected Output: 3
   • Justification: The possible arithmetic subsequences are [1, 2, 3], [2, 3, 4], and [1, 2, 3, 4]. Each has a common difference of 1. These are the only subsequences that meet the criteria.

2. Example 2:

   • Input: nums = [9, 4, 7, 2, 10]
   • Expected Output: 1
   • Justification: The possible arithmetic subsequence is [4, 7, 10]. It has a consistent difference between consecutive elements, which is 3.

3. Example 3:

   • Input: nums = [3, 6, 9, 12, 15]
   • Expected Output: 7
   • Justification: The arithmetic subsequences are [3, 6, 9], [6, 9, 12], [9, 12, 15], [3, 6, 9, 12], [6, 9, 12, 15], [3, 6, 9, 12, 15], and [3, 9, 15].

Solution

To solve this problem, we'll use dynamic programming combined with hashing. The key idea is to track the number of subsequences ending at each index with a specific common difference. This method is effective because it allows us to efficiently update and count subsequences as we iterate through the array, leveraging previous computations.

The approach works well because it breaks down the problem into smaller, manageable sub-problems. Each sub-problem involves calculating the number of arithmetic subsequences ending at a particular element, which we then aggregate for the final count. By using a hash map to store these counts based on their common differences, we can update and retrieve them in constant time, making this method highly efficient for the task.

Step-by-Step Algorithm

1. Initialization: Create a list of hash maps, one for each element in the input array. Each hash map will track the count of arithmetic subsequences ending at that element, keyed by their common difference.

2. Iterate Through the Array: For each element nums[i] in the input array, starting from the second element, perform the following steps:

   • Initialize an empty hash map for nums[i].
   • Iterate through all previous elements nums[j] where j < i.
     • Calculate the difference d = nums[i] - nums[j].
     • Retrieve the count of subsequences ending at j with difference d, denoted as countAtJ. If no such count exists, consider countAtJ to be 0.
     • Retrieve the count of subsequences ending at i with difference d, denoted as countAtI. If no such count exists, consider countAtI to be 0.
     • Update the count at i for difference d by adding countAtJ + 1 to countAtI. The "+1" accounts for the new subsequence formed by nums[j] and nums[i].
     • If j had one or more subsequences ending with it with the same difference d, add countAtJ to the total count of valid arithmetic subsequences.

3. Aggregate the Total Count: The total count of arithmetic subsequences with at least three elements is accumulated during the iteration. This is the final answer.

4. Return the Total Count: Return the accumulated total count of valid arithmetic subsequences.

Algorithm Walkthrough

Let's consider the input: nums = [3, 6, 9, 12, 15].

1. Initialization:

   • Begin without any previous comparisons, as the algorithm starts with the second element for comparisons.

2. First Element: 3

   • No comparisons are made. HashMaps are still empty.

3. Second Element: 6

   • Comparing with first element (3):
     • Difference d = 6 - 3 = 3.
     • Update HashMap at index 1: {3: 1}.
   • HashMap Visualization:
     • Index 0: {}
     • Index 1: {3: 1}

4. Third Element: 9

   • Comparing with first element (3):
     • Difference d = 9 - 3 = 6.
     • Update hashmap with d = 6.
   • Comparing with second element (6):
     • Difference d = 9 - 6 = 3.
     • There's 1 subsequence ending at 6 with this difference.
     • Update HashMap at index 2: {3: 2} (1 existing + 1 new).
     • Total count increases by 1 (for [3, 6, 9]).
     • TotalCount = 1.
   • HashMap Visualization:
     • Index 0: {}
     • Index 1: {3: 1}
     • Index 2: {3: 2, 6: 1}

5. Fourth Element: 12

   • Comparing with first element (3):
     • Difference d = 12 - 3 = 9.
     • Update hashmap with d = 9.
   • Comparing with second element (6):
     • Difference d = 12 - 6 = 6.
     • Update hashmap with d = 6.
   • Comparing with third element (9):
     • Difference d = 12 - 9 = 3.
     • There are 2 subsequences ending at 9 with this difference.
     • Update HashMap at index 3: {3: 3} (2 existing + 1 new).
     • Total count increases by 2 (for [6, 9, 12] and [3, 6, 9, 12]).
     • TotalCount = 3.
   • HashMap Visualization:
     • Index 0: {}
     • Index 1: {3: 1}
     • Index 2: {3: 2, 6: 1}
     • Index 3: {3: 3, 6: 1, 9: 1}

6. Fifth Element: 15

   • Comparing with first element (3):
     • Difference d = 15 - 3 = 12.
     • Update hashmap with d = 12.
   • Comparing with second element (6):
     • Difference d = 15 - 6 = 9.
     • Update hashmap with d = 9.
   • Comparing with third element (9):
     • Difference d = 15 - 9 = 6.
     • There are 1 subsequences ending at 9 with this difference.
     • Update HashMap at index 4: {6: 2} (1 existing + 1 new).
     • Total count increases by 1 (for [3, 9, 15]).
     • TotalCount = 4.
   • Comparing with fourth element (12):
     • Difference d = 15 - 12 = 3.
     • There are 3 subsequences ending at 12 with this difference.
     • Update HashMap at index 4: {3: 4} (3 existing + 1 new).
     • Total count increases by 3 (for [9, 12, 15], [6, 9, 12, 15], and [3, 6, 9, 12, 15]).
     • TotalCount = 7.
   • HashMap Visualization:
     • Index 0: {}
     • Index 1: {3: 1}
     • Index 2: {3: 2, 6: 1}
     • Index 3: {3: 3, 6: 1, 9: 1}
     • Index 4: {3: 4, 9: 1, 12: 1, 6: 2}

7. Final Consideration:

   • The total count thus far is 7 for explicitly identified subsequences.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {

  // Method to calculate the number of arithmetic slices in an array
  public int numberOfArithmeticSlices(int[] nums) {
    int totalCount = 0;
    Map<Long, Integer>[] countMaps = new HashMap[nums.length];

    for (int i = 0; i < nums.length; i++) {
      countMaps[i] = new HashMap<>();
      for (int j = 0; j < i; j++) {
        long diff = (long) nums[i] - nums[j];
        int countAtJ = countMaps[j].getOrDefault(diff, 0);
        int countAtI = countMaps[i].getOrDefault(diff, 0);

        // Update the count for the current difference at position i
        countMaps[i].put(diff, countAtI + countAtJ + 1);
        // Only count subsequences that are at least 3 elements long
        totalCount += countAtJ;
      }
    }

    return totalCount;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test the algorithm with the provided examples
    System.out.println(
      solution.numberOfArithmeticSlices(new int[] { 1, 2, 3, 4 })
    ); // Example 1
    System.out.println(
      solution.numberOfArithmeticSlices(new int[] { 9, 4, 7, 2, 10 })
    ); // Example 2
    System.out.println(
      solution.numberOfArithmeticSlices(new int[] { 3, 6, 9, 12, 15 })
    ); // Example 3
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where (n) is the length of the input array. This is because there are two nested loops:

• The outer loop runs (n) times, once for each element in the array.
• The inner loop runs for each pair of elements in the array, leading to iterations in total, which simplifies to .

Space Complexity

The space complexity is due to the usage of a list of hash maps, where each hash map can potentially store up to (n-1) entries (representing different arithmetic differences found so far). In the worst case, where every pair of elements in the array has a unique difference, this structure could store ) entries.