Number of Longest Increasing Subsequences

▶

Steps

setup

Coordinate Compression Setup

We extract the unique sorted values from the input array to compress coordinates, mapping each number to a smaller index range for Fenwick tree usage.

💡 Coordinate compression reduces the range of values, enabling efficient Fenwick tree operations on a smaller index set.

Line:

sorted_unique = sorted(set(nums))

💡 The compressed coordinates allow Fenwick tree indices to correspond to unique values in ascending order.

setup

Initialize Fenwick Tree

We create a Fenwick tree of size 4 (number of unique values) with all entries initialized to (length=0, count=0).

💡 Fenwick tree stores pairs (length, count) for LIS ending at each compressed coordinate.

Line:

fenw = FenwickTree(len(sorted_unique))

💡 Fenwick tree is ready to accumulate LIS information as we process each number.

fill_cells

Process First Number: 1

For number 1, we find its compressed index 1. We query Fenwick tree for max length and count of smaller numbers (index 0).

💡 Querying index 0 returns (0,0) since no smaller numbers exist before 1.

Line:

idx = get_index(num) - 1
length, count = fenw.query(idx)

💡 No smaller subsequences exist before 1, so length is 0 and count is 0.

fill_cells

Update Fenwick Tree for 1

We update Fenwick tree at index 1 with length=1 and count=1, representing subsequences ending at 1.

💡 Updating Fenwick tree propagates this info to indices covering 1.

Line:

fenw.update(get_index(num), length + 1, max(count,1))

💡 Fenwick tree now records one subsequence of length 1 ending at 1.

fill_cells

Process Second Number: 3

For number 3, compressed index is 2. Query Fenwick tree at index 1 for max length and count of smaller numbers.

💡 Query returns (1,1) from index 1, indicating one subsequence of length 1 before 3.

Line:

idx = get_index(num) - 1
length, count = fenw.query(idx)

💡 We can extend subsequences ending before 3 to length 2.

fill_cells

Update Fenwick Tree for 3

Update Fenwick tree at index 2 with length=2 and count=1, representing subsequences ending at 3.

💡 Update propagates to indices covering 2, recording longer subsequences.

Line:

fenw.update(get_index(num), length + 1, max(count,1))

💡 Fenwick tree now tracks subsequences of length 2 ending at 3.

fill_cells

Process Third Number: 5

For number 5, compressed index is 3. Query Fenwick tree at index 2 for max length and count of smaller numbers.

💡 Query returns (2,1) from index 2, indicating subsequences of length 2 before 5.

Line:

idx = get_index(num) - 1
length, count = fenw.query(idx)

💡 We can extend subsequences to length 3 ending at 5.

fill_cells

Update Fenwick Tree for 5

Update Fenwick tree at index 3 with length=3 and count=1, representing subsequences ending at 5.

💡 Update propagates to indices covering 3, recording longer subsequences.

Line:

fenw.update(get_index(num), length + 1, max(count,1))

💡 Fenwick tree now tracks subsequences of length 3 ending at 5.

fill_cells

Process Fourth Number: 4

For number 4, compressed index is 3. Query Fenwick tree at index 2 for max length and count of smaller numbers.

💡 Query returns (2,1) from index 2, indicating subsequences of length 2 before 4.

Line:

idx = get_index(num) - 1
length, count = fenw.query(idx)

💡 We can extend subsequences to length 3 ending at 4.

fill_cells

Update Fenwick Tree for 4 (Merge Counts)

Update Fenwick tree at index 3 with length=3 and count=1. Since length 3 equals current length, counts are added: 1 + 1 = 2.

💡 This step shows how multiple LIS of same length accumulate counts in Fenwick tree.

Line:

fenw.update(get_index(num), length + 1, max(count,1))

💡 Fenwick tree now records two subsequences of length 3 ending at 4 or 5.

fill_cells

Process Fifth Number: 7

For number 7, compressed index is 4. Query Fenwick tree at index 3 for max length and count of smaller numbers.

💡 Query returns (3,2) from index 3, indicating two subsequences of length 3 before 7.

Line:

idx = get_index(num) - 1
length, count = fenw.query(idx)

💡 We can extend subsequences to length 4 ending at 7.

fill_cells

Update Fenwick Tree for 7

Update Fenwick tree at index 4 with length=4 and count=2, representing subsequences ending at 7.

💡 Update propagates to index 4, recording the longest subsequences found so far.

Line:

fenw.update(get_index(num), length + 1, max(count,1))

💡 Fenwick tree now tracks two subsequences of length 4 ending at 7.

traverse

Query Final Result

Query Fenwick tree at index 4 to get the maximum length and total count of LIS in the entire array.

💡 This final query aggregates all subsequence info to produce the answer.

Line:

max_len, total_count = fenw.query(len(sorted_unique))

💡 The longest increasing subsequence length is 4, and there are 2 such subsequences.

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [(0, 0) for _ in range(size + 1)]  # STEP 2

    def update(self, i, length, count):
        while i <= self.size:
            cur_len, cur_count = self.tree[i]
            if length > cur_len:
                self.tree[i] = (length, count)  # STEP 4,6,8,10,12
            elif length == cur_len:
                self.tree[i] = (cur_len, cur_count + count)  # STEP 10
            i += i & (-i)

    def query(self, i):
        max_len, total_count = 0, 0
        while i > 0:
            cur_len, cur_count = self.tree[i]
            if cur_len > max_len:
                max_len, total_count = cur_len, cur_count  # STEP 3,5,7,9,11,13
            elif cur_len == max_len:
                total_count += cur_count
            i -= i & (-i)
        return max_len, total_count

def findNumberOfLIS(nums):
    sorted_unique = sorted(set(nums))  # STEP 1
    def get_index(x):
        import bisect
        return bisect.bisect_left(sorted_unique, x) + 1

    fenw = FenwickTree(len(sorted_unique))  # STEP 2
    for num in nums:
        idx = get_index(num) - 1
        length, count = fenw.query(idx)  # STEP 3,5,7,9,11
        fenw.update(get_index(num), length + 1, max(count,1))  # STEP 4,6,8,10,12
    max_len, total_count = fenw.query(len(sorted_unique))  # STEP 13
    return total_count

if __name__ == '__main__':
    print(findNumberOfLIS([1,3,5,4,7]))  # Output: 2

📊

Number of Longest Increasing Subsequences - Watch the Algorithm Execute, Step by Step

Watching each Fenwick tree query and update reveals how the algorithm efficiently accumulates counts of longest increasing subsequences without enumerating them explicitly.

Initializing dp array

i\w	0	1	2	3
i=0	(0,0)	(0,0)	(0,0)	(0,0)

Uninitialized Fenwick tree

Initializing dp array

i\w	0	1	2	3
i=0	(0,0)	(0,0)	(0,0)	(0,0)

Fenwick tree initialized

Item 0 - wt:1 val:1

i\w	0	1	2	3
i=0	(0,0)	(0,0)	(0,0)	(0,0)

Query index 0

Item 0 - wt:1 val:1

i\w	0	1	2	3
i=0	(1,1)	(0,0)	(0,0)	(0,0)

Update index 1

Item 1 - wt:3 val:3

i\w	0	1	2	3
i=0	(1,1)	(0,0)	(0,0)	(0,0)

Query index 1

Item 1 - wt:3 val:3

i\w	0	1	2	3
i=0	(1,1)	(2,1)	(0,0)	(2,1)

Update index 2

Item 2 - wt:5 val:5

i\w	0	1	2	3
i=0	(1,1)	(2,1)	(0,0)	(2,1)

Query index 2

Item 2 - wt:5 val:5

i\w	0	1	2	3
i=0	(1,1)	(2,1)	(3,1)	(3,1)

Update index 3

Item 3 - wt:4 val:4

i\w	0	1	2	3
i=0	(1,1)	(2,1)	(3,1)	(3,1)

Query index 2

Item 3 - wt:4 val:4

i\w	0	1	2	3
i=0	(1,1)	(2,1)	(3,2)	(3,2)

Update index 3 with merged counts

Item 4 - wt:7 val:7

i\w	0	1	2	3
i=0	(1,1)	(2,1)	(3,2)	(3,2)

Query index 3

Item 4 - wt:7 val:7

i\w	0	1	2	3
i=0	(1,1)	(2,1)	(3,2)	(4,2)

Update index 4

Initializing dp array

i\w	0	1	2	3
i=0	(1,1)	(2,1)	(3,2)	(4,2)

Answer cell

Key Takeaways

✓ Fenwick tree efficiently accumulates counts of longest increasing subsequences by storing (length, count) pairs at compressed indices.

This insight is hard to see from code alone because the Fenwick tree's internal state and propagation are abstract; visualization reveals how counts merge.

✓ When updating Fenwick tree, if a new subsequence length equals the current stored length, counts are added rather than replaced.

This merging of counts explains why multiple LIS can be counted without enumerating all subsequences explicitly.

✓ Querying Fenwick tree at index one less than current number's compressed index returns the best LIS info for all smaller numbers.

This shows how the algorithm builds on previously computed results, a key dynamic programming principle visualized step-by-step.

Practice

1. Consider the following Python code implementing the optimized LIS algorithm. What is the value of the variable tails after processing the input [3, 1, 2]?

easy

A. [1, 2, 3]

B. [1, 2]

C. [1, 3]

D. [3, 1, 2]

Solution

1. Step 1: Process num=3

   tails is empty, bisect_left returns 0, append 3 -> tails = [3]

2. Step 2: Process num=1

   bisect_left(tails,1) returns 0, replace tails[0] with 1 -> tails = [1]

3. Step 3: Process num=2

   bisect_left(tails,2) returns 1 (end of tails), append 2 -> tails = [1, 2]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   tails always sorted and minimal last elements [OK]

Hint: tails stores smallest possible ends of subsequences [OK]

Common Mistakes:

• Appending instead of replacing in tails
• Misunderstanding bisect_left index
• Confusing tails with actual subsequence

2. The following code attempts to count arithmetic subsequences but contains a subtle bug. Identify the line causing incorrect counting of subsequences.

medium

A. dp = [defaultdict(int) for _ in range(n)]

B. count_at_j = dp[j][diff]

C. dp[i][diff] += count_at_j + 1

D. total += dp[i][diff] # adding wrong value to total

Solution

1. Step 1: Understand counting logic

   Total should only increase by count_at_j, which counts subsequences extended by nums[i]. Adding dp[i][diff] counts pairs and subsequences multiple times.

2. Step 2: Identify incorrect line

   Line adding dp[i][diff] to total causes double counting; it should add only count_at_j.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct counting adds count_at_j, not dp[i][diff] [OK]

Hint: Only add count_at_j to total, not dp[i][diff] [OK]

Common Mistakes:

• Adding dp[i][diff] to total
• Not initializing dp correctly
• Counting pairs as subsequences

3. What is the time complexity of the optimal bottom-up DFS solution for computing the diameter of a binary tree with n nodes?

medium

A. O(n) because each node is visited once in the DFS traversal

B. O(n^2) due to repeated height computations in recursion

C. O(n log n) because height computations take log n time per node

D. O(n) but with additional O(n) space for memoization arrays

Solution

1. Step 1: Identify that naive recursive approach causes repeated height computations

   In naive recursion without memoization, height computations are repeated, causing O(n^2) time complexity.

2. Step 2: Confirm that optimal bottom-up DFS avoids repeated computations

   The question asks for the optimal bottom-up DFS solution, which is O(n), but the options are designed to test understanding of naive vs optimal.

3. Step 3: Since O(n) because each node is visited once in the DFS traversal states optimal O(n), but O(n^2) due to repeated height computations in recursion states O(n^2) due to repeated computations, and question asks for optimal solution, correct answer is A.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Single DFS traversal over n nodes -> O(n) time [OK]

Hint: Single DFS traversal means linear time [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming height calls cost log n each

4. What is the time complexity of the topological sort based DP solution for the longest increasing path in an m x n matrix?

medium

A. O(m * n * log(m * n))

B. O(m * n^2)

C. O(m * n * 4^{m*n})

D. O(m * n)

Solution

1. Step 1: Identify sorting cost

   Sorting all m*n cells by their values costs O(m*n*log(m*n)).

2. Step 2: Analyze DP updates

   Each cell checks up to 4 neighbors, so DP updates cost O(m*n) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, so complexity is O(m*n*log(m*n)) [OK]

Hint: Sorting cells dominates complexity [OK]

Common Mistakes:

• Assuming DP is O(m*n) ignoring sorting
• Confusing exponential brute force with DP
• Ignoring log factor from sorting

5. What is the time complexity of the bottom-up bitmask DP solution for the Travelling Salesman Problem with n cities, and why? Options:

medium

A. O(n * 2^n) because we process each subset and city once

B. O(2^n) because subsets dominate the complexity

C. O(n^2 * 2^n) because for each subset and city, we check all possible previous cities

D. O(n! ) because we consider all permutations of cities

Solution

1. Step 1: Identify loops in the code

   There are three nested loops: over all subsets (2^n), over all cities (n), and over all possible previous cities (n).

2. Step 2: Multiply loop complexities

   Total complexity is O(2^n * n * n) = O(n^2 * 2^n). O(n * 2^n) because we process each subset and city once misses the inner loop over previous cities, underestimating complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask DP complexity is well-known as O(n^2 * 2^n) [OK]

Hint: Remember triple nested loops: subsets, current city, previous city [OK]

Common Mistakes:

• Ignoring inner loop over previous cities leads to underestimation