300. Longest Increasing Subsequence

Description

Difficulty: Medium

Given an integer array nums, return the length of the longest strictly increasing subsequence.

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

Constraints:

• 1 <= nums.length <= 2500
• -10⁴ <= nums[i] <= 10⁴

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solution

1. Dynamic Programming

The idea is Dynamic Programming (DP), specifically a bottom-up tabulation approach. The fundamental principle here is to break down the complex problem of finding the LIS into smaller, overlapping subproblems and then build up the solution from these subproblems.

1. Subproblem Definition: dp[i] is defined as the length of the Longest Increasing Subsequence that ends with nums[i]. This is a crucial definition, as it allows us to build upon previous calculations.

2. Base Case / Initialization: Each number nums[i] by itself forms an increasing subsequence of length 1. Therefore, dp[i] for all i is initially set to 1. This provides the base values from which longer subsequences can be constructed.

3. Building Up (State Transition): For each nums[i] (iterating from left to right):

   • We look at all preceding numbers nums[j] (where j < i).

   • If nums[j] < nums[i], it means nums[i] can be appended to an increasing subsequence ending at nums[j].

   • In this case, a potential length for the LIS ending at nums[i] would be dp[j] + 1 (the length of the LIS ending at nums[j] plus nums[i] itself).

   • We take the maximum of all such dp[j] + 1 values and dp[i]'s current value (which is at least 1) to update dp[i]. This ensures dp[i] always stores the maximum possible LIS ending at nums[i].

4. Overall Result: As we compute each dp[i], we keep track of the max value encountered in the entire dp array. This max variable ultimately holds the length of the longest increasing subsequence found anywhere in the nums array, because the LIS must end at some nums[i].

2. Binary Search

Binary Search's Role in O(NlogN) LIS In the O(NlogN) solution for the Longest Increasing Subsequence problem, binary search isn't used to find the LIS itself, nor is it looking for a specific number in the input array. Instead, it's used to efficiently maintain and update a special auxiliary array, often called tails (or dp).

Here's the core idea:

1. The tails Array: We maintain an array tails where tails[i] stores the smallest tail (last element) among all increasing subsequences of length i+1. This tails array itself will always be sorted in increasing order.
2. Iterating Through nums: For each num in the input array nums:
   • Binary Search for Placement: We perform a binary search on the tails array to find the first element that is greater than or equal to num.
   • Two Scenarios:
     • If num is greater than all elements in tails: This means num can extend the longest increasing subsequence we've found so far. We append num to the tails array, effectively increasing the length of our LIS.
     • If num is less than or equal to an element in tails (at index i): This means num can form an increasing subsequence of length i+1 with a smaller ending element than tails[i] currently holds. We replace tails[i] with num. Why is this beneficial? Because a smaller ending element for a subsequence of the same length creates more opportunities for subsequent numbers to form even longer increasing subsequences. It's like saying, "I can achieve this length, but now I'm doing it with a better (smaller) last number."
3. The Result: The final length of the tails array (or the counter we use to track its size) will be the length of the Longest Increasing Subsequence.

In essence, the binary search efficiently helps us to either extend our current "best" LIS or optimize an existing one by finding a smaller tail for a given length. This allows us to process each number in O(logN) time, leading to the overall O(NlogN) complexity.

Code

1. Dynamic Programming

import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
		if (nums == null || nums.length == 0) {
            return 0;
        }
				
        int[] dp = new int[2501];
		Arrays.fill(dp, 1);
				
        int max = 1;

        for (int i = 0; i < nums.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }

        return max;
    }
}

Time Complexity: O(N²)

• The code involves two nested loops. The outer loop iterates N times (for i from 0 to nums.length - 1). The inner loop iterates up to i times (for j from 0 to i - 1).

• Inside the loops, operations like comparison and Math.max are constant time.

• Therefore, the total number of operations is proportional to N * N.

Space Complexity: O(N)

• An array dp of size nums.length (or 2501 which effectively scales with the maximum N) is used to store the intermediate results. This space requirement grows linearly with the input size.

2. Binary Search

import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int len = 0;

        for (int num : nums) {
            int i = Arrays.binarySearch(tails, 0, len, num);

            if (i < 0) {
                i = -(i + 1);
            }

            tails[i] = num;

            if (i == len) {
                len++;
            }
        }

        return len;
    }
}

Time Complexity: O(NlogN)

Space Complexity: O(N)