Here we solve 300. Longest Increasing Subsequence. It asks us for the length of the longest strictly increasing subsequence in an array. So, for the array [3, 2, 6, 2, 9, 2, 7, 1, 4, 2, 15, 16, 14, 18, 1], the answer would be 6, one of such arrays being [2, 6, 7, 15, 16, 18].

Solution

We solve this problem by iteratively building a subsequence from left to right, obeying the following rules:

Input: Integer Array nums
Initialize subsequence = [nums[0]]

for x in nums:
  if x > last element of subsequence
      append x to subsequence
  else
    find the first element greater than x in subsequence and replace it with x

 return length of subsequence

From the above, we can easily infer a space complexity of $O(1)$. Moreover, since we are iterating linearly over a linearly-growing subsequence, we also deduce a time complexity of $O(N^2)$.

The following is an example of the algorithm in work:

Example

But why the hell does this work??

In pure, spoken english, the essence of this solution is that when we update the subsequence, we do it incrementally.

  • Case 1: Appending to the end of the array
    • This is easy to understand - if this value is greater than all encountered thus far, obviously it will be the end of the strictly increasing subsequence. Mathematically, this implies that for any pair of indices $n, n+1$ in nums, we have that $$ \exists i, j, i<j \text{ such that } subsequence[n] = nums[i] \text{ and } subsequence[n+1] = nums[j] $$
  • Case 2: Replacing an existing element
    • We replace the smallest element greater than or equal to the new one we add. So, for any index $m$ that is replaced in the subsequence, after the replacement we are guaranteed that there exists some $nums[i]$ such that $subsequence[m] \leq nums[i] < subsequence[m+1]$

Using these two facts, we can observe that for any length of the subsequence array, it is possible to construct an actual subsequence from nums of that length.

So while our updates to the subsequence array may not give an actual subsequence, it reflects the structure of one, preserving the length.

Optimizations

We can use a binary search to update the subsequence instead. This will bring the overall runtime complexity down to $O(N*log(N))$.

Python Code

from bisect import bisect

def longestIncreasingSubsequence(nums: List[int]) -> int:
  subsequence = [nums[0]]
  for num in nums:
    if num > subsequence[-1]:
      subsequence.append(num)
    else:
      pos = bisect_left(subsequence, num)
      subsequence[pos] = num
  return len(subsequence)