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

  • -2

    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) {
                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 ++;
                        curSeq = 1;
                    dp[i] = Math.max(curSeq, dp[i-1]);
                return dp[dp.length-1];

  • 1

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

  • 0

    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.