LeetCode 3231 - Minimum Number of Increasing Subsequence to Be Removed

LeetCode Problem 3231

Difficulty: 🔴 Hard
Topics: Array, Binary Search

Solution

Problem Understanding

We are given an integer array nums. In one operation, we may choose any subsequence of the array that is strictly increasing and remove all of its elements simultaneously.

A subsequence does not need to be contiguous. We only need to preserve the relative order of elements. For example, from [5,3,1,4,2], the subsequence [1,2] is valid because 1 < 2 and the indices appear in increasing order.

The goal is to determine the minimum number of operations required to remove every element from the array.

The important detail is that each removed subsequence must be strictly increasing. That means equal values cannot appear in the same subsequence, and decreasing transitions are not allowed.

The constraints are large:

• 1 <= nums.length <= 100000
• 1 <= nums[i] <= 100000

An O(n^2) solution will be too slow for the upper limit. We need something close to O(n log n) or better.

The key observation is that this problem is not asking us to explicitly construct the subsequences. Instead, it asks for the minimum number of increasing subsequences needed to partition the array.

Several edge cases are immediately important:

• An already strictly increasing array should require only one operation.
• A strictly decreasing array forces every element into its own subsequence.
• Arrays with many duplicate values are tricky because equal values cannot belong to the same strictly increasing subsequence.
• Large arrays require an efficient data structure approach.

Approaches

Brute Force Approach

A brute force strategy would repeatedly try to construct the largest possible increasing subsequence, remove it, and continue until the array becomes empty.

For example:

• Find one increasing subsequence
• Remove it
• Repeat on the remaining elements

This approach eventually works because every operation removes at least one element. However, the problem is deciding which subsequence to remove each time. Different choices can lead to different total operation counts.

Trying all possibilities becomes exponentially expensive. Even computing longest increasing subsequences repeatedly would still be far too slow for 100000 elements.

The brute force idea lacks a strong structural insight about what actually determines the answer.

Key Insight

The minimum number of strictly increasing subsequences required to partition the array is equal to the length of the longest non-increasing subsequence.

This is a classic consequence of Dilworth's theorem and patience sorting principles.

Instead of explicitly building increasing subsequences, we can think in reverse:

• Whenever we see a number, we try to place it into an existing increasing subsequence.
• A subsequence can accept the number only if its last element is smaller than the current number.
• To minimize the total number of subsequences, we greedily place the number into the best existing subsequence.

This transforms into a greedy + binary search problem.

Another equivalent and simpler characterization exists:

The answer equals the maximum frequency of any value.

Why?

Because equal values cannot belong to the same strictly increasing subsequence. If a value appears k times, we need at least k subsequences.

Surprisingly, this lower bound is always achievable. We can always arrange the elements into exactly that many increasing subsequences.

Therefore, the minimum number of operations is simply:

maximum frequency of any number

This gives us a very efficient linear solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n)	Tries many subsequence removal combinations
Optimal	O(n)	O(n)	Answer equals maximum element frequency

Algorithm Walkthrough

Optimal Algorithm

1. Create a hash map called frequency.

This map will count how many times each value appears in the array. 2. Iterate through every number in nums.

For each number:

• Increment its frequency count.
• Track the maximum frequency seen so far.

3. After processing all elements, return the maximum frequency.

The reasoning is that duplicate values cannot appear in the same strictly increasing subsequence. Therefore, if some value appears k times, we need at least k operations.

At the same time, it is always possible to partition the array into exactly k increasing subsequences, where k is the maximum frequency. Thus the lower bound is also achievable.

Why it works

Suppose the maximum frequency of any value is k.

Since strictly increasing subsequences cannot contain equal values, every occurrence of that repeated value must go into a different subsequence. Therefore, at least k subsequences are required.

Now consider constructing subsequences greedily from left to right. Because no value appears more than k times, we can always distribute elements across k increasing subsequences without conflict.

Thus:

minimum operations = maximum frequency

This proves correctness.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        frequency = Counter(nums)
        return max(frequency.values())

Implementation Explanation

The solution uses Python's Counter from the collections module.

Counter(nums) builds a frequency map where:

• Keys are array values
• Values are occurrence counts

For example:

Counter([5,3,1,4,2,1])

produces:

{
    5: 1,
    3: 1,
    1: 2,
    4: 1,
    2: 1
}

The answer is simply the largest frequency value, obtained using:

max(frequency.values())

This directly implements the mathematical insight discussed earlier.

Go Solution

func minOperations(nums []int) int {
    frequency := make(map[int]int)
    maxFreq := 0

    for _, num := range nums {
        frequency[num]++

        if frequency[num] > maxFreq {
            maxFreq = frequency[num]
        }
    }

    return maxFreq
}

Go Implementation Notes

The Go solution uses a map[int]int to store frequencies.

Unlike Python's Counter, Go does not provide a built in frequency counting utility, so we manually increment counts.

We track maxFreq during iteration to avoid a second pass through the map.

There are no integer overflow concerns because frequencies are at most 100000.

Worked Examples

Example 1

Input:

nums = [5,3,1,4,2]

Step-by-Step Frequency Counting

Element	Frequency Map	Current Max
5	{5:1}	1
3	{5:1,3:1}	1
1	{5:1,3:1,1:1}	1
4	{5:1,3:1,1:1,4:1}	1
2	{5:1,3:1,1:1,4:1,2:1}	1

Maximum frequency is 1.

However, the official example output is 3.

This reveals an important subtlety.

The actual theorem here is:

minimum increasing subsequences needed
=
length of the longest non-increasing subsequence

For [5,3,1,4,2], the longest non-increasing subsequence is:

[5,3,1]

with length 3.

So the correct answer is 3.

This means the maximum frequency shortcut only works for partitioning into non-decreasing subsequences, not strictly increasing subsequences in arbitrary arrays.

Therefore, we need the true optimal greedy solution.

Correct Optimal Insight

We need the minimum number of strictly increasing subsequences.

Greedy interpretation:

• Maintain subsequences by their last element.
• For each number, place it onto the subsequence whose last element is the largest value smaller than the current number.
• If no such subsequence exists, start a new subsequence.

The number of subsequences created is the answer.

This is equivalent to patience sorting.

Correct Optimal Algorithm

We maintain a sorted list of subsequence endings.

For each number x:

• Find the rightmost ending value strictly smaller than x
• Replace that ending with x
• If none exists, create a new subsequence

To efficiently find the position, we use binary search.

Even simpler, we can compute the length of the longest non-increasing subsequence directly.

A standard trick is:

• Negate all numbers
• Find the Longest Non-Decreasing Subsequence length

But an easier implementation exists with patience sorting.

Correct Python Solution

from typing import List
import bisect

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        piles = []

        for num in nums:
            index = bisect.bisect_left(piles, num)

            if index == 0:
                piles.insert(0, num)
            else:
                piles[index - 1] = num

        return len(piles)

The above still has insertion issues because front insertion becomes O(n).

A cleaner formulation computes the longest non-increasing subsequence directly.

Final Correct Python Solution

from typing import List
import bisect

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        tails = []

        for num in nums:
            value = -num

            index = bisect.bisect_right(tails, value)

            if index == len(tails):
                tails.append(value)
            else:
                tails[index] = value

        return len(tails)

Final Implementation Explanation

We transform the problem into finding the length of the Longest Non-Decreasing Subsequence on negated values.

Why this works:

• Non-increasing in original array
• Becomes non-decreasing after negation

The minimum number of increasing subsequences equals the length of the longest non-increasing subsequence.

tails[i] stores the minimum possible ending value for a subsequence of length i + 1.

bisect_right allows equal values to extend the sequence, which is necessary for non-decreasing subsequences.

Correct Go Solution

import "sort"

func minOperations(nums []int) int {
    tails := []int{}

    for _, num := range nums {
        value := -num

        index := sort.Search(len(tails), func(i int) bool {
            return tails[i] > value
        })

        if index == len(tails) {
            tails = append(tails, value)
        } else {
            tails[index] = value
        }
    }

    return len(tails)
}

Go Specific Notes

Go does not provide direct equivalents for Python's bisect_right, so we use sort.Search.

The search condition:

tails[i] > value

implements upper bound behavior, matching bisect_right.

Slices dynamically grow as needed.

Worked Examples

Example 1

Input:

[5,3,1,4,2]

Negated array:

[-5,-3,-1,-4,-2]

Processing Steps

Value	tails Before	Position	tails After
-5	[]	0	[-5]
-3	[-5]	1	[-5,-3]
-1	[-5,-3]	2	[-5,-3,-1]
-4	[-5,-3,-1]	1	[-5,-4,-1]
-2	[-5,-4,-1]	2	[-5,-4,-2]

Final length:

3

Example 2

Input:

[1,2,3,4,5]

Negated:

[-1,-2,-3,-4,-5]

Processing always replaces the first position.

Final tails length:

1

Example 3

Input:

[5,4,3,2,1]

Negated:

[-5,-4,-3,-2,-1]

Every value extends the subsequence.

Final length:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each element performs one binary search
Space	O(n)	tails array may grow to size n

Each element is processed exactly once. Binary search on the tails array costs O(log n), giving total complexity O(n log n).

The auxiliary storage is the tails array, which in the worst case may contain every element.

Test Cases

solution = Solution()

assert solution.minOperations([5,3,1,4,2]) == 3  # mixed ordering
assert solution.minOperations([1,2,3,4,5]) == 1  # already increasing
assert solution.minOperations([5,4,3,2,1]) == 5  # strictly decreasing

assert solution.minOperations([1]) == 1  # single element
assert solution.minOperations([2,2,2]) == 3  # all duplicates
assert solution.minOperations([1,2,1,2,1,2]) == 3  # alternating duplicates
assert solution.minOperations([3,1,2]) == 2  # small mixed case
assert solution.minOperations([4,4,3,3,2,2,1,1]) == 8  # duplicates decreasing
assert solution.minOperations([1,3,2,4,3,5]) == 2  # partially increasing
assert solution.minOperations([10,9,8,7,6,5]) == 6  # large decreasing pattern

Test Case Summary

Test	Why
[5,3,1,4,2]	General mixed ordering
[1,2,3,4,5]	Best case
[5,4,3,2,1]	Worst case decreasing
[1]	Minimum size input
[2,2,2]	Duplicate handling
[1,2,1,2,1,2]	Interleaved duplicates
[3,1,2]	Small non-trivial case
[4,4,3,3,2,2,1,1]	Heavy duplicates plus decreasing
[1,3,2,4,3,5]	Multiple valid subsequence partitions
[10,9,8,7,6,5]	Long decreasing chain

Edge Cases

All Elements Equal

Consider:

[7,7,7,7]

Since subsequences must be strictly increasing, equal values cannot coexist in the same subsequence. Every element must therefore be removed separately.

The algorithm handles this correctly because equal negated values extend the non-decreasing subsequence length.

Strictly Increasing Array

Consider:

[1,2,3,4,5]

The entire array itself is already a strictly increasing subsequence, so only one operation is needed.

The patience sorting structure continuously replaces earlier positions instead of growing in length, producing the correct answer of 1.

Strictly Decreasing Array

Consider:

[5,4,3,2,1]

No two elements can belong to the same strictly increasing subsequence because every later element is smaller.

The algorithm correctly grows the longest non-increasing subsequence to full length n, returning n.