Number of Longest Increasing Subsequence solution and explanation
Google
9 more videos on this problem
DP 47. Number of Longest Increasing Subsequencestake U forward · 20:46 · 197K views
Number of Longest Increasing Subsequence - Dynamic Programming - Leetcode 673 - PythonNeetCode · 22:12 · 47K views
Number of Longest Increasing Subsequence | LeetCode 673 | C++, Java, PythonKnowledge Center · 22:17 · 8K views
number of longest increasing subsequence | leetcode 673 | dp bottom upNaresh Gupta · 10:37 · 3K views
Leetcode - Number of Longest Increasing Subsequence (Python)Timothy H Chang · 7:48 · 3K views
[Java] Leetcode 673. Number of Longest Increasing Subsequence [DP Subsequence #7]Eric Programming · 16:53 · 1K views
LeetCode 673 Number of Longest Increasing SubsequenceJeevan Kumar - Cracckify · 12:13 · 1K views
Daily Leetcode #1207: Jul 21, 2023 - 673. Number of Longest Increasing SubsequenceProgramming Live with Larry · 10:01 · 496 views
Daily Leetcode #213: Oct 30, 2020 - 673. Number of Longest Increasing SubsequenceProgramming Live with Larry · 13:15 · 486 views
LeetCode 673. Number of Longest Increasing Subsequence | LIS Part 2 | Dynamic ProgrammingBase Case · 6:50 · 121 views
The problem
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Example 1:
Input: nums = [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: nums = [2,2,2,2,2] Output: 5 Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.
Constraints:
1 <= nums.length <= 2000-106 <= nums[i] <= 106- The answer is guaranteed to fit inside a 32-bit integer.
Approach overview
Problem Overview: You receive an integer array and must compute how many longest increasing subsequences (LIS) exist. The subsequence must be strictly increasing, and you return the count of subsequences that reach the maximum possible length.
The challenge is not just finding the LIS length. You must also track how many subsequences achieve that maximum length. This introduces a counting dimension on top of the classic LIS problem.
Approach 1: Brute Force Enumeration (Exponential Time, O(2^n) time, O(n) space)
The most direct approach generates every possible subsequence and checks whether it is strictly increasing. Track the longest length seen and count how many subsequences reach that length. This uses recursion or bitmask generation over the array. The method works for very small inputs but quickly becomes infeasible because the number of subsequences doubles with each element. It mainly helps build intuition about what qualifies as a valid increasing subsequence.
Approach 2: Dynamic Programming with Two Arrays (O(n^2) time, O(n) space)
The standard interview solution uses dynamic programming. Maintain two arrays:
length[i] stores the length of the longest increasing subsequence ending at index i. count[i] stores how many subsequences achieve that length ending at i.
Iterate through the array. For each index i, scan all previous indices j < i. If nums[j] < nums[i], the element can extend an increasing subsequence. Two cases occur: if length[j] + 1 is greater than the current best at i, update length[i] and copy count[j]. If it equals the current best, add count[j] because another LIS path reaches the same length. After processing all indices, find the global maximum length and sum counts of indices that achieve it. This approach is easy to implement and works well for typical constraints.
Approach 3: Fenwick Tree / Segment Tree Optimization (O(n log n) time, O(n) space)
The LIS counting process can also be accelerated using coordinate compression and a Binary Indexed Tree or Segment Tree. Each tree node stores the best LIS length and the number of ways to achieve it for values up to a certain rank. For every number, query the structure to find the best LIS ending with a smaller value, then update the structure with the new length and count. This reduces the nested loop and improves time complexity to O(n log n), which becomes useful for very large inputs.
Recommended for interviews: The dynamic programming solution with two arrays is the expected answer. It clearly demonstrates understanding of LIS transitions and how to track counts along with lengths. Brute force shows conceptual understanding, while the tree-based optimization demonstrates deeper knowledge of advanced data structures and performance improvements.
Approach 1: Dynamic Programming with Two Arrays
This approach utilizes two arrays to track the length of the longest increasing subsequence ending at each index and the count of such subsequences. The first array, lengths, will store the length of L.I.S. ending at each position, and the second array, counts, will store how many times such a subsequence appears. We iterate through each possible pair of indices to update these arrays accordingly.
def findNumberOfLIS(nums):
n = len(nums)
if n <= 0:
return 0
lengths = [1] * n
counts = [1] * n
max_len, result = 0, 0
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
if lengths[j] + 1 > lengths[i]:
lengths[i] = lengths[j] + 1
counts[i] = counts[j]
elif lengths[j] + 1 == lengths[i]:
counts[i] += counts[j]
if lengths[i] > max_len:
max_len = lengths[i]
result = counts[i]
elif lengths[i] == max_len:
result += counts[i]
return result
print(findNumberOfLIS([1, 3, 5, 4, 7]))import java.util.*;
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] lengths = new int[n];
int[] counts = new int[n];
Arrays.fill(lengths, 1);
Arrays.fill(counts, 1);
int maxLen = 0, result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
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];
}
}
}
if (lengths[i] > maxLen) {
maxLen = lengths[i];
result = counts[i];
} else if (lengths[i] == maxLen) {
result += counts[i];
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 3, 5, 4, 7};
System.out.println(sol.findNumberOfLIS(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if (n <= 0) return 0;
vector<int> lengths(n, 1);
vector<int> counts(n, 1);
int maxLen = 0, result = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
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];
}
}
}
if (lengths[i] > maxLen) {
maxLen = lengths[i];
result = counts[i];
} else if (lengths[i] == maxLen) {
result += counts[i];
}
}
return result;
}
int main() {
vector<int> nums = {1, 3, 5, 4, 7};
cout << findNumberOfLIS(nums) << endl;
return 0;
}function findNumberOfLIS(nums) {
const n = nums.length;
if (n <= 0) return 0;
const lengths = Array(n).fill(1);
const counts = Array(n).fill(1);
let maxLen = 0, result = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
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];
}
}
}
if (lengths[i] > maxLen) {
maxLen = lengths[i];
result = counts[i];
} else if (lengths[i] == maxLen) {
result += counts[i];
}
}
return result;
}
console.log(findNumberOfLIS([1, 3, 5, 4, 7]));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int findNumberOfLIS(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int *lengths = (int*)calloc(numsSize, sizeof(int));
int *counts = (int*)calloc(numsSize, sizeof(int));
for (int i = 0; i < numsSize; i++) {
lengths[i] = 1;
counts[i] = 1;
}
int maxLen = 0, result = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
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];
}
}
}
if (lengths[i] > maxLen) {
maxLen = lengths[i];
result = counts[i];
} else if (lengths[i] == maxLen) {
result += counts[i];
}
}
free(lengths);
free(counts);
return result;
}
int main() {
int nums[] = {1, 3, 5, 4, 7};
int numsSize = sizeof(nums)/sizeof(nums[0]);
printf("%d", findNumberOfLIS(nums, numsSize));
return 0;
}using System;
public class Solution {
public int FindNumberOfLIS(int[] nums) {
int n = nums.Length;
if (n == 0) return 0;
int[] lengths = new int[n];
int[] counts = new int[n];
Array.Fill(lengths, 1);
Array.Fill(counts, 1);
int maxLen = 0, result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
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];
}
}
}
if (lengths[i] > maxLen) {
maxLen = lengths[i];
result = counts[i];
} else if (lengths[i] == maxLen) {
result += counts[i];
}
}
return result;
}
public static void Main(string[] args) {
var nums = new int[] {1, 3, 5, 4, 7};
Solution sol = new Solution();
Console.WriteLine(sol.FindNumberOfLIS(nums));
}
}The Python solution relies on dynamic typing and constructs like list comprehensions to streamline the initialization of lengths and counts. The nested iteration pairs remain straightforward and easily track state within the constraints.
Time Complexity: O(n^2), due to nested loops iterating over the array.
Space Complexity: O(n), where n is the space allocated for storing lengths and counts.
Approach 2: Dynamic Programming
We define f[i] as the length of the longest increasing subsequence ending with nums[i], and cnt[i] as the number of longest increasing subsequences ending with nums[i]. Initially, f[i]=1, cnt[i]=1. Also, we define mx as the length of the longest increasing subsequence, and ans as the number of longest increasing subsequences.
For each nums[i], we enumerate all elements nums[j] in nums[0:i-1]. If nums[j] < nums[i], then nums[i] can be appended after nums[j] to form a longer increasing subsequence. If f[i] < f[j] + 1, it means the length of the longest increasing subsequence ending with nums[i] has increased, so we need to update f[i]=f[j]+1 and cnt[i]=cnt[j]. If f[i]=f[j]+1, it means we have found a longest increasing subsequence with the same length as before, so we need to increase cnt[i] by cnt[j]. Then, if mx < f[i], it means the length of the longest increasing subsequence has increased, so we need to update mx=f[i] and ans=cnt[i]. If mx=f[i], it means we have found a longest increasing subsequence with the same length as before, so we need to increase ans by cnt[i].
Finally, we return ans.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array nums.
function findNumberOfLIS(nums: number[]): number {
const n = nums.length;
let [ans, mx] = [0, 0];
const f: number[] = Array(n).fill(1);
const cnt: number[] = Array(n).fill(1);
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
if (f[i] < f[j] + 1) {
f[i] = f[j] + 1;
cnt[i] = cnt[j];
} else if (f[i] === f[j] + 1) {
cnt[i] += cnt[j];
}
}
}
if (mx < f[i]) {
mx = f[i];
ans = cnt[i];
} else if (mx === f[i]) {
ans += cnt[i];
}
}
return ans;
}func findNumberOfLIS(nums []int) (ans int) {
n, mx := len(nums), 0
f := make([]int, n)
cnt := make([]int, n)
for i, x := range nums {
for j, y := range nums[:i] {
if y < x {
if f[i] < f[j]+1 {
f[i] = f[j] + 1
cnt[i] = cnt[j]
} else if f[i] == f[j]+1 {
cnt[i] += cnt[j]
}
}
}
if mx < f[i] {
mx = f[i]
ans = cnt[i]
} else if mx == f[i] {
ans += cnt[i]
}
}
return
}impl Solution {
pub fn find_number_of_lis(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut ans = 0;
let mut mx = 0;
let mut f = vec![1; n];
let mut cnt = vec![1; n];
for i in 0..n {
for j in 0..i {
if nums[j] < nums[i] {
if f[i] < f[j] + 1 {
f[i] = f[j] + 1;
cnt[i] = cnt[j];
} else if f[i] == f[j] + 1 {
cnt[i] += cnt[j];
}
}
}
if mx < f[i] {
mx = f[i];
ans = cnt[i];
} else if mx == f[i] {
ans += cnt[i];
}
}
ans
}
}Approach 3: Binary Indexed Tree
We can use a binary indexed tree to maintain the length and count of the longest increasing subsequence in the prefix interval. We remove duplicates from the array nums and sort it to get the array arr. Then we enumerate each element x in nums, find the position i of x in the array arr by binary search, then query the length and count of the longest increasing subsequence in [1,i-1], denoted as v and cnt, then update the length and count of the longest increasing subsequence in [i] to v+1 and max(cnt,1). Finally, we query the length and count of the longest increasing subsequence in [1,m], where m is the length of the array arr, which is the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
class BinaryIndexedTree {
private n: number;
private c: number[];
private d: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
this.d = Array(n + 1).fill(0);
}
update(x: number, v: number, cnt: number): void {
while (x <= this.n) {
if (this.c[x] < v) {
this.c[x] = v;
this.d[x] = cnt;
} else if (this.c[x] === v) {
this.d[x] += cnt;
}
x += x & -x;
}
}
query(x: number): [number, number] {
let v = 0;
let cnt = 0;
while (x > 0) {
if (this.c[x] > v) {
v = this.c[x];
cnt = this.d[x];
} else if (this.c[x] === v) {
cnt += this.d[x];
}
x -= x & -x;
}
return [v, cnt];
}
}
function findNumberOfLIS(nums: number[]): number {
const arr: number[] = [...new Set(nums)].sort((a, b) => a - b);
const m: number = arr.length;
const tree: BinaryIndexedTree = new BinaryIndexedTree(m);
const search = (x: number): number => {
let l = 0,
r = arr.length;
while (l < r) {
const mid = (l + r) >> 1;
if (arr[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l + 1;
};
for (const x of nums) {
const i: number = search(x);
const [v, cnt]: [number, number] = tree.query(i - 1);
tree.update(i, v + 1, Math.max(cnt, 1));
}
return tree.query(m)[1];
}type BinaryIndexedTree struct {
n int
c []int
d []int
}
func newBinaryIndexedTree(n int) BinaryIndexedTree {
return BinaryIndexedTree{
n: n,
c: make([]int, n+1),
d: make([]int, n+1),
}
}
func (bit *BinaryIndexedTree) update(x, v, cnt int) {
for x <= bit.n {
if bit.c[x] < v {
bit.c[x] = v
bit.d[x] = cnt
} else if bit.c[x] == v {
bit.d[x] += cnt
}
x += x & -x
}
}
func (bit *BinaryIndexedTree) query(x int) (int, int) {
v, cnt := 0, 0
for x > 0 {
if bit.c[x] > v {
v = bit.c[x]
cnt = bit.d[x]
} else if bit.c[x] == v {
cnt += bit.d[x]
}
x -= x & -x
}
return v, cnt
}
func findNumberOfLIS(nums []int) int {
arr := make([]int, len(nums))
copy(arr, nums)
sort.Ints(arr)
m := len(arr)
tree := newBinaryIndexedTree(m)
for _, x := range nums {
i := sort.SearchInts(arr, x) + 1
v, cnt := tree.query(i - 1)
tree.update(i, v+1, max(cnt, 1))
}
_, ans := tree.query(m)
return ans
}struct BinaryIndexedTree {
n: usize,
c: Vec<i32>,
d: Vec<i32>,
}
impl BinaryIndexedTree {
fn new(n: usize) -> BinaryIndexedTree {
BinaryIndexedTree {
n,
c: vec![0; n + 1],
d: vec![0; n + 1],
}
}
fn update(&mut self, x: usize, v: i32, cnt: i32) {
let mut x = x as usize;
while x <= self.n {
if self.c[x] < v {
self.c[x] = v;
self.d[x] = cnt;
} else if self.c[x] == v {
self.d[x] += cnt;
}
x += x & x.wrapping_neg();
}
}
fn query(&self, mut x: usize) -> (i32, i32) {
let (mut v, mut cnt) = (0, 0);
while x > 0 {
if self.c[x] > v {
v = self.c[x];
cnt = self.d[x];
} else if self.c[x] == v {
cnt += self.d[x];
}
x -= x & x.wrapping_neg();
}
(v, cnt)
}
}
impl Solution {
pub fn find_number_of_lis(nums: Vec<i32>) -> i32 {
let mut arr: Vec<i32> = nums.iter().cloned().collect();
arr.sort();
let m = arr.len();
let mut tree = BinaryIndexedTree::new(m);
for x in nums.iter() {
if let Ok(i) = arr.binary_search(x) {
let (v, cnt) = tree.query(i);
tree.update(i + 1, v + 1, cnt.max(1));
}
}
let (_, ans) = tree.query(m);
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Two Arrays | Time Complexity: O(n^2), due to nested loops iterating over the array. |
| Dynamic Programming | – |
| Binary Indexed Tree | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(2^n) | O(n) | Conceptual understanding or very small arrays |
| Dynamic Programming with Length & Count Arrays | O(n^2) | O(n) | Standard interview solution and typical constraints |
| Fenwick Tree / Segment Tree Optimization | O(n log n) | O(n) | Large inputs where quadratic DP becomes too slow |
Frequently asked questions
Is Number of Longest Increasing Subsequence easy or hard?
The problem is rated Medium because it extends the classic Longest Increasing Subsequence problem. Finding the LIS length is already a common dynamic programming problem, but counting the number of optimal subsequences adds an extra layer of reasoning.
Number of Longest Increasing Subsequence Python/Java solution
Most implementations maintain two arrays: length[i] for LIS length ending at index i and count[i] for the number of such subsequences. This logic is straightforward to implement in Python, Java, C++, JavaScript, or C# with nested loops and simple array updates.
How to solve Number of Longest Increasing Subsequence in O(n log n)?
Use coordinate compression and maintain a Binary Indexed Tree or Segment Tree that stores the best LIS length and number of ways for each value range. For each number, query the structure for the best result among smaller values, then update the tree with the new length and count.
What is the best approach for Number of Longest Increasing Subsequence?
The most common approach uses dynamic programming with two arrays: one tracking the LIS length ending at each index and another tracking how many subsequences achieve that length. This solution runs in O(n^2) time and O(n) space and is the approach most interviewers expect.
Is Number of Longest Increasing Subsequence asked at Google/Amazon/Meta?
Variants of LIS and counting subsequences appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers often expect candidates to first recognize the LIS pattern and then extend it to count how many optimal subsequences exist.
What data structure is used in Number of Longest Increasing Subsequence?
The core solution uses arrays for dynamic programming. Optimized solutions may use advanced data structures such as Binary Indexed Trees (Fenwick Trees) or Segment Trees to efficiently query and update LIS states in O(log n) time.
What is the time complexity of Number of Longest Increasing Subsequence?
The standard dynamic programming solution runs in O(n^2) time because each element compares with all previous elements. Space complexity is O(n) for the length and count arrays. Optimized approaches using Fenwick Tree or Segment Tree reduce the time to O(n log n).