We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Increasing Subsequence

Number: 300

Difficulty: Medium

Paid? No

Companies: Google, TikTok, Amazon, Meta, Microsoft, Oracle, PayPal, Walmart Labs, Splunk, Yandex, Squarepoint Capital, Flexport, Citadel, Goldman Sachs, Apple, Atlassian, Commvault, Uber, Accenture, Adobe, Intuit, IBM, Booking.com, Expedia, Samsung, Nvidia, Pure Storage

Problem Description

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

Key Insights

  • A dynamic programming solution with O(n^2) time complexity exists, but we focus on an optimized approach.
  • Using binary search and a dp array, we can achieve O(n log n) time.
  • The dp array maintains the smallest possible tail for increasing subsequences of various lengths.
  • For each number, perform binary search to decide if it can extend or replace a value in dp.

Space and Time Complexity

Time Complexity: O(n log n) where n is the length of nums
Space Complexity: O(n) for storing the dp array

Solution

We use a dynamic programming approach combined with binary search. The idea is to maintain a dp array where dp[i] holds the smallest tail value for any increasing subsequence with length i+1. For each number in the array, we perform a binary search on dp to find its correct insertion position:

  • If the number is larger than all elements, we append it, effectively extending the current longest subsequence.
  • Otherwise, we replace the first element in dp that is greater than or equal to the current number to keep the tail as small as possible. This process ensures that dp remains sorted and its length gives the length of the longest increasing subsequence.

Code Solutions

import bisect

def lengthOfLIS(nums):
    dp = []  # dp array stores smallest tail for each subsequence length
    for num in nums:
        # Find the leftmost insertion point using binary search
        idx = bisect.bisect_left(dp, num)
        if idx == len(dp):
            dp.append(num)  # Extend dp if no larger tail exists
        else:
            dp[idx] = num  # Replace to maintain the smallest tail
    return len(dp)

# Example usage:
# print(lengthOfLIS([10,9,2,5,3,7,101,18]))  # Output: 4
← Back to All Questions