Number of Longest Increasing Subsequence - Practice Coding Problems

Number of Longest Increasing Subsequence - Problem

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

A subsequence is a sequence derived from an array by deleting some or no elements without changing the order of the remaining elements.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,6,7,9,4,10,5,6]

› Output: 2

💡 Note: The longest increasing subsequences are [1,3,6,7,9] and [1,3,6,7,10], both have length 5. So there are 2 longest increasing subsequences.

Example 2 — Single Element Repeated

$ Input: nums = [2,2,2,2,2]

› Output: 5

💡 Note: Each single element forms a valid increasing subsequence of length 1. Since there are 5 elements, there are 5 longest increasing subsequences.

Example 3 — Strictly Decreasing

$ Input: nums = [5,4,3,2,1]

› Output: 5

💡 Note: No increasing subsequence of length > 1 exists. Each single element is a longest increasing subsequence, giving us 5 subsequences of length 1.

Constraints

1 ≤ nums.length ≤ 2000
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array with elements that can form increasing subsequences

Process

Find all longest increasing subsequences

Output

Count how many longest subsequences exist

Key Takeaway

🎯 Key Insight: Use dynamic programming to simultaneously track the length and count of longest increasing subsequences ending at each position

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to track both the length of the longest increasing subsequence ending at each position and the count of such subsequences. The optimal approach uses dynamic programming with two arrays: one for lengths and one for counts. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Length and Count Arrays	O(n²)	O(n)	Use two arrays to track length and count of longest subsequences ending at each position
Generate All Subsequences	O(2ⁿ)	O(n)	Generate all possible increasing subsequences and count the longest ones

Dynamic Programming with Length and Count Arrays — Algorithm Steps

Initialize length and count arrays
For each position, check all previous positions
Update length and count based on increasing subsequences
Find maximum length and sum corresponding counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set all lengths to 1, all counts to 1

Fill Arrays

For each position, check all previous positions and update

Count Result

Find max length and sum counts where length equals max

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    if (n == 0) return 0;
    
    int* lengths = (int*)malloc(n * sizeof(int));
    int* counts = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        lengths[i] = 1;
        counts[i] = 1;
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (lengths[j] + 1 > lengths[i]) {
                    lengths[i] = lengths[j] + 1;
                    counts[i] = counts[j];
                } else if (lengths[j] + 1 == lengths[i]) {
                    counts[i] += counts[j];
                }
            }
        }
    }
    
    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        if (lengths[i] > maxLength) {
            maxLength = lengths[i];
        }
    }
    
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (lengths[i] == maxLength) {
            result += counts[i];
        }
    }
    
    free(lengths);
    free(counts);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: for each of n positions, check all previous positions

⚠ Quadratic Growth

Space Complexity

O(n)

Two arrays of size n to store length and count information

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Length and Count Arrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler