Short Java solution using DP O(n log n)


  • 200
    J
    public class Solution {
        public int lengthOfLIS(int[] nums) {            
            int[] dp = new int[nums.length];
            int len = 0;
    
            for(int x : nums) {
                int i = Arrays.binarySearch(dp, 0, len, x);
                if(i < 0) i = -(i + 1);
                dp[i] = x;
                if(i == len) len++;
            }
    
            return len;
        }
    }

  • 22
    R

    Similar solution using ArrayList:

    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> dp = new ArrayList<>(nums.length);
        for (int num : nums) {
            if (dp.size() == 0 || dp.get(dp.size()-1) < num) dp.add(num);
            else {
                int i = Collections.binarySearch(dp, num);
                dp.set((i<0) ? -i-1 : i, num);
            }
        }
        return dp.size();
    }

  • 1

    This is the best solution I have ever seen.
    can you explain it?


  • 24
    J

    The basic idea is present in the majority of solutions shared for this task, I have only tried to implement it in a manner as concise as possible without damaging the code readability.

    The idea is that as you iterate the sequence, you keep track of the minimum value a subsequence of given length might end with, for all so far possible subsequence lengths. So dp[i] is the minimum value a subsequence of length i+1 might end with. Having this info, for each new number we iterate to, we can determine the longest subsequence where it can be appended using binary search. The final answer is the length of the longest subsequence we found so far.


  • 1
    J

    Hello, it's really a nice answer. But I have a question, how did you come up the idea of using binary search. And what if we need to return the subsequence, will binary search still work? I tried to print the subsequence of your answer, the answer is not correct. But the length is correct. For example: [10, 9, 2, 5, 6,3, 7, 101, 18] =》 your code's answer: [2, 3, 6,7, 101], But i think the right answer is [2, 5, 6,7, 101]. Thank you.


  • 0
    M
    This post is deleted!

  • 0
    M
    This post is deleted!

  • 0
    M

    This is a great solution. By the way, what is the difference between two versions of Arrays.binarySearch()? If substitute it with another one, it has the error: java.lang.ArrayIndexOutOfBoundsException: 8 for input [10,9,2,5,3,7,101,18]... Has anyone seen where the problem is?

    public class Solution {
        public int lengthOfLIS(int[] nums) {
            // keep track of the end elements of each lists
            int[] dp = new int[nums.length];
            int len = 0;
            for(int i = 0; i<nums.length; i++){
                int pos = Arrays.binarySearch(dp,nums[i]);
                if(pos < 0){
                   pos = - pos - 1;
                }
                dp[pos] = nums[i];
                if(pos == len) len++;
            }
            return len;
        }
    }

  • 11
    R

    Arrays.binarySearch() returns ( - insertion_index - 1) in cases where the element was not found in the array. Initially the dp array is all zeroes. For all zeroes array the insertion index for any element greater than zero is equal to the length of the array (dp.length in this case). This means that the number needs to be added to the end of the array to keep the array sorted.

    As a result pos is equal to insertion_index, which is equal to dp.length. So the dp[pos] = nums[i]; line fails, because pos is out of bounds.

    This problem does not happen when searching just part of the array by using Arrays.binarySearch(dp, 0, len, nums[i]), because in this case the insertion index is len.

    By the way the issue will happen on any input that contains a positive integer, e.g. [1].


  • 0
    Y
    This post is deleted!

  • 1
    E

    @julielong That's because dp[] is not storing the sequence as explained by the author in the reply. dp[i] is storing the smallest number such that the length is i+1.


  • 0
    G

    I think:
    if(i < 0) i = ~i;

    ... is clearer given the definition what return (<0 is not in array, return bitwise complement of position where it WOULD be if inserted).


  • 0
    P

    Where did you find the definition? According to Java API (https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(char[], int, int, char) It is defined as “index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1)”


  • 0
    G

    How is this solution better if your ArrayList's backed array has the same length as the original array (nums.length). That means you don't save any space using the dynamic array, but also the solution is heavier due to higher level data structure. You don't have to initialize your ArrayList with nums.length - then it will make sense.


  • 0
    G

    @spritmouselet in the original code "len" != dp.length.


  • 0
    R

    I didn't say it's better. It's just using ArrayList instead of a regular array. You're right that it would be more space efficient in most cases to not initialize the ArrayList with nums.length.


  • 0
    M

    Great Solution!! The way you construct dp is brilliant ~


  • 5
    F

    Hi guys, I understand this works great, but I'm confused why this approach is a DP? Can anyone give a recurrence relation for it? Thank you.


  • 0
    H

    Why can you use binary search on an array with trailing zeros?


  • 0
    N
    This post is deleted!

Log in to reply
 

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