73. Longest Increasing Subsequence · DSA Practice

Return the length of the longest strictly increasing subsequence of nums (elements keep their order but need not be adjacent). Can you do it in O(n log n)?

Example 1

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation: One LIS is 2, 3, 7, 101.

Example 2

Input: nums = [0,1,0,3,2,3]

Output: 4

Hint 1

O(n²): dp[i] = 1 + max(dp[j]) for j < i with nums[j] < nums[i].

Hint 2

O(n log n): keep the smallest possible tail for each length and binary-search where x goes.

Dynamic ProgrammingBinary Search

Approach 1: Quadratic DP

dp[i] = longest increasing subsequence ending at i.

⏱ Time O(n²)💾 Space O(n)

Approach 2: Patience sorting ✅

Binary search on the tails array.

⏱ Time O(n log n)💾 Space O(n)

Reference solution for Patience sorting (time O(n log n), space O(n)). Each solution passes every test in all four languages.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []      # tails[k] = smallest tail of any increasing subsequence of length k+1
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)       # extends the longest subsequence
            else:
                tails[i] = x          # a smaller tail for length i+1
        return len(tails)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int lo = 0, hi = size;               // first tail >= x
            while (lo < hi) { int mid = (lo + hi) / 2; if (tails[mid] < x) lo = mid + 1; else hi = mid; }
            tails[lo] = x;
            if (lo == size) size++;
        }
        return size;
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);   // first tail >= x
            if (it == tails.end()) tails.push_back(x); else *it = x;
        }
        return tails.size();
    }
};

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length; // first tail >= x
    while (lo < hi) { const mid = (lo + hi) >> 1; if (tails[mid] < x) lo = mid + 1; else hi = mid; }
    tails[lo] = x;
  }
  return tails.length;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Dynamic Programming (1-D).