O(1) space, O(n log n) time, short solution without additional memory, Java


  • 16
    D
    public class Solution {
        public int lengthOfLIS(int[] nums) {
            int N = 0, idx, x;
            for(int i = 0; i < nums.length; i++) {
                x = nums[i];
                if (N < 1 || x > nums[N-1]) {
                    nums[N++] = x;
                } else if ((idx = Arrays.binarySearch(nums, 0, N, x)) < 0) {
                    nums[-(idx + 1)] = x;
                }
            }
            return N;
        }
    }
    

    Re-use the array given as input for storing the tails.


  • 0
    H

    whar does this mean:
    nums[-(idx + 1)] = x;

    negative index in array?


  • 0
    D

    As this statement is executed only if idx variable is negative (meaning there is no such tail in our DP part of the array at the moment), we use -(idx + 1) to convert it to the right position.

    If we already have this number in the array Arrays.binarySearch() will return positive index (or 0) - we don't need to update anything. But if it is not in the array then we update it.

    To avoid any confusion, look at the documentation of Arrays.binarySearch() (return part) here: http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[], int, int, int)


  • 0
    H

    Oh I c, it returns (-(insertion point) - 1) if search target is not in the array.


  • 0
    H

    Concise and elegant!


  • 0
    K

    This one is nice. But it has changed the input int[] nums, right?


  • 0
    S

    the code won't work with an input of 10,9,2,5,3,7,101,18,1,5,6,7,8,9,10,11

    the output should be 8 but this will output a 9 instead.


  • 0
    D

    Actually the answer IS 9 for the input you provided:

    2,3,5,6,7,8,9,10,11

    Total of 9 nums, increasing with each number.


  • 0
    P

    Guys, could someone explain this algorithm? I just can't get the general idea of it.


Log in to reply
 

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