Java O(n) solution, but how could I improve this?


  • 1
    C

    My solution looks at each input only once, and uses a HashTable to store the boundaries of the Longest Common Subsequence.

    1. If the current num[i] is in the hash table, return the value
    2. if the previous number is in the hash table, remember it's value
    3. if the next number is in the hash table, remember it's value
    4. update the current number by summing the previous and next values and adding 1
    5. update the values at the boundary

    After submitting and having my solution accepted, I'm wondering what I could do to speed it up?

    public int longestConsecutive(int[] num) {
    
        if (num.length < 2) {
            return num.length;
        }
    
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
        int ans = 0;
    
        for (int i = 0; i < num.length; i++){
    
            if (map.containsKey(num[i])) {
                continue;
            }
    
            int before = 0;
            if (map.containsKey(num[i]-1)) {
                before = map.get(num[i]-1);
            }
    
            int after = 0;
            if (map.containsKey(num[i]+1)) {
                after = map.get(num[i]+1);
            }
    
            // get the current value
            int current = before + after + 1;
    
            // update the current value
            map.put(num[i], current);
    
            // update the edges
            if (before != 0) {
                map.put(num[i]-before, current);
            }
    
            if (after != 0) {
                map.put(num[i]+after, current);
            }
    
            ans = Math.max(ans, current);
        }
    
        return ans;
    }

  • 0
    F

    Can you explain more about why we use current = before + after + 1? I think the after will always be 0 because n+1 will always be inserted into the map after n, am I right? If so, why we still initialize right?


  • 0
    C

    after will be set to the length of the longest subsequence that contains the next digit. In the sequence 3, 2, 1 when we get to the '2' after will be set to 1 so current will get set to 2. When we get to the last digit after will be wet to 2 so current will get set to 3. Hope that helps?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.