Longest Increasing Subsequence LeetCode solution in Python

1
class Solution:
2
    def lengthOfLIS(self, nums: list[int]) -> int:
3

4
        # Initialize the result
5
        res = []
6

7
        # Binary search to find the index of the smallest number in result that is greater than or equal to the target
8
        def binarySearch(l, r, target):
9

10
            nonlocal res
11

12
            # If the left and right pointers meet, we have found the smallest number that is greater than the target
13
            if l == r:
14
                return l
15

16
            # Find the mid pointer
17
            m = (r - l) // 2 + l
18

19
            # If the number at the mid pointer is equal to the target, we have found a number that is equal to the target
20
            if res[m] == target:
21
                return m
22

23
            # Else if the number at the mid poitner is less than the target, we search the right side
24
            elif res[m] < target:
25
                return binarySearch(m + 1, r, target)
26

27
            # Else, we search the left side including the number at mid pointer because it is one of the possible solution since it is greater than the target
28
            else:
29
                return binarySearch(l, m, target)
30

31
        # Iterate through all numbers
32
        for n in nums:
33

34
            # If the last number in the result is less than the current number
35
            if not res or res[-1] < n:
36

37
                # Append the current number to the result
38
                res.append(n)
39

40
                continue
41

42
            # Else, find the index of the smallest number in the result that is greater than or equal to the current number
43
            i = binarySearch(0, len(res) - 1, n)
44

45
            # Replace the current number at such index
46
            res[i] = n
47

48
        return len(res)