#58 · 1D DP

Longest Increasing Subsequence

Given an integer array, return the length of the longest strictly increasing subsequence (elements in order, not necessarily adjacent).

MediumLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

DP table over positions

dp[i] = the length of the longest increasing subsequence that starts (or ends) at position i. It is one more than the best dp[j] over compatible positions j, so each cell needs a scan of the others: O(n²) in total.

Memory layout

A flat array of n integers.

Operation	Cost
time	O(n²)
space	O(n)

Tails array (patience sorting)

tails[k] stores the smallest possible last element of an increasing subsequence of length k + 1. The array is always sorted, so for each new number a binary search finds the first tail that is not smaller: replace it, or append if there is none.

Memory layout

A growing sorted array of at most n integers.

Operation	Cost
time	O(n log n)
space	O(n)

Why it fits

A subsequence is built left to right and only its last element matters for what can follow, which makes position (or last value) a complete state.
The tails array exploits an exchange argument: for a given length, a smaller ending is never worse, so only the smallest ending per length needs to be kept.
Because tails is sorted, finding where a new value belongs is a binary search instead of a scan.

Why alternatives degrade

Sorting the array and taking the longest run:: Sorting destroys the original order, which is what a subsequence depends on.
Greedy: always take the next larger element:: For 1, 100, 2, 3, 4 greedy picks 1 then 100 and stops at length 2, but 1, 2, 3, 4 has length 4.
Longest common subsequence with the sorted array:: That is correct for distinct values (LIS = LCS of the array and its sorted copy) but costs O(n²), no better than the direct DP.

Four approaches, from naive to production

1 · beginner

Recursion: longest chain from each start

time O(2ⁿ)space O(n)

from(i) is the length of the longest increasing subsequence beginning at position i: 1 plus the best from(j) over later positions j with a larger value. The answer is the maximum from(i).

int lengthOfLIS(vector<int>& nums) {
    function<int(int)> longestFrom = [&](int i) -> int {
        int best = 1;
        for (int j = i + 1; j < (int)nums.size(); j++) {
            if (nums[j] > nums[i]) best = max(best, 1 + longestFrom(j));
        }
        return best;
    };
    int answer = 0;
    for (int i = 0; i < (int)nums.size(); i++) answer = max(answer, longestFrom(i));
    return answer;
}

public int lengthOfLIS(int[] nums) {
    int answer = 0;
    for (int i = 0; i < nums.length; i++) answer = Math.max(answer, longestFrom(nums, i));
    return answer;
}
private int longestFrom(int[] nums, int i) {
    int best = 1;
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] > nums[i]) best = Math.max(best, 1 + longestFrom(nums, j));
    }
    return best;
}

def length_of_lis(nums):
    def longest_from(i):
        best = 1
        for j in range(i + 1, len(nums)):
            if nums[j] > nums[i]: best = max(best, 1 + longest_from(j))
        return best
    answer = 0
    for i in range(len(nums)): answer = max(answer, longest_from(i))
    return answer

function lengthOfLIS(nums: number[]): number {
  const from = (i: number): number => {
    let best = 1;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) best = Math.max(best, 1 + from(j));
    }
    return best;
  };
  let answer = 0;
  for (let i = 0; i < nums.length; i++) answer = Math.max(answer, from(i));
  return answer;
}

Flaws & bottlenecks

The same from(j) is recomputed by every earlier element that can reach j.
Exponential time on increasing arrays (every subset of an increasing array is an increasing subsequence).
Recursion depth is up to n.

Interviewer cross-questions

Why is a fully increasing array the worst case?

Say: Every later element is a valid extension, so from(0) calls from(1) … from(n − 1), and each of those branches the same way: the number of calls doubles with each extra element.

What are the overlapping subproblems?

Say: from(j) depends only on j, not on how we got there, yet it is recomputed for every path that leads to j.

How do you fix it?

Say: Store each from(i) the first time it is computed (memoisation) or compute the values from right to left.

2 · intermediate

Memoised recursion

time O(n²)space O(n)

Same recursion with a memo array: when from(i) is requested a second time, return the stored value.

int lengthOfLIS(vector<int>& nums) {
    vector<int> memo(nums.size(), 0);
    function<int(int)> longestFrom = [&](int i) -> int {
        if (memo[i] > 0) return memo[i];
        int best = 1;
        for (int j = i + 1; j < (int)nums.size(); j++) {
            if (nums[j] > nums[i]) best = max(best, 1 + longestFrom(j));
        }
        memo[i] = best;
        return best;
    };
    int answer = 0;
    for (int i = 0; i < (int)nums.size(); i++) answer = max(answer, longestFrom(i));
    return answer;
}

public int lengthOfLIS(int[] nums) {
    int[] memo = new int[nums.length];
    int answer = 0;
    for (int i = 0; i < nums.length; i++) answer = Math.max(answer, longestFrom(nums, memo, i));
    return answer;
}
private int longestFrom(int[] nums, int[] memo, int i) {
    if (memo[i] > 0) return memo[i];
    int best = 1;
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] > nums[i]) best = Math.max(best, 1 + longestFrom(nums, memo, j));
    }
    memo[i] = best;
    return best;
}

def length_of_lis(nums):
    memo = [0] * len(nums)
    def longest_from(i):
        if memo[i] > 0: return memo[i]
        best = 1
        for j in range(i + 1, len(nums)):
            if nums[j] > nums[i]: best = max(best, 1 + longest_from(j))
        memo[i] = best
        return best
    answer = 0
    for i in range(len(nums)): answer = max(answer, longest_from(i))
    return answer

function lengthOfLIS(nums: number[]): number {
  const memo = new Array<number>(nums.length).fill(0);
  const from = (i: number): number => {
    if (memo[i] > 0) return memo[i];
    let best = 1;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) best = Math.max(best, 1 + from(j));
    }
    memo[i] = best;
    return best;
  };
  let answer = 0;
  for (let i = 0; i < nums.length; i++) answer = Math.max(answer, from(i));
  return answer;
}

Flaws & bottlenecks

Each call still loops over all later positions: quadratic.
Recursion depth up to n.
The 0 sentinel works only because every real answer is at least 1.

Interviewer cross-questions

Why is it quadratic now?

Say: There are n states and each loops over up to n later positions: O(n²).

Why use 0 as "unknown"?

Say: A computed value is always at least 1 (the element alone), so 0 can never be a real answer.

Can the quadratic loop be avoided?

Say: Yes: keep, for each length, the smallest tail, and find the right length with a binary search.

3 · advanced

Bottom-up table, O(n²)

time O(n²)space O(n)

dp[i] starts at 1. Scan i from the right; for every later j with a larger value set dp[i] = max(dp[i], 1 + dp[j]). The answer is the maximum dp value.

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int answer = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (nums[j] > nums[i]) dp[i] = max(dp[i], 1 + dp[j]);
        }
        answer = max(answer, dp[i]);
    }
    return answer;
}

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int answer = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (nums[j] > nums[i]) dp[i] = Math.max(dp[i], 1 + dp[j]);
        }
        answer = Math.max(answer, dp[i]);
    }
    return answer;
}

def length_of_lis(nums):
    n = len(nums)
    dp = [1] * n
    answer = 0
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if nums[j] > nums[i]: dp[i] = max(dp[i], 1 + dp[j])
        answer = max(answer, dp[i])
    return answer

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array<number>(n).fill(1);
  let answer = 0;
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      if (nums[j] > nums[i]) dp[i] = Math.max(dp[i], 1 + dp[j]);
    }
    answer = Math.max(answer, dp[i]);
  }
  return answer;
}

Flaws & bottlenecks

Quadratic: too slow for arrays of 100,000 elements.
Reports only the length; the subsequence itself needs parent pointers.
The scan checks every later j even when most are smaller.

Interviewer cross-questions

How do you recover the subsequence?

Say: Store for each i the j that gave the best dp[i] (a "next" pointer), then follow the pointers from the position with the largest dp.

Why scan from the right?

Say: dp[i] needs final values of dp[j] for j > i; going right to left guarantees them. The mirrored version (ending at i, left to right) is equally valid.

How do you do better than O(n²)?

Say: Replace the inner scan with a binary search over a sorted array of the best tails: O(n log n).

4 · expert

Tails array + binary search

time O(n log n)space O(n)

Maintain tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1. For each number, binary-search the first tail that is not smaller; replace it, or append when none exists. The final size of tails is the answer.

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        int lo = 0, hi = tails.size();
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo == (int)tails.size()) tails.push_back(x); else tails[lo] = x;
    }
    return tails.size();
}

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

def length_of_lis(nums):
    tails = []
    for x in nums:
        lo, hi = 0, len(tails)
        while lo < hi:
            mid = (lo + hi) >> 1
            if tails[mid] < x: lo = mid + 1
            else: hi = mid
        if lo == len(tails): tails.append(x)
        else: tails[lo] = x
    return len(tails)

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

Flaws & bottlenecks

tails is not an actual subsequence, so extra bookkeeping (parent indices) is needed to reconstruct one.
The strictly increasing requirement needs the "first tail not smaller" rule: using "greater" instead would give the non-decreasing variant.
The exchange argument behind it is subtle to justify in an interview.

Interviewer cross-questions

Why is replacing a tail correct?

Say: A subsequence of the same length that ends in a smaller value is always at least as good for future extensions, and no information about the length is lost. So keep the smaller ending.

Is tails a valid increasing subsequence?

Say: Not necessarily: its entries may come from different subsequences and positions. Only its length equals the LIS length.

How would you change it for non-decreasing sequences?

Say: Search for the first tail strictly greater than x (upper bound) instead of the first tail not smaller (lower bound), so equal values extend the sequence.

Synchronized code walkthrough

Showing: Recursion: longest chain from each start — shares the player above; click any step to jump.

int lengthOfLIS(vector<int>& nums) {
    function<int(int)> longestFrom = [&](int i) -> int {
        int best = 1;
        for (int j = i + 1; j < (int)nums.size(); j++) {
            if (nums[j] > nums[i]) best = max(best, 1 + longestFrom(j));
        }
        return best;
    };
    int answer = 0;
    for (int i = 0; i < (int)nums.size(); i++) answer = max(answer, longestFrom(i));
    return answer;
}

public int lengthOfLIS(int[] nums) {
    int answer = 0;
    for (int i = 0; i < nums.length; i++) answer = Math.max(answer, longestFrom(nums, i));
    return answer;
}
private int longestFrom(int[] nums, int i) {
    int best = 1;
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] > nums[i]) best = Math.max(best, 1 + longestFrom(nums, j));
    }
    return best;
}

def length_of_lis(nums):
    def longest_from(i):
        best = 1
        for j in range(i + 1, len(nums)):
            if nums[j] > nums[i]: best = max(best, 1 + longest_from(j))
        return best
    answer = 0
    for i in range(len(nums)): answer = max(answer, longest_from(i))
    return answer

function lengthOfLIS(nums: number[]): number {
  const from = (i: number): number => {
    let best = 1;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) best = Math.max(best, 1 + from(j));
    }
    return best;
  };
  let answer = 0;
  for (let i = 0; i < nums.length; i++) answer = Math.max(answer, from(i));
  return answer;
}

int lengthOfLIS(vector<int>& nums) {
    vector<int> memo(nums.size(), 0);
    function<int(int)> longestFrom = [&](int i) -> int {
        if (memo[i] > 0) return memo[i];
        int best = 1;
        for (int j = i + 1; j < (int)nums.size(); j++) {
            if (nums[j] > nums[i]) best = max(best, 1 + longestFrom(j));
        }
        memo[i] = best;
        return best;
    };
    int answer = 0;
    for (int i = 0; i < (int)nums.size(); i++) answer = max(answer, longestFrom(i));
    return answer;
}

public int lengthOfLIS(int[] nums) {
    int[] memo = new int[nums.length];
    int answer = 0;
    for (int i = 0; i < nums.length; i++) answer = Math.max(answer, longestFrom(nums, memo, i));
    return answer;
}
private int longestFrom(int[] nums, int[] memo, int i) {
    if (memo[i] > 0) return memo[i];
    int best = 1;
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] > nums[i]) best = Math.max(best, 1 + longestFrom(nums, memo, j));
    }
    memo[i] = best;
    return best;
}

def length_of_lis(nums):
    memo = [0] * len(nums)
    def longest_from(i):
        if memo[i] > 0: return memo[i]
        best = 1
        for j in range(i + 1, len(nums)):
            if nums[j] > nums[i]: best = max(best, 1 + longest_from(j))
        memo[i] = best
        return best
    answer = 0
    for i in range(len(nums)): answer = max(answer, longest_from(i))
    return answer

function lengthOfLIS(nums: number[]): number {
  const memo = new Array<number>(nums.length).fill(0);
  const from = (i: number): number => {
    if (memo[i] > 0) return memo[i];
    let best = 1;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) best = Math.max(best, 1 + from(j));
    }
    memo[i] = best;
    return best;
  };
  let answer = 0;
  for (let i = 0; i < nums.length; i++) answer = Math.max(answer, from(i));
  return answer;
}

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int answer = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (nums[j] > nums[i]) dp[i] = max(dp[i], 1 + dp[j]);
        }
        answer = max(answer, dp[i]);
    }
    return answer;
}

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int answer = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (nums[j] > nums[i]) dp[i] = Math.max(dp[i], 1 + dp[j]);
        }
        answer = Math.max(answer, dp[i]);
    }
    return answer;
}

def length_of_lis(nums):
    n = len(nums)
    dp = [1] * n
    answer = 0
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if nums[j] > nums[i]: dp[i] = max(dp[i], 1 + dp[j])
        answer = max(answer, dp[i])
    return answer

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array<number>(n).fill(1);
  let answer = 0;
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      if (nums[j] > nums[i]) dp[i] = Math.max(dp[i], 1 + dp[j]);
    }
    answer = Math.max(answer, dp[i]);
  }
  return answer;
}

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        int lo = 0, hi = tails.size();
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo == (int)tails.size()) tails.push_back(x); else tails[lo] = x;
    }
    return tails.size();
}

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

def length_of_lis(nums):
    tails = []
    for x in nums:
        lo, hi = 0, len(tails)
        while lo < hi:
            mid = (lo + hi) >> 1
            if tails[mid] < x: lo = mid + 1
            else: hi = mid
        if lo == len(tails): tails.append(x)
        else: tails[lo] = x
    return len(tails)

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