Coders Crushby Napplied AI
Back to DSA Problems
MediumLeetCode #300Dynamic Programming

Longest Increasing Subsequence

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

Constraints
1 <= nums.length <= 2500, -10^4 <= nums[i] <= 10^4
Coders Crushby Napplied AI

The ultimate interview preparation platform. Master System Design, DSA, and tackle community challenges to crush your FAANG interviews.

System Design

  • All Problems
  • Easy
  • Hard

DSA

  • All Problems
  • Dynamic Programming
  • Graphs

More

  • Problems Arena
  • Growth Paths
  • AI Discovery

Coders Crush by Napplied AI - Built for engineers preparing for FAANG/MAANG interviews

Examples
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
[2,3,7,101]
Solution

Approach

O(n²) DP: dp[i] = max(dp[j] + 1) for j < i where nums[j] < nums[i]. O(n log n): maintain sorted list of smallest tails and use binary search.

def lengthOfLIS(nums):
    tails = []
    for num in nums:
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        if left == len(tails):
            tails.append(num)
        else:
            tails[left] = num
    return len(tails)
Complexity
Time:O(n log n)
Space:O(n)
Hints
  • 1.Think about what makes a good subsequence
  • 2.For O(n²): dp[i] = longest ending at i
  • 3.For O(n log n): maintain smallest tail for each length
Asked at
GoogleAmazonMetaMicrosoftApple