Coding Interview: How Do You Find the Longest Increasing Subsequence?

Problem and applicable scenarios

Given an integer array nums, return any longest strictly increasing subsequence. A subsequence preserves the relative order of the input but need not be contiguous. “Strictly increasing” means each next value must be greater, so equal values cannot increase the length. If several optimal answers exist, return any one. Return an empty array for empty input.

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

Increasing indices: 2 < 4 < 5 < 7
Increasing values:  2 < 3 < 7 < 18
Length: 4

Assume 0 ≤ n ≤ 100,000, signed 32-bit integer values, and an input array that must remain unchanged. This scale rules out enumerating subsequences and rules out quadratic dynamic programming as the final solution. The LeetCode problem asks for the length of a strictly increasing subsequence and explicitly follows up with an O(n log n) target. A public interview-preparation article dated April 2026 still teaches both the quadratic DP and binary-search optimization. This version additionally returns an actual subsequence. Those sources establish the problem and its present preparation value; they do not establish interview frequency or company attribution.

What the interviewer evaluates

The first signal is a precise state definition. The quadratic solution should define dp[i] as the best length that must end at nums[i]. Saying only “the answer for the first i values” discards the ending value needed to decide whether the current element can be appended.

The second signal is deriving the optimization from the bottleneck. Scanning every earlier j for every i costs O(n²). A stronger answer changes the state: for each reachable length, retain only the smallest ending value. A smaller tail is at least as easy to extend. These minimum tails are strictly increasing, so the update position can be found with binary search.

The third signal is handling duplicates correctly. A strictly increasing sequence requires the first position whose tail is greater than or equal to the current value: lower-bound semantics. An equal value replaces the same position and does not extend the length. Only a non-decreasing variant uses the first position strictly greater than the value.

The fourth signal is knowing that tails is not itself the answer. After [3, 5, 6, 2], the tail values are [2, 5, 6]. They increase by value, but their input indices are 3, 1, 2, so they are not a subsequence. To return a real path, also store the current input index for each tail length and a predecessor index for every element.

The final signal is proof and validation. A candidate should explain the minimum-tail invariant, why replacement cannot lose an optimal length, why predecessor links form a valid path, and how to compare random small inputs against an O(n²) oracle instead of relying on one example.

Questions to clarify before answering

• Strictly increasing or non-decreasing? This problem is strict, so duplicates cannot extend the answer. If

equality is allowed, the binary-search boundary changes.

• Return the length or an actual sequence? This problem returns a sequence, so it needs previous and tail

indices. A length-only solution can reduce auxiliary space to O(L), where L is the answer length.

• How should ties between optimal answers be resolved? Any answer is acceptable. Lexicographically smallest,

smallest-index, or stable selection requirements need additional rules and proof.

• What is the input size? At one hundred thousand elements, use O(n log n). For a few hundred elements,

quadratic DP is easier to implement, explain, and extend to counting.

• Can the input be empty? Yes; return []. This determines whether reconstruction may read a final tail

index.

• May the input be modified? No. Sorting destroys the original index order and changes the problem.
• Can integer arithmetic overflow? The algorithm compares and copies values without arithmetic on them, so

signed 32-bit inputs do not overflow because of the algorithm.

30-second answer framework

“I keep the smallest tail for every reachable length. Those tails are sorted, so for each value I binary-search the first tail greater than or equal to it, replace that position, or append at the end. This lower bound prevents duplicates from extending a strict sequence. The tail array may mix incompatible input indices, so I also store each tail's index and a predecessor per element, then reconstruct backward. One binary search per element gives O(n log n) time and O(n) space. I test empty, duplicate, decreasing, and random small arrays against a quadratic oracle.”

Step-by-step deep solution

Start with the baseline that is easiest to prove. Let dp[i] be the length of a longest strictly increasing subsequence that must end at nums[i]. Any answer longer than one has a penultimate element at some j < i with nums[j] < nums[i]:

dp[i] = 1 + max(dp[j]) over j < i and nums[j] < nums[i]
If no such j exists, dp[i] = 1
Final length = max(dp[i])

The definition also proves the recurrence. Every eligible predecessor can be extended by nums[i], while every optimal sequence ending at nums[i] must transition from one of those predecessors. The problem is that every i scans all earlier positions, for O(n²) total time.

For the optimization, maintain this prefix invariant: after processing the first i elements, tails[k] is the smallest possible ending value among all strictly increasing subsequences of length k + 1. For the current value x, locate the first position satisfying tails[k] ≥ x:

• If no position exists, x exceeds every tail and extends the longest sequence by one.
• If position k exists, replace tails[k] with x. The length is unchanged, but a smaller or equal tail cannot

reduce future extension choices.

• Because tails is strictly increasing, the position is found in O(log L) time.

For [3, 5, 6, 2], the first three states are [3], [3, 5], and [3, 5, 6]. The final 2 replaces the first position, producing [2, 5, 6]. The length remains correct, but 2 occurs after 5 and 6 in the input. This is the counterexample to returning tails directly.

Reconstruction needs two index structures. tailsIndices[k] stores the input position currently realizing the minimum tail for length k + 1. When nums[i] lands at position k, set previous[i] to tailsIndices[k - 1]. That predecessor occurs before i and has a strictly smaller value. Later tail replacements do not mutate predecessor links already written. Reconstruct backward from the final longest tail.

export function longestIncreasingSubsequence(nums: number[]): number[] {
  if (nums.length === 0) return []

  const tails: number[] = []
  const tailsIndices: number[] = []
  const previous = new Array<number>(nums.length).fill(-1)

  for (let index = 0; index < nums.length; index += 1) {
    const value = nums[index]
    let left = 0
    let right = tails.length

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2)
      if (tails[middle] < value) left = middle + 1
      else right = middle
    }

    const lengthIndex = left
    if (lengthIndex > 0) {
      previous[index] = tailsIndices[lengthIndex - 1]
    }

    if (lengthIndex === tails.length) {
      tails.push(value)
      tailsIndices.push(index)
    } else {
      tails[lengthIndex] = value
      tailsIndices[lengthIndex] = index
    }
  }

  const result = new Array<number>(tails.length)
  let index = tailsIndices[tails.length - 1]

  for (
    let resultIndex = result.length - 1;
    resultIndex >= 0;
    resultIndex -= 1
  ) {
    result[resultIndex] = nums[index]
    index = previous[index]
  }

  return result
}

Correctness has three parts. First, tails remains strictly increasing: removing the last item from a longer increasing sequence leaves a shorter sequence with a smaller tail. Second, binary-search replacement preserves the smallest realizable tail for every length; it improves extendability without inventing a longer sequence. Third, each tailsIndices[k] realizes a chain of length k + 1, with strictly increasing predecessor indices and values. Therefore tails.length cannot exceed the true optimum, and scanning any real LIS forces the structure to reach at least that length. The reconstructed predecessor chain is a valid optimal answer.

Each element performs one binary search over at most L tails, for O(n log L) time and the conventional upper bound O(n log n). The three arrays use O(n) space; the output itself uses O(L). The algorithm neither sorts the input nor depends on the numeric range.

Tests should check the length, strict increase, and input-index order:

const cases: Array<[number[], number]> = [
  [[10, 9, 2, 5, 3, 7, 101, 18], 4],
  [[0, 1, 0, 3, 2, 3], 4],
  [[7, 7, 7, 7], 1],
  [[5, 4, 3, 2, 1], 1],
  [[], 0],
]

for (const [nums, expectedLength] of cases) {
  const result = longestIncreasingSubsequence(nums)
  if (result.length !== expectedLength) throw new Error("wrong length")
  for (let i = 1; i < result.length; i += 1) {
    if (result[i - 1] >= result[i]) throw new Error("not increasing")
  }
}

A stronger check generates random arrays of length at most 12 and compares the optimized result length with an O(n²) DP oracle. A linear scan through the input should also verify that the returned values appear in order. Together these checks expose duplicate-boundary errors, incorrect binary-search conditions, and broken predecessors.

High-quality sample answer

“I will first confirm that the order is strict and that I must return an actual sequence. The quadratic solution defines dp[i] as the best length ending at nums[i] and checks every smaller predecessor. To eliminate that backward scan, I store the smallest possible tail for each length.

For a value x, I find the first tail greater than or equal to x. If none exists, x extends the current longest sequence. Otherwise, replacing that tail with x gives the same length a value that is at least as easy to extend. Strict increase requires this lower-bound position, so a duplicate replaces rather than extends.

The tail values summarize the best ending for each length; they need not come from compatible input indices. To return a real answer, tailsIndices[k] records the current tail index for length k + 1. When an element lands at position k, its predecessor is tailsIndices[k - 1]. After the scan, I follow predecessors from the longest tail and fill the output backward.

The invariant is that every tail is the smallest realizable tail for its length, and every tail index has a real predecessor chain. Replacement never removes an existing length and only improves future extension. Conversely, scanning every element of any real increasing subsequence forces the structure to reach at least that length, so the final length is optimal. One binary search per element gives O(n log n) time, and indices plus predecessors use O(n) space. I would test empty, duplicate, increasing, and decreasing inputs, then compare random small arrays with a quadratic oracle.”

Common mistakes

• Treating a subsequence as a contiguous subarray → A sliding window cannot skip elements → **Define the

answer by increasing input indices.**

• Sorting before solving → Sorting destroys the original relative order → Process values in input order.
• Defining dp[i] as a prefix optimum and transitioning directly → The optimum's tail may not accept the

current value → Require the state to end at i.

• Searching for the first tail strictly greater than the value in the strict variant → Duplicates incorrectly

extend the length → Search for the first tail greater than or equal to the value.

• Returning tails directly → Tail values may come from decreasing input indices → **Reconstruct with tail

indices and predecessor links.**

• Rewriting old predecessors after a tail replacement → A previously valid path is corrupted → **Keep each

predecessor immutable after assignment.**

• Proving only that tails are sorted → Sortedness alone does not prove optimal length → **Prove the minimum

realizable tail invariant and both length bounds.**

• Calling binary search plus array insertion O(log n) → Middle insertion shifts elements → **Only replace in

place or append at the end.**

• Running only the classic example → Duplicate and predecessor bugs remain hidden → **Use all-equal,

decreasing, empty, and randomized oracle tests.**

• Claiming high frequency at a named company → Public problem pages do not prove frequency or attribution →

State only the verified problem and algorithm value.

Follow-ups and responses

Follow-up 1: What changes for a longest non-decreasing subsequence?

Equal values may now extend the sequence. Change the boundary to the first position strictly greater than value, which is the right insertion point. Predecessors, reconstruction, and complexity remain the same. Changing only the final comparison without changing the binary-search boundary fails on duplicates.

Follow-up 2: Can a length-only answer use less space?

Yes. Remove tailsIndices and previous, and retain only the L minimum tail values for O(L) space. Time remains O(n log L). Returning a sequence already requires O(L) output, while this one-pass reconstruction uses predecessor information for each input position.

Follow-up 3: How do you count the number of longest increasing subsequences?

Minimum tails merge multiple paths of the same length, so they cannot recover counts directly. A simple solution maintains length[i] and count[i]: copy the predecessor count when a longer path is found and add counts when an equal-length path is found, for O(n²) time. Larger inputs can coordinate-compress values and use a Fenwick tree or segment tree storing a maximum-length-and-count pair, with careful merge rules to avoid double counting.

Follow-up 4: What if values arrive in an append-only stream?

The current LIS length is online: binary-search tails for each arriving value in O(log L) time. Retain indices and predecessors if an actual sequence must be available. If old values can be deleted, a minimum tail may depend on deleted data; this algorithm cannot undo that state locally, so dynamic structures or offline decomposition are needed.

Follow-up 5: What if every element has a weight and the goal is maximum total weight?

A minimum tail no longer summarizes the state because the same tail range can carry different accumulated weights. Coordinate-compress the values, query a Fenwick tree or segment tree for the best weight among smaller values, add the current weight, and update the current coordinate. Strict and non-decreasing variants still use different query boundaries. The time is O(n log n).

Follow-up 6: Does this code return the lexicographically smallest optimal answer?

It does not guarantee that. The replacement rule minimizes individual tail values but defines no stable ordering among complete optimal paths. One approach computes how much optimal prefix or suffix each index can support, then greedily selects values that can still finish an optimal-length answer. A smallest-value sequence and a smallest-index sequence are different requirements, so clarify which lexicographic order is intended first.