Longest Increasing Subsequence - Practice Coding Problems

Longest Increasing Subsequence - Problem

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].

Input & Output

Example 1 — Basic Case

$ Input: nums = [10,9,2,5,3,7,101,18]

› Output: 4

💡 Note: The longest increasing subsequence is [2,3,7,101] or [2,3,7,18] or [2,5,7,101] or [2,5,7,18], all with length 4.

Example 2 — All Decreasing

$ Input: nums = [0,1,0,3,2,3]

› Output: 4

💡 Note: The longest increasing subsequence is [0,1,2,3] with length 4.

Example 3 — All Same Elements

$ Input: nums = [7,7,7,7,7,7,7]

› Output: 1

💡 Note: Since all elements are the same, the longest strictly increasing subsequence has length 1.

Constraints

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array with elements in any order

Process

Find longest subsequence where each element is strictly greater than the previous

Output

Return the length of the longest increasing subsequence

Key Takeaway

🎯 Key Insight: Use binary search to maintain smallest tails for optimal O(n log n) solution

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to use dynamic programming or binary search to efficiently track the longest increasing subsequence. The optimal binary search approach maintains an array of smallest tail elements for each subsequence length. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimization	O(n log n)	O(n)	Use binary search to maintain array of smallest tail elements for each subsequence length
Dynamic Programming	O(n²)	O(n)	Build up solution using 1D DP array to track longest sequence ending at each position
Brute Force - Try All Subsequences	O(2ⁿ)	O(n)	Generate all possible subsequences and find the longest increasing one

Binary Search Optimization — Algorithm Steps

Initialize empty tails array
For each element in nums, find its position in tails using binary search
If position equals tails length, append element (extending longest subsequence)
Otherwise, replace tails[position] with current element (optimizing for future extensions)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with empty tails array

Process

For each element, binary search position in tails array

Update

Either extend tails or replace element to keep optimal state

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int binarySearch(int* tails, int tailsSize, int target) {
    int left = 0, right = tailsSize;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (tails[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int solution(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    int* tails = malloc(numsSize * sizeof(int));
    int tailsSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        // Binary search for the position to place num
        int pos = binarySearch(tails, tailsSize, num);
        
        if (pos == tailsSize) {
            // num is larger than all elements in tails, extend the longest subsequence
            tails[tailsSize++] = num;
        } else {
            // Replace tails[pos] with num to optimize for future extensions
            tails[pos] = num;
        }
    }
    
    int result = tailsSize;
    free(tails);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    if (strncmp(line, "[]", 2) == 0) {
        printf("0\n");
        return 0;
    }
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

For each of n elements, we do binary search on tails array of length up to n

⚡ Linearithmic

Space Complexity

O(n)

Tails array can grow up to size n in worst case

⚡ Linearithmic Space

87.5K Views

High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler