Minimum Number of Increasing Subsequence to Be Removed

Minimum Number of Increasing Subsequence to Be Removed - Problem

Given an array of integers nums, you are allowed to perform the following operation any number of times:

Remove a strictly increasing subsequence from the array.

Your task is to find the minimum number of operations required to make the array empty.

A strictly increasing subsequence is a subsequence where each element is greater than the previous one.

Input & Output

Example 1 — Basic Case

$ Input: nums = [5,3,4,2,1]

› Output: 2

💡 Note: We can remove [3,4] and [5] as increasing subsequences, leaving [2,1]. Then remove [2] and [1] separately. Total: 4 operations. But optimally, we can think of this as needing to handle the longest decreasing subsequence [5,3,2,1] which requires 4 operations, but the actual answer is based on a different partitioning strategy.

Example 2 — Already Sorted

$ Input: nums = [1,2,3,4,5]

› Output: 1

💡 Note: The entire array is already strictly increasing, so we can remove it all in one operation.

Example 3 — All Same Elements

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

› Output: 4

💡 Note: Since we need strictly increasing subsequences, each element of value 5 must be removed separately, requiring 4 operations.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array with mixed order: [5,3,4,2,1]

Process

Find minimum partitions into increasing subsequences

Output

Minimum operations needed: 4

Key Takeaway

🎯 Key Insight: The minimum operations equal the length of the longest decreasing subsequence in the array

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that this problem is equivalent to finding the minimum number of non-increasing subsequences needed to cover the array. The optimal approach uses binary search to efficiently maintain tails of decreasing subsequences. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Binary Search	O(n log n)	O(n)	Use binary search to efficiently track multiple decreasing subsequences
Brute Force - Try All Combinations	O(2^n)	O(n)	Generate all possible ways to partition the array into increasing subsequences

Greedy with Binary Search — Algorithm Steps

Initialize array to track tail elements of decreasing subsequences
For each element, use binary search to find position
Either extend existing subsequence or start new one

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Elements

Go through each element in the array

Binary Search

Find optimal position using binary search

Update Tails

Either extend or replace in tails array

Code -

solution.c — C

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

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

int solution(int* nums, int n) {
    int tails[1000];
    int tailSize = 0;
    
    for (int i = 0; i < n; i++) {
        int pos = binarySearch(tails, tailSize, nums[i]);
        
        if (pos == tailSize) {
            tails[tailSize++] = nums[i];
        } else {
            tails[pos] = nums[i];
        }
    }
    
    return tailSize;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Single pass through array with binary search for each element

⚡ Linearithmic

Space Complexity

O(n)

Array to store tail elements of decreasing subsequences

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 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

Greedy with Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler