Grokking Advanced Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Number of Longest Increasing Subsequence (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

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

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

Note: Sequences should be strictly increasing.

Examples

  1. Example 1:

    • Input: nums = [2, 6, 4, 3, 5]
    • Expected Output: 2
    • Explanation: The longest increasing subsequences are [2, 3, 5] and [2, 4, 5], both having a length of 3. Therefore, there are two such subsequences.

  2. Example 2:

    • Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
    • Expected Output: 4
    • Explanation: The longest increasing subsequences are [2, 3, 7, 18], [2, 5, 7, 18], [2, 3, 101], and [2, 5, 101], each having a length of 4. Thus, there are four such subsequences.

  3. Example 3:

    • Input: nums = [1, 5, 2, 6, 3, 7]
    • Expected Output: 3
    • Explanation: The longest increasing subsequences are [1, 2, 3, 7], [1, 2, 6, 7], and [1, 5, 6, 7].

Constraints:

  • 1 <= nums.length <= 2000
  • -10<sup>6</sup> <= nums[i] <= 10<sup>6</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible