Sweaty Imposter

Longest Increasing Subsequence

MediumDynamic Programming (1-D & 2-D)Blind 75MidOpen on LeetCodeUpdated

You're given an integer array nums. Return the length of its longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements, so the chosen values don't have to be adjacent. Strictly increasing means each chosen value is greater than the one before it, so equal values can't both be used. Aim for O(n log n) time.

Examples

nums = [10,9,2,5,3,7,101,18] returns 4

10091225334751016187
One longest increasing choice: 2, 3, 7, 101.

One longest choice is 2, 3, 7, 101, and 2, 5, 7, 18 works too. No increasing subsequence of length 5 exists.

nums = [0,1,0,3,2,3] returns 4

0, 1, 2, 3 (from indices 0, 1, 4 and 5) is strictly increasing and has length 4.

nums = [7,7,7,7,7,7,7] returns 1

All values are equal, and equal values don't count as increasing, so only a single 7 can be chosen.

Constraints

  • 1 <= nums.length <= 2500

Hints

Hint 1

What property must the next element have to extend a subsequence you've been building?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Keep an array tails where tails[i] is the smallest value that can end an increasing subsequence of length i + 1. tails stays sorted, so for each number, binary search for the first entry >= it. If none exists, append the number: it extends the longest subsequence so far. Otherwise overwrite that entry, since a smaller ending leaves more room to grow. The length of tails is the answer, though tails itself isn't necessarily a real subsequence. O(n log n) time, O(n) space.

Time

O(n log n)

Space

O(n)

Pitfall

Searching for the first entry > n (bisect_right) instead of >= n lets equal values extend a subsequence, so [7,7,7,7,7,7,7] would return 7 instead of 1. And don't return tails as the subsequence; it only tracks lengths.

Solutions

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int n : nums) {
            int lo = 0, hi = tails.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails.get(mid) < n) lo = mid + 1;
                else hi = mid;
            }
            if (lo == tails.size()) tails.add(n);
            else tails.set(lo, n);
        }
        return tails.size();
    }
}
Drill This