Longest Increasing Subsequence medium

Problem Statement

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

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 Explanation: The longest increasing subsequence is [0,1,2,3], therefore the length is 4.

Steps

1. Initialization: Create a tails array to store the smallest tail of all increasing subsequences with length i+1 in tails[i]. Initialize tails[0] = nums[0] and length (the length of the longest increasing subsequence) to 1.

2. Iteration: Iterate through the nums array starting from the second element. For each element num:

   • If num is greater than the last element of tails (tails[length - 1]), it extends the longest increasing subsequence. Append num to tails and increment length.
   • Otherwise, find the smallest tail in tails that is greater than or equal to num using binary search. Replace that tail with num. This ensures we maintain the smallest tails for all subsequence lengths.

3. Return: After iterating through all elements in nums, length will hold the length of the longest increasing subsequence.

Explanation

The algorithm uses a dynamic programming approach combined with binary search for efficiency. tails array cleverly stores only the smallest tail of all increasing subsequences of a given length. This optimization prevents us from needing to store the entire subsequence at each step, significantly reducing space complexity. When a new number is encountered, it either extends the longest subsequence or it replaces a larger tail element to potentially create a new better subsequence of the same length. The binary search efficiently finds the correct position for replacement, maintaining the sorted property of the tails array and ensuring the smallest tail for each length.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int LengthOfLIS(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }

        int[] tails = new int[nums.Length];
        tails[0] = nums[0];
        int length = 1;

        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] > tails[length - 1]) {
                tails[length++] = nums[i];
            } else {
                int index = BinarySearch(tails, 0, length - 1, nums[i]);
                tails[index] = nums[i];
            }
        }

        return length;
    }

    private int BinarySearch(int[] arr, int low, int high, int target) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
}

Complexity

• Time Complexity: O(N log N), where N is the length of the input array. This is dominated by the binary search in each iteration.
• Space Complexity: O(N) in the worst case, to store the tails array. In the best case, it could be O(1) if the input array is already sorted decreasingly.