LeetCode 300: Longest Increasing Subsequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 300: Longest Increasing Subsequence?

In LeetCode 300: Longest Increasing Subsequence, you’re given an integer array nums, and your task is to find the length of the longest strictly increasing subsequence—a sequence where each number is greater than the previous one, and you can skip numbers in between. For example, in [10, 9, 2, 5, 3, 7, 101, 18], one subsequence is [2, 5, 7, 101] (length 4), and that’s the longest possible. This problem tests your sequence-finding skills, sharing a vibe with dynamic programming classics like LeetCode 1143: Longest Common Subsequence.

Problem Statement

• Input: An integer array nums.
• Output: An integer—the length of the longest increasing subsequence.
• Rules: Subsequence must be strictly increasing; can skip elements; return length only.

Constraints

• nums length: 1 to 2500.
• Values: -10⁴ to 10⁴.

Examples

• Input: nums = [10,9,2,5,3,7,101,18]
• Output: 4 ([2,5,7,101])
• Input: nums = [0,1,0,3,2,3]
• Output: 4 ([0,1,2,3])
• Input: nums = [7,7,7,7,7]
• Output: 1 (no increase possible)

Understanding the Problem: Finding the Longest Climb

To solve LeetCode 300: Longest Increasing Subsequence in Python, we need to find the longest chain of numbers in nums where each one is bigger than the last, like picking stepping stones that only go up. For [10, 9, 2, 5, 3, 7], we could have [2, 5, 7] (length 3) or [2, 3, 7] (length 3), but [2, 5, 7, 101] (length 4) is longest. A naive way might be to try every possible subsequence, but that’s way too slow. Instead, we’ll use:

• Best Solution (DP with Binary Search): O(n log n) time, O(n) space—fast and smart.
• Alternative Solution (Basic DP): O(n²) time, O(n) space—simpler but slower.

Let’s dive into the DP with binary search solution with a friendly breakdown that’s easy to follow.

Best Solution: Dynamic Programming with Binary Search

Why This Is the Best Solution

The dynamic programming with binary search approach is the top choice for LeetCode 300 because it’s super efficient—O(n log n) time and O(n) space—combining DP’s sequence-building power with binary search’s speed to update a growing list. It keeps track of the smallest ending number for each subsequence length, making it fast to find and replace spots. It’s like building a ladder where each rung is the smallest possible step up—perfect for this problem!

How It Works

Let’s picture this like assembling a ladder:

• Step 1: Build a List of Ends:
• Keep a list tails where tails[i] is the smallest number that can end a subsequence of length i+1.
• Step 2: Process Each Number:
• For each num in nums:
• Use binary search to find where num fits in tails—the spot where tails[i] ≥ num.
• If num is bigger than everything in tails, append it (new longest subsequence).
• Otherwise, replace the smallest number ≥ num (keeps tails minimal).
• Step 3: Get the Length:
• The length of tails is the longest increasing subsequence length.
• Step 4: Why It Works:
• tails holds the smallest ends, ensuring we can extend or replace efficiently.
• Binary search makes updates O(log n) instead of O(n).
• Length of tails reflects the longest possible chain.

It’s like stacking blocks, swapping out bigger ones for smaller ones to keep climbing!

Step-by-Step Example

Example: nums = [10, 9, 2, 5, 3, 7, 101, 18]

• Init: tails = [].
• 10: tails = [10] (length 1).
• 9: tails = [9] (replace 10, still length 1).
• 2: tails = [2] (replace 9).
• 5: tails = [2, 5] (append, length 2).
• 3: tails = [2, 3] (replace 5, still length 2).
• 7: tails = [2, 3, 7] (append, length 3).
• 101: tails = [2, 3, 7, 101] (append, length 4).
• 18: tails = [2, 3, 7, 18] (replace 101, still length 4).
• Result: Length of tails = 4 (e.g., [2, 3, 7, 18] or [2, 5, 7, 101]).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # Step 1: List to hold smallest ends
        tails = []

        # Step 2: Process each number
        for num in nums:
            # Step 3: Binary search for insertion spot
            left, right = 0, len(tails)
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid

            # Step 4: Update tails
            if left == len(tails):  # Bigger than all, append
                tails.append(num)
            else:  # Replace smallest >= num
                tails[left] = num

        # Step 5: Return length
        return len(tails)

• Line 4: Start with an empty list tails for subsequence ends.
• Line 7-16: For each num:
• Line 8-14: Binary search:
• Find the smallest index where tails[mid] ≥ num.
• If num > tails[mid], search right; else, search left.
• Line 15-17: If left = len(tails), append num; else replace tails[left].
• Line 19: Return tails length—longest subsequence.

• Time Complexity: O(n log n)—n numbers, log n binary search each.
• Space Complexity: O(n)—tails list.

This is like a fast ladder builder—stack and swap smartly!

Alternative Solution: Basic Dynamic Programming

Why an Alternative Approach?

Basic dynamic programming uses a DP array—O(n²) time, O(n) space—to track the longest subsequence ending at each index. It’s slower but easier to grasp, like checking every step up to build the chain—great for learning the basics!

How It Works

Let’s think of this as a step-by-step climb:

• Step 1: DP array where dp[i] = longest subsequence ending at nums[i].
• Step 2: For each i, look back at all j < i:
• If nums[i] > nums[j], dp[i] = max(dp[i], dp[j] + 1).
• Step 3: Max of dp is the answer.

It’s like counting all possible climbs up to each spot!

Step-by-Step Example

Example: nums = [10, 9, 2, 5, 3, 7]

• Init: dp = [1, 1, 1, 1, 1, 1].
• i=1: 9 < 10, dp[1] = 1.
• i=2: 2 < 10, 2 < 9, dp[2] = 1.
• i=3: 5 > 2, dp[3] = max(1, 1+1) = 2.
• i=4: 3 > 2, dp[4] = max(1, 1+1) = 2.
• i=5: 7 > 2, 7 > 5, 7 > 3, dp[5] = max(1, 2+1, 2+1) = 3.
• Result: max(dp) = 3 ([2, 5, 7]).

Code for Basic DP Approach

Copy codeclass Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0

        dp = [1] * len(nums)  # Start with length 1 everywhere
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

• Time Complexity: O(n²)—n² comparisons.
• Space Complexity: O(n)—dp array.

It’s a steady build but slow!

Comparing the Two Solutions

• DP with Binary Search (Best):
• Pros: O(n log n) time, O(n) space, fast.
• Cons: Binary search to learn.
• Basic DP (Alternative):
• Pros: O(n²) time, O(n) space, simple logic.
• Cons: Slower.

Binary search wins big.

Additional Examples and Edge Cases

• [1]: 1.
• [3,2,1]: 1.
• [1,2,3]: 3.

Binary search is faster.

Complexity Breakdown

• Binary Search: Time O(n log n), Space O(n).
• Basic DP: Time O(n²), Space O(n).

Binary search rules.

Key Takeaways

• Binary Search: Fast ladder—smart!
• Basic DP: Step-by-step—clear!
• Sequences: Climbing is fun.
• Python Tip: Lists rock—see [Python Basics](/python/basics).

Final Thoughts: Climb That Chain

LeetCode 300: Longest Increasing Subsequence in Python is a neat sequence puzzle. DP with binary search zips to the top, while basic DP builds it steady. Want more? Try LeetCode 1143: Longest Common Subsequence or LeetCode 673: Number of Longest Increasing Subsequence. Ready to climb? Head to Solve LeetCode 300 on LeetCode and find that longest streak today!