Problem overview
The method lengthOfLIS receives an array of integers, nums, and returns the length of its longest strictly increasing subsequence. A subsequence is what remains after deleting some elements, possibly none, without reordering the rest. It is strictly increasing when every element is larger than the one before, so two equal values can't both be in it. Only the length is returned, not the subsequence itself.
For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4: [2, 3, 7, 101] and [2, 5, 7, 18] both qualify, and none has 5 elements. For [0, 1, 0, 3, 2, 3] the answer is also 4, through [0, 1, 2, 3]. For [7, 7, 7, 7, 7, 7, 7] it is 1, because equal values don't increase.
The statement asks for O(n²) time and O(n) extra space. A faster O(n log n) method exists, using a binary search over the smallest possible tail for each length. This lesson builds the simpler quadratic version.
Approach: the best subsequence ending at each index
Checking every subsequence is hopeless, since an array of n elements has 2^n of them. Instead, ask a smaller question for each index: what is the length of the longest strictly increasing subsequence that ends with nums[i]? Call it dp[i].
Every nums[i] alone is a subsequence of length 1, so each dp[i] starts at 1. To do better, look at every earlier index j. If nums[j] < nums[i], then nums[i] can follow the best subsequence that ends at j, giving length dp[j] + 1. Keep the largest such value over all j. The longest subsequence can end anywhere, so the final answer is the largest dp[i].
Take the 5 at index 3 as an example. The earlier values are 10, 9 and 2. Only the 2 is smaller, and its dp entry is 1, so dp[3] becomes 2. The 10 and the 9 are larger than 5, so they are ignored. Later entries build on earlier ones, which is why the table is worth keeping.
The table for [10, 9, 2, 5, 3, 7, 101, 18]:
[1, 1, 1, 2, 2, 3, 4, 4]The 7 at index 5 ends a subsequence of length 3 (for example 2, 5, 7 or 2, 3, 7), and the 101 and the 18 each extend it to 4. For [0, 1, 0, 3, 2, 3] the table is:
[1, 2, 1, 3, 3, 4]Step by step
- Store the length of
numsinn. Both loops run over the indexes. - Create
dpasnones, withvarbecause the loops write into it. No entry is ever less than 1. - Create
beststarting at 0, withvar. It keeps the largestdp[i]seen so far. - Loop
iover0..<n. Eachdp[i]needs only entries before it, and those are final by the time the loop reachesi. - Loop
jover0..<i. Only elements beforenums[i]can come before it in a subsequence. Fori = 0the range is empty and the loop doesn't run. - Check
nums[j] < nums[i]. The test is strict, so an equal value can't extend the subsequence. - Update
dp[i]tomax(dp[i], dp[j] + 1). This is the key line: it reuses the answer already computed forj. - After the inner loop, update
bestwithmax(best, dp[i]). At that pointdp[i]has seen everyj < i. - Return
bestafter the outer loop.
The solution in Swift
class Solution {
func lengthOfLIS(_ nums: [Int]) -> Int {
let n = nums.count
var dp = [Int](repeating: 1, count: n)
var best = 0
for i in 0..<n {
for j in 0..<i {
if nums[j] < nums[i] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
best = max(best, dp[i])
}
return best
}
}
The Swift details worth a closer look:
- Creating the table.
[Int](repeating: 1, count: n)builds an array ofncopies of 1. Arrays are value types, and sincedpis declared withvar,dp[i] = ...changes it in place. - Half-open ranges.
0..<iexcludesi, so the inner loop never compares an element with itself, and fori = 0it is an empty range that does nothing. Writing0...iwould includeiand compare an element with itself. maxis a global function.max(a, b)returns the larger of two values, with no import needed.- Empty input. With an empty array,
0..<nis an empty range and the method returns 0. Writing0...(n - 1)instead would crash, because0...-1is an invalid range in Swift.
Complexity
Time: O(n²). The two loops look at each pair j < i once, which is n · (n - 1) / 2 pairs, and each comparison takes constant time.
Space: O(n). The table dp has one integer per element. Everything else is a few variables.
Edge cases and common mistakes
- Duplicates.
[7, 7, 7, 7, 7, 7, 7]gives 1. Using<=instead of<would count equal values as increasing and return 7. - Sorted input.
[1, 2, 3, 4, 5]gives 5, and the table is[1, 2, 3, 4, 5]. - Decreasing input.
[5, 4, 3, 2, 1]gives 1: no pair satisfies the test, so everydp[i]stays 1. - Returning
dp[n - 1]. The longest subsequence need not end at the last element. In[1, 3, 2, 4]the table is[1, 2, 2, 3], and in[4, 10, 4, 3, 8, 9]it is[1, 2, 1, 1, 2, 3]. Taking the maximum over the table is what makes the method correct in general. - Starting
dpat 0. A single element is a subsequence of length 1, so entries must start at 1, or a one-element array would return 0. - Single element.
[5]gives 1.
Testing
[10, 9, 2, 5, 3, 7, 101, 18]gives4.[0, 1, 0, 3, 2, 3]gives4.[7, 7, 7, 7, 7, 7, 7]gives1.[1, 2, 3, 4, 5]gives5.[5, 4, 3, 2, 1]gives1.[1, 3, 2, 4]gives3.[4, 10, 4, 3, 8, 9]gives3.
