A LeetCode Daily Series — Day 62

Today’s problem is called “Longest Increasing Subsequence”

Published: at 05:24 AM

Welcome to another journey into the world of algorithmic problem-solving! Today, we’ll tackle the problem of finding the Longest Increasing Subsequence (LIS) in a given array. This classic problem has multiple approaches, from brute force to highly efficient algorithms. Let’s dive in!

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

cover image

Understanding the Problem

Given an integer array nums, our goal is to return the length of the longest strictly increasing subsequence. A subsequence is derived by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Using Efficient Approach: Dynamic Programming with Caching

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. Here, we use a DP array to store the length of the LIS ending at each index. We then iterate through the array to update this DP array based on the conditions given.

def lengthOfLIS(nums: List[int]) -> int:
    LIS = [1] * len(nums)

    for i in range(len(nums) - 1, -1, -1):
        for j in range(i + 1, len(nums)):
            if nums[i] < nums[j]:
                LIS[i] = max(LIS[i], 1 + LIS[j])

    return max(LIS)

Explanation

  1. Initialization: We initialize a list LIS of the same length as nums with all elements set to 1. Each element LIS[i] represents the length of the longest increasing subsequence ending at index i.
  2. Iterate Backwards: We iterate over the array from the end to the beginning.
  3. Nested Loop: For each i, we check all j indices greater than i. If nums[i] < nums[j], it means nums[j] can be appended to the subsequence ending at i.
  4. Update LIS: We update LIS[i] with the maximum value between its current value and 1 + LIS[j].
  5. Result: Finally, the length of the longest increasing subsequence is the maximum value in the LIS array.

Time Complexity: O(n^2), where n is the length of the input array. This is due to the nested loops.

Space Complexity: O(n), where n is the length of the input array. This is for storing the LIS array.

DP Result

Using Efficient Approach 2: Binary Search with Greedy

This approach combines Binary Search with a Greedy algorithm. The idea is to maintain a list that represents the smallest possible tail of all increasing subsequences of various lengths. We use binary search to determine the position of elements and update the list efficiently.

from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        sub = [nums[0]]

        for num in nums[1:]:
            if num > sub[-1]:
                sub.append(num)
            else:
                i = bisect_left(sub, num)
                sub[i] = num

        return len(sub)

Explanation

  1. Initialization: We start by initializing a list sub with the first element of nums. This list will store the smallest possible tail values for increasing subsequences of various lengths.
  2. Iterate Over Array: We iterate over the array starting from the second element.
  3. Comparison: If the current element num is greater than the last element in sub, we append it to sub.
  4. Binary Search: If num is not greater, we use bisect_left to find the first element in sub that is not smaller than num and replace that element with num. This ensures that sub remains sorted and maintains the smallest possible tail values.
  5. Result: The length of the sub list represents the length of the longest increasing subsequence.

Time Complexity: O(nlogn), where n is the length of the input array. This is due to the binary search operation within the loop.

Space Complexity: 𝑂(n), where n is the length of the input array. This is for storing the sub list.

binary search with greedy algo result

How bisect_left Works

The bisect_left function from Python’s bisect module is a powerful tool for binary search. It helps find the insertion point for a given element in a sorted list while maintaining the list’s order. Specifically, it returns the position where the element should be inserted to keep the list sorted, favoring the leftmost possible position in case of duplicates.

Let’s break down how bisect_left works using an example.

import bisect

# Initializing list
li = [1, 3, 4, 4, 4, 6, 7]

# Using bisect_left() to find index to insert new element
# Returns 2 (leftmost possible index)
print("Leftmost index to insert, so list remains sorted is: ", end="")
print(bisect.bisect_left(li, 4))

Output:

Leftmost index to insert, so list remains sorted is: 2

Binary Search Mechanism

bisect_left performs a binary search on the list to determine the appropriate insertion point. Here’s how it works step-by-step:

  1. Initial Range: The search range is initially the entire list, with low at index 0 and high at index 6 (the length of the list minus one).
  2. First Check: It calculates the midpoint:
  1. Second Check: It recalculates the midpoint:
  1. Third Check: It recalculates the midpoint:

At this point, low is equal to high, both pointing to index 2. This is the leftmost index where 4 can be inserted to keep the list sorted.

Conclusion

We’ve explored the problem of finding the Longest Increasing Subsequence using two efficient approaches: Dynamic Programming with caching and a combination of Binary Search with a Greedy algorithm.

Each approach has its trade-offs in terms of time and space complexity, and choosing the right approach depends on the constraints of the problem and the size of the input.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series