Longest Increasing Subsequence

▶

Steps

setup

Initialize tails array as empty

Start with an empty 'tails' array which will store the smallest tail values of increasing subsequences.

💡 This empty array is the foundation; it will grow as we process numbers and track subsequences.

Line:

tails = []

💡 The algorithm begins with no subsequences, so tails is empty.

fill_cells

Process first number 10: append to tails

The first number 10 is processed. Since tails is empty, 10 is appended as the smallest tail of subsequence length 1.

💡 The first element always starts the first subsequence of length 1.

Line:

num = 10
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
    tails.append(num)

💡 Appending 10 means we have an increasing subsequence of length 1 ending with 10.

fill_cells

Process second number 9: replace tails[0]

Number 9 is processed. Binary search finds position 0 in tails to replace 10 with 9, since 9 < 10.

💡 Replacing tails[0] with a smaller number keeps subsequences optimal for future extensions.

Line:

num = 9
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
    tails.append(num)
else:
    tails[idx] = num

💡 Replacing 10 with 9 means we have a better (smaller) tail for subsequence length 1, allowing longer subsequences later.

fill_cells

Process third number 2: replace tails[0]

Number 2 is processed. Binary search finds position 0 to replace 9 with 2, improving the smallest tail for subsequence length 1.

💡 Continuously replacing with smaller tails keeps subsequences flexible for future growth.

Line:

num = 2
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
    tails.append(num)
else:
    tails[idx] = num

💡 2 is now the smallest tail for subsequence length 1, enabling longer subsequences later.

fill_cells

Process fourth number 5: append to tails

Number 5 is processed. Binary search finds position 1 (end of tails), so 5 is appended, extending subsequence length to 2.

💡 Appending means we found a longer increasing subsequence ending with 5.

Line:

num = 5
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
    tails.append(num)
else:
    tails[idx] = num

💡 tails now represents smallest tails for subsequences of length 1 and 2: [2,5].

fill_cells

Process fifth number 3: replace tails[1]

Number 3 is processed. Binary search finds position 1 to replace 5 with 3, improving the tail for subsequence length 2.

💡 Replacing with smaller tail keeps subsequences optimal for future extensions.

Line:

num = 3
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
    tails.append(num)
else:
    tails[idx] = num

💡 tails now is [2,3], better than [2,5] for subsequences of length 2.

fill_cells

Process sixth number 7: append to tails

Number 7 is processed. Binary search finds position 2 (end of tails), so 7 is appended, extending subsequence length to 3.

💡 Appending means a longer increasing subsequence ending with 7 is found.

Line:

num = 7
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
    tails.append(num)
else:
    tails[idx] = num

💡 tails now represents smallest tails for subsequences of length 1, 2, and 3: [2,3,7].

fill_cells

Process seventh number 101: append to tails

Number 101 is processed. Binary search finds position 3 (end of tails), so 101 is appended, extending subsequence length to 4.

💡 Appending 101 extends the longest subsequence found so far.

Line:

num = 101
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
    tails.append(num)
else:
    tails[idx] = num

💡 tails now represents smallest tails for subsequences of length 1 to 4: [2,3,7,101].

fill_cells

Process eighth number 18: replace tails[3]

Number 18 is processed. Binary search finds position 3 to replace 101 with 18, improving the tail for subsequence length 4.

💡 Replacing 101 with smaller 18 keeps subsequences optimal for future extensions.

Line:

num = 18
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
    tails.append(num)
else:
    tails[idx] = num

💡 tails now is [2,3,7,18], representing improved tails for subsequences up to length 4.

reconstruct

Return length of tails as LIS length

All numbers processed. The length of tails array is returned as the length of the longest increasing subsequence.

💡 The length of tails corresponds to the LIS length because each element represents a subsequence length's smallest tail.

Line:

return len(tails)

💡 The LIS length for input [10,9,2,5,3,7,101,18] is 4.

import bisect

def lengthOfLIS(nums):
    tails = []  # STEP 1: initialize tails
    for i, num in enumerate(nums):  # STEP 2-9: process each number
        idx = bisect.bisect_left(tails, num)  # binary search position
        if idx == len(tails):  # append if num is larger than all tails
            tails.append(num)  # append operation
        else:
            tails[idx] = num  # replace operation
    return len(tails)  # STEP 10: return length

if __name__ == '__main__':
    print(lengthOfLIS([10,9,2,5,3,7,101,18]))  # Output: 4

📊

Longest Increasing Subsequence - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization helps you understand how the algorithm efficiently maintains subsequence tails to find the LIS length without enumerating all subsequences.

Initializing dp array

i\w	0	1	2	3	4	5	6	7
i=0	?	?	?	?	?	?	?	?

Item 0 - wt:0 val:10

i\w	0	1	2	3	4	5	6	7
i=0	10	?	?	?	?	?	?	?

append 10

Item 1 - wt:0 val:9

i\w	0	1	2	3	4	5	6	7
i=0	9	?	?	?	?	?	?	?

replace 10 with 9

Item 2 - wt:0 val:2

i\w	0	1	2	3	4	5	6	7
i=0	2	?	?	?	?	?	?	?

replace 9 with 2

Item 3 - wt:0 val:5

i\w	0	1	2	3	4	5	6	7
i=0	2	5	?	?	?	?	?	?

append 5

Item 4 - wt:0 val:3

i\w	0	1	2	3	4	5	6	7
i=0	2	3	?	?	?	?	?	?

replace 5 with 3

Item 5 - wt:0 val:7

i\w	0	1	2	3	4	5	6	7
i=0	2	3	7	?	?	?	?	?

append 7

Item 6 - wt:0 val:101

i\w	0	1	2	3	4	5	6	7
i=0	2	3	7	101	?	?	?	?

append 101

Item 7 - wt:0 val:18

i\w	0	1	2	3	4	5	6	7
i=0	2	3	7	18	?	?	?	?

replace 101 with 18

Item 7 - wt:0 val:18

i\w	0	1	2	3	4	5	6	7
i=0	2	3	7	18	?	?	?	?

final tails

Key Takeaways

✓ The 'tails' array stores the smallest possible tail values for increasing subsequences of each length.

This insight is hard to see from code alone because the array is updated non-intuitively via replacements, not by storing actual subsequences.

✓ Binary search efficiently finds where to place each number in 'tails', enabling O(n log n) time complexity.

Visualizing each binary search step clarifies why the algorithm is faster than naive DP approaches.

✓ Replacing elements in 'tails' with smaller numbers keeps subsequences optimally extendable.

Seeing replacements step-by-step shows how the algorithm maintains flexibility for longer subsequences.

Practice

1. Given an integer array, you need to count all arithmetic subsequences of length ≥ 3. Which approach guarantees an optimal solution that efficiently counts subsequences by their common difference without enumerating all subsequences explicitly?

easy

A. Brute force enumeration of all subsequences and checking arithmetic property

B. Dynamic programming with hash maps storing counts of subsequences by difference

C. Greedy approach selecting longest arithmetic subsequence only

D. Sorting the array and using two pointers to find arithmetic triplets

Solution

1. Step 1: Understand problem constraints

   Counting all arithmetic subsequences of length ≥ 3 requires tracking subsequences by their common difference, which brute force cannot do efficiently.

2. Step 2: Identify approach that counts subsequences by difference

   DP with hash maps stores counts of subsequences ending at each index with a given difference, enabling O(n²) time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP with hash maps is the known optimal approach for this problem [OK]

Hint: Counting subsequences by difference requires DP with hash maps [OK]

Common Mistakes:

• Thinking greedy or sorting solves counting all subsequences
• Assuming brute force is feasible for large n

2. Consider the following iterative postorder traversal code snippet for computing the maximum path sum in a binary tree. Given the tree: 1 / \ 2 3 What is the final value of max_sum after the algorithm completes?

easy

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Trace gains for leaf nodes

   Node 2 and Node 3 are leaves, so gains[2] = 2, gains[3] = 3, max_sum updated to max(-inf, 2) = 2, then max(2,3) = 3.

2. Step 2: Compute gains for root node 1

   left_gain = max(gains[2],0) = 2, right_gain = max(gains[3],0) = 3, price_newpath = 1 + 2 + 3 = 6, max_sum updated to max(3,6) = 6.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of path 2 -> 1 -> 3 is 6 [OK]

Hint: Sum path through root includes both children gains [OK]

Common Mistakes:

• Forgetting to add both children
• Using only max child gain
• Off-by-one in stack processing

3. You are given a 2D grid of integers and need to find the length of the longest strictly increasing path moving only up, down, left, or right. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that always moves to the neighbor with the largest value

B. Topological sort based dynamic programming processing cells in ascending order of their values

C. Simple DFS from each cell without memoization

D. Breadth-first search layer by layer from the smallest values

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest strictly increasing path in a matrix, which can be modeled as a directed graph where edges go from smaller to larger values.

2. Step 2: Identify suitable algorithm

   Topological sort based DP processes nodes in ascending order, ensuring all dependencies are resolved before updating dp values, guaranteeing optimal substructure and avoiding recomputation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Topological sort ensures correct order for DP updates [OK]

Hint: Longest increasing path -> topological sort DP [OK]

Common Mistakes:

• Assuming greedy always works
• Using DFS without memoization causing TLE
• Using BFS layer by layer ignoring value order

4. The following code attempts to count the number of longest increasing subsequences using DP arrays. Identify the bug that causes incorrect counting of LIS.

medium

A. counts array is initialized with zeros instead of ones

B. lengths array should be initialized with zeros instead of ones

C. The condition nums[j] < nums[i] should be nums[j] <= nums[i]

D. The final sum should be over counts where lengths are less than max_len

Solution

1. Step 1: Check initialization of counts array

   Counts represent number of LIS ending at each index; initially each element alone forms LIS of length 1, so counts[i] must start at 1, not 0.

2. Step 2: Consequence of zero initialization

   With counts initialized to 0, counts[i] remains 0 unless updated, causing undercounting of LIS and incorrect final result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initialize counts with 1 to count single-element subsequences [OK]

Hint: Counts must start at 1 to count single elements [OK]

Common Mistakes:

• Initializing counts with zeros
• Using <= instead of <
• Summing counts incorrectly

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