Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
699 views
in Online Assessments by Expert (46,090 points) | 699 views

2 Answers

0 like 0 dislike
Best answer

images of ques

image

by Expert (46,090 points)
0 like 0 dislike

 O(biggestDiff * n + nlogn)

public int longestArithSeqLength(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int biggestDiff = nums[n-1] - nums[0];
    Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
    int ans = 0;
    for(int num : nums) {
        for(int i=0; i<=biggestDiff; i++) {
            if(map.containsKey(num-i)) {
                int seqCnt = map.get(num-i).get(i);
                ans = Math.max(ans, seqCnt+1);
                map.computeIfAbsent(num, x->new HashMap<>()).put(i, seqCnt+1);
            } else {
                map.computeIfAbsent(num, x->new HashMap<>()).put(i, 1);
            }
        }
    }
    return ans;
}

 

similar to this 

https://leetcode.com/problems/longest-arithmetic-subsequence/description/

by Expert (46,090 points)