3738. Make Array Non Decreasing¶

3738. Make Array Non-decreasing

Medium

You are given an integer array nums. In one operation, you can select a subarray and replace it with a single element equal to its maximum value.

Return the maximum possible size of the array after performing zero or more operations such that the resulting array is non-decreasing.

Example 1:

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

Output: 3

Explanation:

One way to achieve the maximum size is:

Replace subarray nums[1..2] = [2, 5] with 5 → [4, 5, 3, 5].
Replace subarray nums[2..3] = [3, 5] with 5 → [4, 5, 5].

The final array [4, 5, 5] is non-decreasing with size 3.

Example 2:

Input: nums = [1,2,3]

Output: 3

Explanation:

No operation is needed as the array [1,2,3] is already non-decreasing.

Constraints:

1 <= nums.length <= 2 * 10⁵
1 <= nums[i] <= 2 * 10⁵

Solution¶

class Solution {
    public int maximumPossibleSize(int[] nums) {
        int n = nums.length;
        if (isSorted(nums)) return n;
        int count = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            if (i == 0) set.add(nums[0]);
            else {
                int current = nums[i];
                if (set.higher(current) != null) count++;
                else {
                    set.add(nums[i]);
                }
            }
        }
        return n - count;
    }
    private boolean isSorted(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) return false;
        }
        return true;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]