Longest Increasing Subsequence LeetCode Solution

Last updated on January 21st, 2025 at 02:12 am

Here, we see a Longest Increasing Subsequence LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Binary Search, Dynamic Programming

Companies

Microsoft

Level of Question

Medium

Longest Increasing Subsequence LeetCode Solution

Longest Increasing Subsequence LeetCode Solution

1. Problem Statement

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

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

Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1

2. Coding Pattern Used in Solution

The coding pattern used in the provided code can be categorized as Dynamic Programming. Specifically, the problem is a variation of the Longest Increasing Subsequence (LIS) problem, which is a classic dynamic programming problem.

  • The C++ code uses a Modified Binary Search approach to optimize the LIS computation.
  • The Java, JavaScript, and Python codes use a Dynamic Programming (DP) Table approach to solve the problem.

3. Code Implementation in Different Languages

3.1 Longest Increasing Subsequence C++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> res;
        for(int i=0; i<nums.size(); i++) {
            auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
            if(it==res.end()) res.push_back(nums[i]);
            else *it = nums[i];
        }
        return res.size();
    }
};

3.2 Longest Increasing Subsequence Java

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxLength = Arrays.stream(dp).max().orElse(0);
        return maxLength;
    }
}

3.3 Longest Increasing Subsequence JavaScript

var lengthOfLIS = function(nums) {
    if (!nums || nums.length === 0) {
        return 0;
    }
    const n = nums.length;
    const dp = new Array(n).fill(1);
    for (let i = 1; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp);
};

3.4 Longest Increasing Subsequence Python

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        n = len(nums)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n log n)O(n)
JavaO(n²)O(n)
JavaScriptO(n²)O(n)
PythonO(n²)O(n)

Scroll to Top