O(nlogn) Clean and easy Java DP + Binary Search solution with detailed explanation


  • 18
    C

    I use an array dp[] to store the largest elements in the increasing subsequences and the array's index is the length of the subsequence (since this, we can make sure that the array dp[] is in-order). The idea is keep checking if nums[i] is bigger than dp[len] or not: nums[i] > dp[len] means we can retrieve a longer subsequence by adding the current element nums[i] into the result, so we just increase the pointer 'len' by one and put the current element into the new index; otherwise we need to do a binary search to find out the index of the largest element st. dp[index] < nums[i] && dp[index + 1] > nums[i] and update the dp[index] with value nums[i].

    Let's see an example:
    intput: 2 4 9 3 7 8

    The array 'dp' looks like these in first two iterations:

    2 4 0 0 0 (len = 1)

    2 4 9 0 0 (len = 2)

    In the third iteration, we notice that dp[len] ('9' here) > nums[i] ('3' here), so we update the dp[index] with value '3', then we got:

    2 3 9 0 0 (len = 2) <---- Attention here, this array doesn't mean we can retrieve subsequence [2,3,9], it only means the largest element in a length 1 subsequence is '2' ([2]), the largest element in a length 2 subsequence is '3' ([2,3]) and the largest element in a length 3 subsequence is '9' ([2,4,9]) by far.

    In next iteration, we update the dp[index] with value '7' again and we got:
    2 3 7 0 0 (len = 2)

    In the final round, obviously dp[len] (7) < nums[i] (8) so we increase the 'len' by one and put '8' into dp[3] then we got:
    2 3 7 8 0 (len = 3)

    Clearly len + 1 = 4 is our result : )

    PS: Keep in mind that 'len' always indicate the length of the longest increasing subsequence in each iteration.

    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int len = 0;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] > dp[len]) {
                dp[++len] = nums[i];
            }
            else {
                int index = search(dp, len, nums[i]);
                dp[index] = nums[i];
            }
        }
        return len + 1;
    }
    
    private int search(int[] dp, int len, int val) {
        int start = 0;
        while(start <= len) {
            int mid = start + (len - start) / 2;
            if(dp[mid] == val) {
                return mid;
            }
            else if(dp[mid] < val) {
                start = mid + 1;
            }
            else {
                len = mid - 1;
            }
        }
        return start;
    }

  • 0
    L

    You have said the wrong explanation.
    You said: otherwise we need to do a binary search to find out the index of the largest element st. dp[index] < nums[i] && dp[index + 1] > nums[i] and update the dp[index] with value nums[i].
    But in your example, in the step:2 3 9 0 0 (len = 2) <---- Attention here, i=3, nums[i]=3, index = 0, dp[0]<3<dp[1], so we should update dp[0] rather than dp[1].
    It would be better if you can update this conflict in your explanation.


  • 0

    I don't think it's the largest under given length, but the smallest at that position. Consider the sequence 2 4 9 3 1 10, you will get 1 3 9 10 at last.

    In this case, 3 is the smallest number that can have increasing sequence with length 2. That's why the problem can be considered into category of DP.


Log in to reply
 

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