Number of Longest Increasing Subsequence LeetCode Solution

Number of Longest Increasing Subsequence LeetCode Solution

Problem Description

The Number of Longest Increasing Subsequence LeetCode Solution problem involves finding the number of longest increasing subsequences in an array. Given an unsorted array of integers, the task is to find the length of the longest increasing subsequence and the number of such subsequences with that maximum length.

Intuition

The problem can be approached using dynamic programming. We can maintain two arrays: length to store the length of the longest increasing subsequence ending at each index, and count to store the number of such subsequences. We iterate through the array, updating these arrays based on the increasing subsequence conditions.

Solution Approach

  1. Initialize two arrays: length of size n (length of the input array) and count of size n, both initialized to 1.
  2. Iterate through the array with two nested loops. For each pair of indices (i, j) where nums[i] < nums[j], update length[j] and count[j] based on the conditions.
  3. Find the maximum length in the length array.
  4. Iterate through the length array and accumulate the counts of subsequences with maximum length.
  5. Return the maximum length and the count of such subsequences.

Example Walkthrough

Consider the following array: [1, 3, 5, 4, 7]

  1. Initialize length and count arrays: [1, 1, 1, 1, 1] and [1, 1, 1, 1, 1].
  2. Iterate through the array:
    • For nums[1] = 3, update length[1] to 2 and count[1] to 1.
    • For nums[2] = 5, update length[2] to 3 and count[2] to 1.
    • For nums[3] = 4, update length[3] to 3 and count[3] to 1.
    • For nums[4] = 7, update length[4] to 4 and count[4] to 2.
  3. Find the maximum length, which is 4.
  4. Accumulate counts of subsequences with length 4, which is 2.
  5. Return the maximum length (4) and the count (2).

Code Solutions

    class Solution:
        def findNumberOfLIS(self, nums: List[int]) -> int:
            if not nums:
                return 0
    
            n = len(nums)
            lengths = [1] * n
            counts = [1] * n
    
            for j in range(n):
                for i in range(j):
                    if nums[i] < nums[j]:
                        if lengths[i] + 1 > lengths[j]:
                            lengths[j] = lengths[i] + 1
                            counts[j] = counts[i]
                        elif lengths[i] + 1 == lengths[j]:
                            counts[j] += counts[i]
    
            max_length = max(lengths)
            result = sum(count for length, count in zip(lengths, counts) if length == max_length)
    
            return result
    
    class Solution {
    public:
        int findNumberOfLIS(vector& nums) {
            if (nums.empty())
                return 0;
    
            int n = nums.size();
            vector lengths(n, 1);
            vector counts(n, 1);
    
            for (int j = 0; j < n; j++) {
                for (int i = 0; i < j; i++) {
                    if (nums[i] < nums[j]) {
                        if (lengths[i] + 1 > lengths[j]) {
                            lengths[j] = lengths[i] + 1;
                            counts[j] = counts[i];
                        } else if (lengths[i] + 1 == lengths[j]) {
                            counts[j] += counts[i];
                        }
                    }
                }
            }
    
            int maxLength = *max_element(lengths.begin(), lengths.end());
            int result = 0;
    
            for (int k = 0; k < n; k++) {
                if (lengths[k] == maxLength)
                    result += counts[k];
            }
    
            return result;
        }
    };
    
    class Solution {
        public int findNumberOfLIS(int[] nums) {
            if (nums == null || nums.length == 0)
                return 0;
    
            int n = nums.length;
            int[] lengths = new int[n];
            int[] counts = new int[n];
    
            Arrays.fill(lengths, 1);
            Arrays.fill(counts, 1);
    
            for (int j = 0; j < n; j++) {
                for (int i = 0; i < j; i++) {
                    if (nums[i] < nums[j]) {
                        if (lengths[i] + 1 > lengths[j]) {
                            lengths[j] = lengths[i] + 1;
                            counts[j] = counts[i];
                        } else if (lengths[i] + 1 == lengths[j]) {
                            counts[j] += counts[i];
                        }
                    }
                }
            }
    
            int maxLength = Arrays.stream(lengths).max().orElse(0);
            int result = 0;
    
            for (int k = 0; k < n; k++) {
                if (lengths[k] == maxLength)
                    result += counts[k];
            }
    
            return result;
        }
    }
    

    Time and Space Complexity

    Time Complexity: O(n^2) – Two nested loops are used to iterate through the array.

    Space Complexity: O(n) – Additional arrays lengths and counts of size n are used.

    Leave a Comment