Java/Python Binary search O(nlogn) time with explanation


  • 201

    tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i].
    For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

    len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
    len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
    len = 3   :      [4, 5, 6]            => tails[2] = 6
    

    We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

    Each time we only do one of the two:

    (1) if x is larger than all tails, append it, increase the size by 1
    (2) if tails[i-1] < x <= tails[i], update tails[i]
    

    Doing so will maintain the tails invariant. The the final answer is just the size.

    Java

    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int i = 0, j = size;
            while (i != j) {
                int m = (i + j) / 2;
                if (tails[m] < x)
                    i = m + 1;
                else
                    j = m;
            }
            tails[i] = x;
            if (i == size) ++size;
        }
        return size;
    }
    // Runtime: 2 ms
    

    Python

    def lengthOfLIS(self, nums):
        tails = [0] * len(nums)
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                m = (i + j) / 2
                if tails[m] < x:
                    i = m + 1
                else:
                    j = m
            tails[i] = x
            size = max(i + 1, size)
        return size
    
    # Runtime: 48 ms

  • 1
    E

    This is a very good explanation. Thank you very much!


  • 0
    X

    Clear and smart!!!


  • 1
    Y

    if input array has negative value, this one doesn't work, right?


  • 0
    I

    @dietpepsi For the explanation, I think tails[0] should be 4, isn't it?


  • 18
    T

    // how to read discussions on LeetCode:

    if see "Diet Pepsi"
        skip all other posts;
    else
        search for a second best one;
    

  • 0
    J

    @icezhou0784 It should be 3. The for loop work on every element. When its the turn for 3, binary search will indicate that 3 is smaller than every entry in tail. And at last, i = 0, which lead to tail[0] = 3.


  • 20
    L

    Just explain more about the tail processing example, based on https://segmentfault.com/a/1190000003819886

    [1,3,5,2,8,4,6]
    

    For this list, we can have LIS with different length.
    For length = 1, [1], [3], [5], [2], [8], [4], [6], we pick the one with smallest tail element as the representation of length=1, which is [1]
    For length = 2, [1,2] [1,3] [3,5] [2,8], ...., we pick [1,2] as the representation of length=2.
    Similarly, we can derive the sequence for length=3 and length=4
    The result sequence would be:
    len=1: [1]
    len=2: [1,2]
    len=3: [1,3,4]
    len=4: [1,3,5,6]

    According to the logic in the post,we can conclude that:
    (1) If there comes another element, 9
    We iterate all the sequences, found 9 is even greater than the tail of len=4 sequence, we then copy len=4 sequence to be a new sequece, and append 9 to the new sequence, which is len=5: [1,3,5,6,9]
    The result is:
    len=1: [1]
    len=2: [1,2]
    len=3: [1,3,4]
    len=4: [1,3,5,6]
    len=5: [1,3,5,6,9]

    (2) If there comes another 3,
    We found len=3 [1,3,4], whose tailer is just greater than 3, we update the len=3 sequence tobe [1,3,3]. The result is:
    len=1: [1]
    len=2: [1,2]
    len=3: [1,3,3]
    len=4: [1,3,5,6]

    (3) If there comes another 0,
    0 is smaller than the tail in len=1 sequence, so we update the len=1 sequence. The result is:
    len=1: [0]
    len=2: [1,2]
    len=3: [1,3,3]
    len=4: [1,3,5,6]


  • 0
    C

    You did a great job to explain the algorithm!


  • 1
    V

    @dietpepsi If I try with the input [1,5,3,4,2], I'm getting the length of the longest subsequence as 3, when it is supposed to be 2. why?


  • 0
    D

    @vignesh6v it's 1,3,4 :)


  • 0
    M

    Is it possible to get the subsequence of LIS using this method in O(NlgN) time?


  • 0
    Q

    @icezhou0784 I kind of confused about this also.


  • 5

  • 0
    J

    @yang2007chun Thx for the sharing. And this is the easy java version.
    I will be an honorable inspiration porter :)
    "Our strategy determined by the following conditions,

    1. If A[i] is smallest among all end
      candidates of active lists, we will start
      new active list of length 1.

    2. If A[i] is largest among all end candidates of
      active lists, we will clone the largest active
      list, and extend it by A[i].

    3. If A[i] is in between, we will find a list with
      largest end element that is smaller than A[i].
      Clone and extend this list by A[i]. We will discard all
      other lists of same length as that of this modified list."

        public int lengthOfLIS(int[] nums) {
            int len = nums.length;
            if(len==0) return 0;
            int[] table = new int[len];
            table[0] = nums[0];
            int res = 1;
            for(int i = 1; i < len ; i++){
                if(nums[i]<table[0]){
                    table[0] = nums[i];
                }
                else if(nums[i]>table[res-1]){
                    table[res++] = nums[i];
                }
                else table[ceil(table,nums[i],res-1)] = nums[i];
            }
            return res;
        }
        
        private int ceil(int[] t, int target,int len) {
            int lo = 0, hi = len, mid;
            while(lo<hi) {
                mid = (lo + hi)/2;
                if(t[mid]<target) lo = mid + 1;
                else hi = mid;
            }
            return hi;
        }
    }

  • 1

    Great solution and detailed explanation. To be honest, the people who can come up with the tails table idea in a 45mins no-cheat-sheet interview must be either a genuis or a monster.


  • 0
    B

    hi! can anyone explain why we would need to have this line in the py section. All tests pass w/o it.
    size = max(i + 1, size)


  • 0
    M

    replace tails with nums also works

    public int lengthOfLIS(int[] nums) {
            int size = 0;
            for (int x : nums) {
                int i = 0, j = size;
                while (i != j) {
                    int m = i + (j - i) / 2;
                    if (nums[m] < x) {
                        i = m + 1;
                    } else {
                        j = m;
                    }
                }
                nums[i]= x;
                if (i == size) size++;
            }
            return size;
        }
    

  • 1
    Y

    @mengmengli815 I think you should not change the input data.


  • 0
    Y

    @dietpepsi thanks for explanation. To make the idea more clear:

    The key idea is to keep each Increasing subsequence as long as possible. This means two things:

    1. when we find a smaller number than my tail. I need to update my tail. This makes it possible to append more data to this sequence.
    2. if we find that the number is smaller than all the subsequence's tail, this means we could create a new subsequence with bigger size with this number as the tail

Log in to reply
 

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