LC-1027 Medium LeetCode

1027. Longest Arithmetic Subsequence

Array Hash Table Binary Search Dynamic Programming

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 49% Topics: Array, Hash Table, Binary Search, Dynamic Programming

View full problem on LeetCode

Also on leetcode.ca (community mirror)

Reading material

Arrays & Hashing 12 min Binary Search 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · java)

import java.util.*;

class Solution {
    int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        int result = 0;
        List<Map<Integer, Integer>> dp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            dp.add(new HashMap<>());
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int d = nums[i] - nums[j];
                int len = dp.get(j).getOrDefault(d, 1) + 1;
                dp.get(i).put(d, len);
                result = Math.max(result, len);
            }
        }
        return result;
    }
}

Solution from kamyu104/LeetCode-Solutions · MIT