Katkat
Back

Compute longest increasing subsequence length

PinduoduoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to solve the Longest Increasing Subsequence (LIS) problem, specifically targeting the transition from a standard dynamic programming approach to an optimized binary search solution.

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting zero or more elements without changing the order of the remaining elements. For example, [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7].

Function Signature

def length_of_lis(nums: List[int]) -> int:

Constraints

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1: Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4 Explanation: The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

Example 2: Input: nums = [0, 1, 0, 3, 2, 3] Output: 4 Explanation: The longest increasing subsequence is [0, 1, 2, 3].

Edge Cases

  • Single element arrays should return 1.
  • Arrays with all identical elements should return 1.
  • Strictly decreasing arrays should return 1.

Hints

Hint 1

Consider the standard dynamic programming approach where `dp[i]` represents the length of the LIS ending at index `i`.

Hint 2

The naive DP approach has a time complexity of O(n^2); can you maintain an auxiliary array that keeps track of the smallest possible tail for all increasing subsequences of various lengths?

Hint 3

If you maintain a sorted list of tail elements, you can use binary search (`bisect_left` in Python) to update this list in O(log n) time per element.

Follow-up questions

  • How would you modify the algorithm if the subsequence needed to be non-decreasing instead of strictly increasing?
  • Can you reconstruct the actual subsequence rather than just returning its length?
  • What is the space complexity of your optimized solution, and can it be improved?