7.01.2024
446. Arithmetic Slices II - Subsequence hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/464
Problem TLDR
Count of arithmetic subsequences.
Intuition
We can take every pair and search for the third element.
The result only depends on the diff
and suffix array position, so can be cached.
Approach
be careful how to count each new element: first add the
1
then add the suffix count. Wrong approach: just count the1
at the end of the sequence.
Complexity
Time complexity:
O(n^2), it looks like n^4, but thedfs
n^2 part will only go deep onceSpace complexity:
O(n^2)
Code
fun numberOfArithmeticSlices(nums: IntArray): Int {
val dp = mutableMapOf<Pair<Int, Int>, Int>()
fun dfs(i: Int, k: Int): Int = dp.getOrPut(i to k) {
var count = 0
for (j in i + 1..<nums.size)
if (nums[i].toLong() - nums[k] == nums[j].toLong() - nums[i])
count += 1 + dfs(j, i)
count
}
var count = 0
for (i in nums.indices)
for (j in i + 1..<nums.size)
count += dfs(j, i)
return count
}