LeetCode 300: Longest Increasing Subsequence Solution

Master LeetCode problem 300 (Longest Increasing Subsequence), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

300. Longest Increasing Subsequence

Medium

Array Binary Search Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming with a slightly modified approach to find the longest increasing subsequence. We will create an array dp to store the length of the longest increasing subsequence ending at index i. For each element at index i, we iterate through all previous elements to find the maximum length ending at index i.

The time complexity of this dynamic programming approach is O(n^2), where n is the number of elements in the input array. However, we can optimize this solution to run in O(n log(n)) time complexity using a binary search-based approach.

The optimized algorithm involves maintaining a separate array tails which will store the smallest tail of all increasing subsequences with length i+1. We iterate through the input array and update the tails array based on the current element's value. The length of the longest increasing subsequence will be the length of the tails array.

Solution Code

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] tails = new int[n];
        int len = 0;
        
        for (int num : nums) {
            int i = 0, j = len;
            while (i < j) {
                int mid = i + (j - i) / 2;
                if (tails[mid] < num) {
                    i = mid + 1;
                } else {
                    j = mid;
                }
            }
            tails[i] = num;
            if (i == len) {
                len++;
            }
        }
        
        return len;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 300 (Longest Increasing Subsequence)?

This page provides optimized solutions for LeetCode problem 300 (Longest Increasing Subsequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 300 (Longest Increasing Subsequence)?

The time complexity for LeetCode 300 (Longest Increasing Subsequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 300 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 300 in Java, C++, or Python.

Back to LeetCode Solutions