# 23.06.2023 [1027. Longest Arithmetic Subsequence]

Max arithmetic subsequence length in array

23.06.2023

1027. Longest Arithmetic Subsequence medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/254

Problem TLDR

Max arithmetic subsequence length in array

Intuition

This was a hard problem for me :)
Naive Dynamic Programming solution with recursion and cache will give TLE.
Let’s observe the result, adding numbers one-by-one:

// 20 1 15 3 10 5 8
// 20
// 20 1
//  1
// 20 20  1 15
//  1 15 15
//
// 20 20 20  1 1 15 3
// 1  15  3 15 3 3
//
// 20 20 20 20  1 1  1 15 15 10
//  1 15  3 10 15 3 10  3 10
//    10
//
// 20 20 20 20 20  1 1  1 1 15 15 15 10 5
//  1 15  3 10  5 15 3 10 5  3 10  5  5
//    10                        5
//     5
//
// 20 20 20 20 20 20  1 1  1 1 1 15 15 15 15 10 10 5 8
//  1 15  3 10  5  8 15 3 10 5 8  3 10  5  8  5  8 8
//    10                             5

For each pair from-to there is a sequence. When adding another number, we know what next numbers are expected.

Approach

We can put those sequences in a HashMap by next number key.

Complexity

• Time complexity:
  O(n^2)

• Space complexity:
  O(n^2)

Code

data class R(var next: Int, val d: Int, var size: Int)
fun longestArithSeqLength(nums: IntArray): Int {
    // 20 1 15 3 10 5 8
    // 20
    // 20 1
    //  1
    // 20 20  1 15
    //  1 15 15
    //
    // 20 20 20  1 1 15 3
    // 1  15  3 15 3 3
    //
    // 20 20 20 20  1 1  1 15 15 10
    //  1 15  3 10 15 3 10  3 10
    //    10
    //
    // 20 20 20 20 20  1 1  1 1 15 15 15 10 5
    //  1 15  3 10  5 15 3 10 5  3 10  5  5
    //    10                        5
    //     5
    //
    // 20 20 20 20 20 20  1 1  1 1 1 15 15 15 15 10 10 5 8
    //  1 15  3 10  5  8 15 3 10 5 8  3 10  5  8  5  8 8
    //    10                             5

    val nextToR = mutableMapOf<Int, MutableList<R>>()
        var max = 2
        nums.forEachIndexed { to, num ->
            nextToR.remove(num)?.forEach { r ->
                r.next = num + r.d
                max = maxOf(max, ++r.size)
                nextToR.getOrPut(r.next) { mutableListOf() } += r
            }
            for (from in 0..to - 1) {
                val d = num - nums[from]
                val next = num + d
                nextToR.getOrPut(next) { mutableListOf() } += R(next, d, 2)
            }
        }
        return max
    }