Number of Longest Increasing Subsequences

📋

Problem

Imagine you are analyzing stock prices over days and want to find not just the longest increasing trend but also how many such longest trends exist.

Given an integer array nums, return the number of longest strictly increasing subsequences. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

1 ≤ nums.length ≤ 10^5-10^6 ≤ nums[i] ≤ 10^6

Edge cases: Single element array → output 1All elements equal → output equals array lengthStrictly increasing array → output 1

</>

IDE

def findNumberOfLIS(nums: list[int]) -> int:public int findNumberOfLIS(int[] nums)int findNumberOfLIS(vector<int>& nums)function findNumberOfLIS(nums)

def findNumberOfLIS(nums):
    # Write your solution here
    pass

class Solution {
    public int findNumberOfLIS(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findNumberOfLIS(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function findNumberOfLIS(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Greedy approach returns count 1 for all inputs, missing multiple LIS counts.✅ Implement DP that tracks counts for all LIS endings, summing counts when lengths match.

Wrong: 0Code returns 0 for empty or single-element input due to missing base case.✅ Add base case to return 0 for empty input and 1 for single-element input.

Wrong: 5Treating equal elements as increasing subsequences, inflating counts.✅ Use strict '>' comparison when updating lengths and counts to exclude equal elements.

Wrong: 3Allowing non-strictly increasing subsequences (using '>=' instead of '>').✅ Use strict '>' comparison to ensure subsequences are strictly increasing.

Wrong: TLEUsing brute force exponential recursion instead of DP.✅ Implement O(n^2) DP or better to avoid timeouts.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before tackling edge cases.

Understand why greedy solutions fail and how to count all LIS using DP.

Optimize your DP solution to handle larger inputs efficiently.

t1_01basic

Input{"nums":[1,3,5,4,7]}

Expected2

⏱ Performance - must finish in 2000ms

The longest increasing subsequence length is 4. There are two such subsequences: [1,3,4,7] and [1,3,5,7].

💡 Think about tracking both length and count of LIS ending at each index.

💡 Use dynamic programming with two arrays: lengths and counts.

💡 Update counts when you find another subsequence of the same length.

Why it failed: Incorrect count output: likely not updating counts correctly when equal length subsequences are found. Fix by adding counts instead of overwriting when lengths match.

✓ Correctly counts all longest increasing subsequences.

t1_02basic

Input{"nums":[2,2,2,2,2]}

Expected5

⏱ Performance - must finish in 2000ms

All elements are equal, so longest increasing subsequence length is 1, and each element forms one such subsequence, total 5.

💡 Consider that equal elements do not increase the subsequence length.

💡 Each element alone forms an LIS of length 1.

💡 Count should be the number of elements when all are equal.

Why it failed: Output less than array length: likely treating equal elements as increasing. Fix by using strict '>' comparison when updating lengths.

✓ Correctly handles equal elements as non-increasing.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subsequences, so count is 0.

💡 Check how your code handles empty input.

💡 Return 0 if input length is zero.

💡 Add a base case for empty array to avoid errors.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a condition to return 0 when nums is empty.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"nums":[10]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array has LIS length 1 and count 1.

💡 Single element always forms an LIS of length 1.

💡 Initialize lengths and counts arrays properly for single element.

💡 Return count 1 for single element input.

Why it failed: Returns 0 or more than 1 for single element. Fix by initializing counts to 1 for each element.

✓ Correctly returns 1 for single element input.

t2_03edge

Input{"nums":[1,2,3,4,5]}

Expected1

⏱ Performance - must finish in 2000ms

Strictly increasing array has exactly one LIS which is the entire array.

💡 Longest increasing subsequence length equals array length here.

💡 Count should be 1 because only one strictly increasing sequence covers all elements.

💡 Check that counts are not incremented incorrectly for strictly increasing sequences.

Why it failed: Returns count > 1 for strictly increasing input. Fix by ensuring counts only increment when equal length subsequences are found, not when strictly longer.

✓ Correctly returns 1 for strictly increasing input.

t2_04edge

Input{"nums":[5,4,3,2,1]}

Expected5

⏱ Performance - must finish in 2000ms

Strictly decreasing array has LIS length 1, each element alone forms an LIS, so count equals array length.

💡 Longest increasing subsequence length is 1 here.

💡 Each element is an LIS of length 1 by itself.

💡 Count should be equal to number of elements.

Why it failed: Returns count less than array length for decreasing input. Fix by initializing counts to 1 and not merging counts incorrectly.

✓ Correctly returns count equal to array length for strictly decreasing input.

t3_01corner

Input{"nums":[1,3,2,4,3,5]}

Expected3

⏱ Performance - must finish in 2000ms

LIS length is 4. The LIS are [1,2,3,5], [1,3,4,5], and [1,3,3,5] is invalid since 3 is not strictly increasing after 3, so total 3 valid LIS.

💡 Check that subsequences are strictly increasing, not non-decreasing.

💡 Verify counts accumulate correctly when multiple LIS of same length exist.

💡 Ensure you only add counts when nums[j] < nums[i], not <=.

Why it failed: Counts incorrect due to allowing non-strictly increasing subsequences. Fix by using strict '>' comparison when updating lengths and counts.

✓ Correctly counts only strictly increasing subsequences.

t3_02corner

Input{"nums":[1,2,4,3,5,4,7,2]}

Expected3

⏱ Performance - must finish in 2000ms

LIS length is 4. The LIS are [1,2,3,4], [1,2,4,5], and [1,2,4,7] among others, total count 3.

💡 Beware of greedy approaches that pick first increasing subsequence found.

💡 Use DP to count all LIS, not just one.

💡 Update counts by summing counts of all valid previous indices.

Why it failed: Greedy approach returns 1 instead of total count. Fix by implementing DP that tracks counts for all LIS endings.

✓ Correctly counts all LIS, not just one.

t3_03corner

Input{"nums":[1,3,5,4,7,2,2,2]}

Expected2

⏱ Performance - must finish in 2000ms

LIS length is 4. The LIS are [1,3,4,7] and [1,3,5,7]. The trailing equal 2s do not extend LIS.

💡 Check that repeated elements at the end do not increase LIS length.

💡 Ensure counts are not incremented incorrectly by equal elements.

💡 Use strict comparison and careful count updates.

Why it failed: Counts inflated by treating equal elements as increasing. Fix by using strict '>' comparison and not counting equal elements as extensions.

✓ Correctly ignores equal trailing elements for LIS count.

t4_01performance

Input{"nums":[1000000,999999,999998,999997,999996,999995,999994,999993,999992,999991,999990,999989,999988,999987,999986,999985,999984,999983,999982,999981,999980,999979,999978,999977,999976,999975,999974,999973,999972,999971,999970,999969,999968,999967,999966,999965,999964,999963,999962,999961,999960,999959,999958,999957,999956,999955,999954,999953,999952,999951,999950,999949,999948,999947,999946,999945,999944,999943,999942,999941,999940,999939,999938,999937,999936,999935,999934,999933,999932,999931,999930,999929,999928,999927,999926,999925,999924,999923,999922,999921,999920,999919,999918,999917,999916,999915,999914,999913,999912,999911,999910,999909,999908,999907,999906,999905,999904,999903,999902,999901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100, strictly decreasing sequence. O(n^2) DP must complete within 2 seconds.

💡 O(n^2) DP is borderline but should pass for n=100.

💡 Avoid brute force exponential solutions.

💡 Use DP with length and count arrays for efficiency.

Why it failed: TLE due to exponential or inefficient approach. Fix by implementing O(n^2) DP with memoization or iterative bottom-up.

✓ Algorithm runs within time limit using O(n^2) DP.

Practice

1. Consider the following code snippet for counting arithmetic subsequences. What is the final returned value when the input is [1, 3, 5]?

easy

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Trace dp and total for input [1,3,5]

   i=1,j=0: diff=2, dp[1][2]=0+1=1, total+=0=0; i=2,j=0: diff=4, dp[2][4]=0+1=1, total+=0=0; i=2,j=1: diff=2, dp[2][2]=dp[1][2]+1=1+1=2, total+=dp[1][2]=1

2. Step 2: Calculate final total

   Total after all iterations is 1, representing one arithmetic subsequence of length ≥ 3: [1,3,5].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only one arithmetic subsequence of length ≥ 3 exists [OK]

Hint: Only subsequences length ≥3 count; pairs add to dp but not total [OK]

Common Mistakes:

• Counting pairs as arithmetic subsequences
• Adding dp[i][diff] to total instead of dp[j][diff]

2. You are given a binary tree and need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A brute force approach that computes the height of every subtree multiple times and checks all paths.

B. A bottom-up depth-first search (DFS) that computes heights and updates the diameter in a single traversal.

C. A greedy approach that always chooses the longest child path at each node without recursion.

D. A dynamic programming approach on arrays that stores intermediate results for subproblems unrelated to tree structure.

Solution

1. Step 1: Understand the problem requires longest path between any two nodes, not necessarily through root

   The problem is to find the diameter, which is the longest path between any two nodes in the tree, possibly passing through any node.

2. Step 2: Identify the approach that computes height and diameter simultaneously in one DFS traversal

   The bottom-up DFS approach computes the height of subtrees and updates the diameter during the same recursion, ensuring O(n) time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bottom-up DFS avoids repeated height computations and covers all paths [OK]

Hint: Diameter requires single DFS updating max path sum [OK]

Common Mistakes:

• Assuming diameter passes only through root
• Using greedy without recursion
• Repeated height computations causing inefficiency

3. You need to find the shortest possible route that visits each city exactly once and returns to the starting city. The number of cities is small (up to 20), and you want an algorithm that efficiently explores all subsets of visited cities while caching intermediate results to avoid recomputation. Which approach best guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that always picks the nearest unvisited city next

B. Dynamic Programming with bitmasking to represent visited subsets and memoize partial paths

C. Simple brute force recursion without memoization to explore all permutations

D. Dijkstra's algorithm to find shortest paths between cities

Solution

1. Step 1: Understand problem constraints

   The problem requires visiting all cities exactly once and returning to start, which is the classic TSP problem.

2. Step 2: Identify suitable algorithm

   Greedy (A) fails to guarantee optimality. Brute force (C) is correct but inefficient. Dijkstra (D) finds shortest paths but not TSP routes. Bitmask DP (B) efficiently encodes visited subsets and caches results, guaranteeing optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask DP is the standard optimal approach for small TSP [OK]

Hint: Bitmask DP encodes visited sets efficiently [OK]

Common Mistakes:

• Greedy seems intuitive but fails on global optimality

4. Examine the following code snippet for longest increasing path. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line returning max value from dp

B. Line initializing dp with 1s

C. Line sorting cells by their matrix values

D. Line checking if matrix[x][y] > matrix[i][j] without boundary check

Solution

1. Step 1: Identify missing boundary check

   The code accesses matrix[x][y] without verifying x,y are within matrix bounds, risking IndexError.

2. Step 2: Confirm other lines are correct

   dp initialization, sorting, and return statements are correct and standard.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary checks are essential before accessing neighbors [OK]

Hint: Always check boundaries before neighbor access [OK]

Common Mistakes:

• Forgetting boundary checks causing crashes
• Misplaced memoization causing TLE
• Incorrect dp initialization

5. The following code attempts to implement the optimized LIS algorithm. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 3: initializing tails as empty list

B. Line 6: using bisect_left instead of bisect_right

C. Line 9: replacing tails[idx] with num + 1 instead of num

D. Line 10: returning length of tails

Solution

1. Step 1: Analyze line replacing tails element

   Replacing tails[idx] with num + 1 corrupts the tails array, which must store actual numbers from input.

2. Step 2: Understand impact

   This causes incorrect binary search behavior and wrong LIS length calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   tails must store input elements, not modified values [OK]

Hint: tails must store actual nums, not altered values [OK]

Common Mistakes:

• Confusing bisect_left with bisect_right
• Modifying values before storing in tails
• Misunderstanding tails purpose