Fast Java Binary Search Solution with detailed explanation


  • 36

    This solution uses Binary Search + DP

    1, traverse from 0 to len-1, the DP array keep the longest sequence.
    2, if the val is bigger than largest in the dp array, add it to the end;
    3, if it is among the sequence, return the pos that bigger than pres, update the array with this position if val is smaller than dp[pos];
    This is to keep the sequence element with the smallest number.
    

    For example:

    10, 9, 2, 5, 3, 7, 101, 18
    
    10 
    9
    2
    2,5
    2,3
    2,3,7
    2,3,7,101
    2,3,7,18
    

    The follow is the solution:

    public class Solution {
        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++) {
                int pos = binarySearch(dp,len,nums[i]);
                if (nums[i] < dp[pos]) dp[pos] = nums[i];
                if (pos > len) {
                    len = pos;
                    dp[len] = nums[i];
                }
            }
            return len+1;
        }
        private int binarySearch(int[] dp, int len, int val) {
            int left = 0;
            int right = len;
            while(left+1 < right) {
                int mid = left + (right-left)/2;
                if (dp[mid] == val) {
                    return mid;
                } else {
                    if (dp[mid] < val) {
                        left = mid;
                    } else {
                        right = mid;
                    }
                }
            }
            if (dp[right] < val) return len+1;
            else if (dp[left] >= val) return left;
            else return right;
        }
    }

  • 10

    Nice solution. however, your explanation is not clear enough.

    For example, if the nums is
    1 6 8 5 9

    then the sequence will be like

    1
    1 6
    1 6 8
    1 5 8
    1 5 8 9
    

    The result will be 4. But the LIS is not 1 5 8 9.

    The algorithm is smart to handle this anyway. But as an explanation, you can do better by analyzing why this does not matter.


  • 0
    S

    Hi Dragon, thank you for bringing up this corner case, can you please explain why this case does not matter?


  • 0

    Well, the dp array is not actually keeping the exact longest sequence. However, the len value is correct.
    Here's another example:
    [1, 6, 8, 9 ,2, 3]
    The sequence will be like:
    1;
    1, 6;
    1, 6, 8;
    1, 6, 8, 9;
    1, 2, 8, 9;
    1, 2, 3, 9;
    Obviously, 1,2 ,3, 9 is not the correct sequence, but the length value is correct.


  • 0
    C

    I am wondering why make the initial value of len 0, there are one element there. actually, make it the same as the real length of the dp array is accepted and more straightforward.

    as for the why the content of dp array is not the real LIS, that's because the dp array keep tracing multi increasing sub sequence.

    public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return 1;
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int len = 1;
    for(int i = 1; i < nums.length; ++i) {
    int pos = search(dp, len, nums[i]);
    if (pos == len) dp[len++] = nums[i];
    else if (dp[pos] > nums[i]) dp[pos] = nums[i];
    }
    return len;
    }


  • 0

    @xdtxdt You just threw a new example థ౪థ. Why the length is correct tho?


  • 0
    R

    because even it did the substitution, it didn't change the LIS' length. so even some of the number is added incorrectly, it won't change the fact that there existed such a sequence with this length.
    so whenever a new digit added, there are two cases. one is it been added to somewhere in the middle, which won't change the last digit. the last digit matters if we will add a new one or not. Second case is it been added to the last, which indicate it will also works for the true LIS.
    So the list DP maybe wrong, the length is right


  • 1

    @monkeyGoCrazy
    if this post stay at top. it saves folks lots of trouble from reading those "simplified and concise and smart" version which brings no good but hiding the thoughts.

    I used to think less code is more, but one condition applied, clarity never should be traded off for shortness. I should say now, clear code is the most. Your solution wins bro


  • 0

    @Dragon.PW
    you assume the dp keeps the subsequence but it isn't. only value we tracking here is len which is the last index of the longest subsequence


  • 1

    @三千世界 You assume I assumed something. However, I didn't. I was just pointing out a fact, which may confuse some other readers.


  • 0

    @三千世界 If I said "it does not matter", then, obviously I know the vector is not the longest increasing subsequence, which really does not matter.


  • 0
    C

    Very poor explanation!


Log in to reply
 

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