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
Companies
Microsoft
Level of Question
Medium

Longest Increasing Subsequence LeetCode Solution
Table of Contents
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 Complexity | Space Complexity | |
C++ | O(n log n) | O(n) |
Java | O(n²) | O(n) |
JavaScript | O(n²) | O(n) |
Python | O(n²) | O(n) |