Arithmetic Slices Ii Subsequence

                                            
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        vector<unordered_map<long long, int>> dp(n);
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                long long diff = (long long)nums[i] - (long long)nums[j];
                dp[i][diff] += 1;
                if (dp[j].count(diff)) {
                    dp[i][diff] += dp[j][diff];
                    ans += dp[j][diff];
                }
            }
        }
        
        return ans;
    }
};

                                            
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int count = 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 d = (int) diff;
                int sum = dp[j].getOrDefault(d, 0);
                int original = dp[i].getOrDefault(d, 0);
                
                dp[i].put(d, original + sum + 1);
                count += sum;
            }
        }
        
        return count;
    }
}

                                            
from collections import defaultdict

class Solution(object):
    def numberOfArithmeticSlices(self, nums):
        """
        :type nums: List[int]
        """
        dp = [defaultdict(int) for _ in nums]
        res = 0
        
        for i in range(len(nums)):
            for j in range(i):
                diff = nums[i] - nums[j]
                count = dp[j][diff]
                dp[i][diff] += count + 1
                res += count
                
        return res

                                            
public class Solution {
    public int NumberOfArithmeticSlices(int[] nums) {
        int n = nums.Length;
        int count = 0;
        var dp = new Dictionary<int, int>[n];

        for (int i = 0; i < n; i++)
        {
            dp[i] = new Dictionary<int, int>();
            for (int j = 0; j < i; j++)
            {
                long diff = (long)nums[i] - (long)nums[j];
                if (diff <= int.MinValue || diff >= int.MaxValue)
                    continue;

                int d = (int)diff;
                int sum = dp[j].ContainsKey(d) ? dp[j][d] : 0;
                int original = dp[i].ContainsKey(d) ? dp[i][d] : 0;
                dp[i][d] = original + sum + 1;
                count += sum;
            }
        }

        return count;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
    const n = nums.length;
    let count = 0;

    const dp = Array(n).fill(0).map(() => ({}));

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            const diff = nums[i] - nums[j];
            if (dp[j][diff]) {
                dp[i][diff] = (dp[i][diff] || 0) + dp[j][diff];
                count += dp[j][diff];
            }
            dp[i][diff] = (dp[i][diff] || 0) + 1;
        }
    }

    return count;
};

                                            
function numberOfArithmeticSlices(nums: number[]): number {
    const n = nums.length;
    let count = 0;
    const dp: Map<number, number>[] = new Array(n);
    
    for (let i = 0; i < n; i++) {
        dp[i] = new Map();
        
        for (let j = 0; j < i; j++) {
            const diff = nums[i] - nums[j];
            const sum = dp[j].get(diff) || 0;
            const original = dp[i].get(diff) || 0;
            
            dp[i].set(diff, original + sum + 1);
            count += sum;
        }
    }
    
    return count;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function numberOfArithmeticSlices($nums) {
        $n = count($nums);
        $dp = array_fill(0, $n, []);
        $count = 0;
        
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $i > $j; $j++) {
                $diff = $nums[$i] - $nums[$j];
                $sum = $dp[$j][$diff] ?? 0;
                $old = $dp[$i][$diff] ?? 0;
                
                $dp[$i][$diff] = $old + $sum + 1;
                $count += $sum;
            }
        }
        
        return $count;
    }
}

                                            
class Solution {
    func numberOfArithmeticSlices(_ nums: [Int]) -> Int {
        var count = 0
        var dp = [Int:[Int:Int]]()
        
        for i in 0..<nums.count {
            dp[i] = [:]
            for j in 0..<i {
                let diff = nums[i] - nums[j]
                
                if let val = dp[j]?[diff] {
                    dp[i, default: [:]][diff, default: 0] += val + 1
                    count += val
                } else {
                    dp[i, default: [:]][diff, default: 0] += 1
                }
            }
        }
        
        return count
    }
}

                                            
class Solution {
    fun numberOfArithmeticSlices(nums: IntArray): Int {
        if (nums.size < 3) return 0
        
        var total = 0
        val dp = Array<MutableMap<Long, Int>>(nums.size) { mutableMapOf() }
        
        for (i in 0 until nums.size) {
            for (j in 0 until i) {
                val diff = nums[i].toLong() - nums[j].toLong()
                val sum = dp[j].getOrDefault(diff, 0)
                val original = dp[i].getOrDefault(diff, 0)
                dp[i][diff] = original + sum + 1
                total += sum
            }
        }
        
        return total
    }
}

                                            
class Solution {
  int numberOfArithmeticSlices(List<int> nums) {
      int n = nums.length;
      int total = 0;

      List<Map<int, int>> dp = List.generate(n, (_) => {});

      for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
          int diff = nums[i] - nums[j];
          int prevCount = dp[j][diff] ?? 0;
          int currentCount = dp[i][diff] ?? 0;
          dp[i][diff] = prevCount + currentCount + 1;
          total += prevCount;
        }
      }

      return total;
  }
}

                                            
func numberOfArithmeticSlices(nums []int) int {
    n := len(nums)
    if n < 3 {
        return 0
    }

    dp := make([]map[int]int, n)
    res := 0

    for i := 0; i < n; i++ {
        dp[i] = make(map[int]int)
        for j := 0; j < i; j++ {
            diff := nums[i] - nums[j]
            count := dp[j][diff]
            dp[i][diff] += count + 1
            if count > 0 {
                res += count
            }
        }
    }

    return res
}

                                            
object Solution {
    def numberOfArithmeticSlices(nums: Array[Int]): Int = {
        val n = nums.length
        var count = 0
        val dp = Array.fill(n)(Map.empty[Long, Int])

        for {
            i <- 0 until n
            j <- 0 until i
        } {
            val diff = nums(i).toLong - nums(j)
            val prev = dp(j).getOrElse(diff, 0)
            val curr = dp(i).getOrElse(diff, 0) + prev + 1
            dp(i) = dp(i) + (diff -> curr)
            count += prev
        }

        count
    }
}

                                            
impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        
        let n = nums.len();
        let mut dp = vec![HashMap::new(); n];
        let mut count = 0;

        for i in 0..n {
            for j in 0..i {
                let diff = nums[i] as i64 - nums[j] as i64;
                let sum = *dp[j].get(&diff).unwrap_or(&0);
                let original = *dp[i].get(&diff).unwrap_or(&0);
                dp[i].insert(diff, original + sum + 1);
                count += sum;
            }
        }
        
        count as i32
    }
}

To solve this coding challenge, we need to identify the total number of arithmetic subsequences in a given array of integers. An arithmetic subsequence is defined as having at least three elements with a constant difference between consecutive elements. This problem involves determining such subsequences efficiently using dynamic programming. Let us break down the approach methodically:

# Explanation

Understanding the Arithmetic Subsequence :

A subsequence is arithmetic if it has at least three elements with a constant difference between any two consecutive elements.
The problem can be reduced to finding out how many valid subsequences exist for each difference.

Dynamic Programming Approach :

Use a list of dictionaries where each dictionary stores counts of subsequences with specific differences ending at the corresponding index.
dp[i]

will be a dictionary. For any specific difference
d

,
dp[i][d]

holds the count of arithmetic subsequences ending at index
i

with difference
d

.
Initialize a result variable to keep track of the total number of valid subsequences.

Iterating through the Array :

For each element
nums[i]

, compare it with every previous element
nums[j]

to calculate the difference
d = nums[i] - nums[j]

.
If there already exist arithmetic subsequences ending at
j

with difference
d

(tracked in
dp[j][d]

), then these can be extended by including
nums[i]

.

Updating Dynamic Programming State :

Update
dp[i][d]

by adding
dp[j][d] + 1

. Here
1

accounts for the new pair
(nums[j], nums[i])

, and
dp[j][d]

accounts for extending previous sequences.
Accumulate the count from
dp[j][d]

to the result because each sequence stored in
dp[j][d]

can be extended by
nums[i]

.

Returning the Result :

Return the total count accumulated which represents the number of valid arithmetic subsequences.

Detailed Steps in Pseudocode

The pseudocode simplifies the explanation above into actionable steps without using specific programming syntax.

Pseudocode with Comments

                                            
# Initialize a list 'dp' where each element is a dictionary to count arithmetic subsequences with different differences.
dp = list of dictionary of integer for each element in nums

# Initialize the result to store the total count of valid subsequences
total_arithmetic_subsequences = 0

# Loop through each element nums[i] in the array
for i from 0 to length of nums - 1:
# Compare with every previous element nums[j]
for j from 0 to i - 1:
# Calculate the difference d
difference = nums[i] - nums[j]

# Check how many subsequences end at j with this difference
count_with_difference = dp[j].get(difference, 0)

# Update dp[i] for the current difference
dp[i][difference] += count_with_difference + 1

# Add the number of sequences that can be extended by nums[i]
total_arithmetic_subsequences += count_with_difference

# Return the total number of arithmetic subsequences
return total_arithmetic_subsequences

# Step-by-Step Explanation

Initialization :

Create a list
dp

where
dp[i]

is a dictionary to store counts of sequences with specific differences ending at index
i

.
Initialize
total_arithmetic_subsequences

to zero.

Nested Loop :

Iterate through each index
i

of the array and then each index
j

before
i

.
For each pair
(i, j)

, compute the difference
difference = nums[i] - nums[j]

.

Count Retrieval and Update :

Retrieve the count of sequences ending at
j

with this difference
dp[j].get(difference, 0)

.
Update
dp[i][difference]

by adding
count_with_difference + 1

.

Result Accumulation :

Add
count_with_difference

to
total_arithmetic_subsequences

to accumulate valid sequences count.

Final Return Value :

Return the value of
total_arithmetic_subsequences

which represents the total count of arithmetic subsequences in the array.

This methodology and pseudocode together offer a coherent approach to solving the problem of identifying all arithmetic subsequences in a given array efficiently.