Java Simple DP O(nlogn) beats 95% java solutions


  • -2
    H

    Use an Array to store max Sequence in each step.
    If the current value = pior value, keep curSeq the same.
    if the current value = pior +1 (it means the sequence is continue), curSeq++
    Otherwise, restart the seq.
    Everytime count dp[i], get the max of curSeq and dp[i-1]

    Since i used Arrays.sort, the time complexity would be O(nlogn) not O(n).

    Feel free to ask questions and suggestions are welcome.

    public class Solution {
            public int longestConsecutive(int[] nums) {
                Arrays.sort(nums);
                int[] dp = new int[nums.length];
                
                dp[0] = 1;
                int curSeq = 1;
                
                for(int i=1; i<nums.length; i++){
                    if(nums[i-1] == nums[i]){
                        
                    }else if(nums[i-1]+1 == nums[i]){
                        curSeq ++;
                    }else{
                        curSeq = 1;
                    }
                    
                    dp[i] = Math.max(curSeq, dp[i-1]);
                    
                }
                
                return dp[dp.length-1];
                
            }
        }

  • 1
    R

    Arrays.sort(nums) is O(nlogn) so your solution is not O(N)


  • 0
    H

    Gotcha, thanks for pointing it out. But i think this is still readable and easy to understand :)


Log in to reply
 

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