Python Coding challenge - Day 538| What is the output of the following Python Code?

 

Code Explanation:

1. Import Required Function

from bisect import bisect_left

bisect_left is a function from the bisect module that performs binary search to find the index where an element should be inserted in a sorted list to maintain the sort order.

It returns the leftmost position to insert the element.

2. Define the Function

def length_of_LIS(nums):

Defines a function length_of_LIS that takes a list of integers nums.

Goal: Return the length of the Longest Increasing Subsequence (not necessarily contiguous).

3. Initialize an Empty List dp

dp = []

This list will not store the actual LIS, but rather:

dp[i] holds the smallest possible tail value of an increasing subsequence of length i+1.

It helps in tracking potential LIS ends efficiently.

4. Iterate Over Each Element in nums

for x in nums:

For each element x in the input list nums, we try to place x in the right position in dp (either replace or append).

5. Insert/Replace Using bisect_left and Slice Assignment

dp[bisect_left(dp, x):bisect_left(dp, x)+1] = [x]

This is the core trick. Let's break it down:

bisect_left(dp, x):

Finds the index i where x can be inserted to maintain the increasing order.

dp[i:i+1] = [x]:

If i is within bounds, it replaces dp[i] with x (to make the subsequence end with a smaller value).

If i == len(dp), it appends x (extends the LIS).

Example:

If dp = [2, 5, 7] and x = 3:

bisect_left(dp, 3) returns 1, so dp[1:2] = [3] → now dp = [2, 3, 7].

This ensures:

The length of dp is the length of the LIS.

We always keep the smallest possible values to allow future elements more room to form longer increasing subsequences.

6. Return the Length of dp

return len(dp)

The length of dp at the end equals the length of the Longest Increasing Subsequence.

7. Call the Function and Print Result

print(length_of_LIS([10,9,2,5,3,7,101,18]))

For this input:

The longest increasing subsequence is [2, 3, 7, 101] or [2, 5, 7, 101], etc.

Length is 4.

Final Output:

4

Download Book-500 Days Python Coding Challenges with Explanation