Given a list of integers, task is to find the maximum length of subsequence having increasing consecutive elements that increase by value = 1.

Example :
Input : 1 0 2 3 2 4 9 6 5
Output : 5 (as the subsequence will be 1 2 3 4 5)

Started with brute force. For optimized approach, I took a lot of time to come up with the hashmap based approach (~30mins had already passed by the time I came up with this solution). Presented the optimized approach, coded it and discussed the time and space complexity. Interviewer didn't ask any follow up probably as not much time was left.

One edge case I had missed in the code which the interviewer pointed out and then I added that check.

Received feedback that I need more DSA practice. Got rejected.

My solution:

def longestSubsequence(arr):
hashmap={}
maxLen = 0

for num in arr:
    if num-1 in hashmap:
        hashmap[num]  = hashmap[num-1]+1
    else:
        hashmap[num]=1
        
    if hashmap[num]>maxLen:
        maxLen = hashmap[num]
        
return maxLen