LeetCode #300 Longest Increasing Subsequence Solution & Explanation

LeetCode Problem

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

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solution

C# Solution

Solution1

public class Solution {
    public int LengthOfLIS(int[] nums) {

        int[]arr = new int[nums.Length];
        Array.Fill(arr, 1);

        for(int i=1;i<nums.Length;i++){
            for(int j=0;j<i;j++){
                if (nums[i] > nums[j])
                {
                    arr[i] = Math.Max(arr[i], arr[j] + 1);
                }
            }        
        }
        return arr.Max();
    }
}

Time Complexity : O(n²)

In summary, this code uses dynamic programming to find the length of the longest increasing subsequence in an array of integers. The arr array is used to store the length of the longest increasing subsequence ending at each index.

Array.Fill(arr, 1); ➡ Initially, each individual element in the array is treated as a subsequence of length 1.

for (int i = 1; i < nums.Length; i++) and for (int j = 0; j < i; j++) ➡ is used to iterate through all combinations of elements. Here, i represents the current element, and j represents the elements before the current one.

arr[i] = Math.Max(arr[i], arr[j] + 1); ➡ represents the dynamic programming update. It ensures that the length of the longest increasing subsequence ending at index i is updated to the maximum of its current value arr[i] and the length of the subsequence ending at j plus one (arr[j] + 1).

Java Solution

Solution1

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[]arr = new int[nums.length];
        
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 1;
        }

        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if (nums[i] > nums[j])
                {
                    arr[i] = Math.max(arr[i], arr[j] + 1);
                }
            }        
        }
        return Arrays.stream(arr).max().orElse(0);
    }
}

Time Complexity : O(n²)

The Java Stream max() method returns an OptionalInt, so you need to use orElse to convert it to an integer.

Python3 Solution

Solution1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    arr[i] = max(arr[i], arr[j] + 1)

        return max(arr)

JavaScript Solution

Solution1

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    var arr = Array(nums.length).fill(1);

        for(let i=1;i<nums.length;i++){
            for(let j=0;j<i;j++){
                if (nums[i] > nums[j])
                {
                    arr[i] = Math.max(arr[i], arr[j] + 1);
                }
            }        
        }

        return (Math.max(...arr));
};

Conclusion

The current approach I can think of is O(n²), but the follow-up of the problem suggests there might be a solution in O(n log(n)). Let me take some time to think about it, and I will provide an update later.

P.S. Dynamic programming problems always seem challenging…

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Longest Increasing Subsequence – LeetCode

Some Random LeetCode posts