11. Longest Increasing Subsequence

Description

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

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
-104 <= nums[i] <= 104

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

Approach - Binary Search

First thing is we maintain tail array which means for tail n it will hold the tail of our sequence tail in the sense the last which would be the last element in an increasing sequence
Second thing is what binary search results if it does not find the element which is {1,,3,4} for searching 2 it would give -2 so our if statement will convert it to 1
For binary search we give the range
If index matches size then it means we found a newer element to add if not then we are just replacing the tail with newer least element
This would O(nlogn) now du to binary search

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
 
        // tails[i] = smallest possible tail value of an increasing subsequence of length (i+1)
        int[] tails = new int[n];
        int size = 0; // tracks how many “slots” in tails are used
        
        for (int x : nums) {
            // binary search for the first index in tails[0..size) where tails[idx] >= x
            int idx = Arrays.binarySearch(tails, 0, size, x);
            if (idx < 0) {
                // binarySearch returns (-insertionPoint - 1) when not found
                idx = -idx - 1;
            }
            tails[idx] = x;
            if (idx == size) {
                // x is bigger than all existing tails, so it extends the LIS
                size++;
            }
        }
        
        return size;
    }
}

Approach - DP (Bottom Up)

If the loop is forward (i from 0 to length), the problem is that we would update the values of d[i] before we’ve had a chance to consider future indices (larger j values) that would help us calculate the correct LIS at each i.
For example, when i = 0 and you haven’t yet processed i = 1, 2, ..., you can’t yet know what the best subsequence starting at i = 0 could be because you haven’t looked ahead at future elements.
The reverse loop ensures that by the time you calculate d[i], you have already considered all the potential subsequences starting at later indices, allowing you to build the correct LIS
Time: O(n^2) Space: O(n)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] d = new int[nums.length];
        Arrays.fill(d,1);
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                    d[i] = Math.max(d[i], d[j] + 1);
                }
            }
        }
        return Arrays.stream(d).max().getAsInt();
    }
}

For better solution we need Binary search
Similar solution with forward loops, simplest to think is for j dp - j plus the ith element for which we are checking

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
 
        return Arrays.stream(dp).max().getAsInt();
    }
}

Approach - Memoization

Just make sure about the p being -1 which cannot be used as an index

class Solution {
    Integer[][] dp;
    public int lengthOfLIS(int[] nums) {
        dp = new Integer[nums.length+1][nums.length+1];
        return dfs(nums, 0, -1);
    }
 
    public int dfs(int[] nums, int i, int p) {
        if (i >= nums.length)
            return 0;
 
        if (p != -1 && dp[i][p] != null) //check
            return dp[i][p];
 
        int take = 0, skip = 0;
        if (p == -1 || nums[i] > nums[p])
            take = 1 + dfs(nums, i+1, i);
        
        skip = dfs(nums, i+1, p);
        if (p != -1) //check
            dp[i][p] = Math.max(take, skip);
        
        return Math.max(take, skip);
    }
}

Approach - Recursion

we have 2 options take or leave we calculate both and find the max one we use if for take because we can take only on a condition

class Solution {
    public int lengthOfLIS(int[] nums) {
        return dfs(nums, 0, -1);
    }
 
    public int dfs(int[] nums, int i, int p) {
        if (i >= nums.length)
            return 0;
 
        int take = 0, skip = 0;
        if (p == -1 || nums[i] > nums[p])
            take = 1 + dfs(nums, i+1, i);
        
        skip = dfs(nums, i+1, p);
        
        return Math.max(take, skip);
    }
}

Primary Approach: Binary Search / Patience Sorting ( $O (N lo g N)$ Time, $O (N)$ Space)

Intuition

To maximize the length of an increasing subsequence, we want the ending elements of our active subsequences to be as small as possible.

Maintain an array tails where tails[i] stores the smallest tail among all increasing subsequences of length i + 1.
Iterate through each element num in nums:
- Use Binary Search (Arrays.binarySearch or manual binary search) to locate the position of num in tails.
- If num is larger than all elements currently in tails, append num to the end (increasing the length of the longest subsequence found so far).
- Otherwise, replace the smallest element in tails that is $\geq num$ with num.
The size of tails at the end gives the length of the Longest Increasing Subsequence.

import java.util.Arrays;
 
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int len = 0;
 
        for (int num : nums) {
            // Binary search for num in tails[0 ... len - 1]
            int idx = Arrays.binarySearch(tails, 0, len, num);
 
            // If num is not found, binarySearch returns (-(insertion point) - 1)
            if (idx < 0) {
                idx = -(idx + 1);
            }
 
            tails[idx] = num;
 
            // If num was placed at the end, expand the active LIS length
            if (idx == len) {
                len++;
            }
        }
 
        return len;
    }
}

Complexity

Time Complexity: $O (N lo g N)$ — Performing binary search ( $O (lo g N)$ ) for each of the $N$ elements.
Space Complexity: $O (N)$ — Extra space used by the tails array.

Alternative Approach: Dynamic Programming ( $O (N^{2})$ Time, $O (N)$ Space)

Intuition

Define dp[i] as the length of the longest increasing subsequence that **ends at index i**:

Initialize dp[i] = 1 for all indices because every element alone forms a valid subsequence of length 1.
For each element at index i, iterate through all prior elements $j$ ( $0 \leq j < i$ ):
- If nums[j] < nums[i], we can extend the increasing subsequence ending at $j$ by adding nums[i]: dp[i] = max(dp[i], dp[j] + 1).
Track the maximum value in dp throughout the iteration.

import java.util.Arrays;
 
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
 
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
 
        return maxLen;
    }
}

Complexity

Time Complexity: $O (N^{2})$ — Nested loop comparing each pair $(i, j)$ where $j < i$ .
Space Complexity: $O (N)$ — Array dp of size $N$ .

Key Interview Discussion Points

tails Array Myth: Emphasize to the interviewer that the final values in the tails array do not necessarily represent the actual elements of the LIS itself—it only tracks the minimal possible tail values to determine the maximum achievable length.
Strictly Increasing Condition: For strictly increasing, use binary search to locate the first element $\geq num$ . If the problem changed to non-decreasing (allowing duplicates), you would search for the first element strictly $> num$ .

Easy Memory Rule

“DP gives $O (N^{2})$ $\to$ Optimize to $O (N lo g N)$ using tails array + Binary Search to maintain minimal tails!”

Obsidian Notes

Explorer

11. Longest Increasing Subsequence

Description

Approach - Binary Search

Approach - DP (Bottom Up)

Approach - Memoization

Approach - Recursion

Primary Approach: Binary Search / Patience Sorting ( $O (N lo g N)$ Time, $O (N)$ Space)

Intuition

Complexity

Alternative Approach: Dynamic Programming ( $O (N^{2})$ Time, $O (N)$ Space)

Intuition

Complexity

Key Interview Discussion Points

Easy Memory Rule

Table of Contents

Backlinks

Obsidian Notes

Explorer

11. Longest Increasing Subsequence

Description

Approach - Binary Search

Approach - DP (Bottom Up)

Approach - Memoization

Approach - Recursion

Primary Approach: Binary Search / Patience Sorting (O(NlogN) Time, O(N) Space)

Intuition

Complexity

Alternative Approach: Dynamic Programming (O(N2) Time, O(N) Space)

Intuition

Complexity

Key Interview Discussion Points

Easy Memory Rule

Table of Contents

Backlinks

Primary Approach: Binary Search / Patience Sorting ( $O (N lo g N)$ Time, $O (N)$ Space)

Alternative Approach: Dynamic Programming ( $O (N^{2})$ Time, $O (N)$ Space)