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

• ``````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.

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

negative index in array?

• 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)

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

• Concise and elegant!

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

• 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.

• 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.

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

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