LeetCode Entry

1218. Longest Arithmetic Subsequence of Given Difference

14.07.2023 medium 2023 kotlin

Longest arithmetic difference subsequence

1218. Longest Arithmetic Subsequence of Given Difference medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/275

Problem TLDR

Longest arithmetic difference subsequence

Intuition

Store the next value and the length for it.

Approach

We can use a HashMap

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


fun longestSubsequence(arr: IntArray, difference: Int): Int =
with(mutableMapOf<Int, Int>()) {
    arr.asSequence().map { x ->
        (1 + (this[x] ?: 0)).also { this[x + difference] = it }
    }.max()!!
}