Make Array Non-decreasing

medium array greedy monotonic stack

Problem

You are given an integer array nums. In one operation you may pick a non-empty subarray and replace the whole subarray with a single element equal to its maximum. Return the maximum possible size of the array after zero or more operations such that the result is non-decreasing.

Because replacing a subarray with its max can only raise the value at that position, an element survives only if some kept element to its right is at least as large. So we scan from the right, keep an element whenever it is ≤ the running ceiling, and absorb it otherwise.

Inputnums = [4, 2, 5, 3, 5]

Output3

Merge [2,5]→5 then [3,5]→5 to get [4,5,5], a non-decreasing array of size 3.

nums (comma-separated, 1..200000)

def maximumPossibleSize(nums):
    cur = float('inf')          # ceiling allowed at the current right boundary
    keep = 0                    # how many original elements survive
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] <= cur:
            keep += 1           # this element fits under the ceiling, keep it
            cur = nums[i]       # it becomes the new (lower) ceiling on its left
        # else: nums[i] > cur, absorb it into the subarray on its right
    return keep

function maximumPossibleSize(nums) {
  let cur = Infinity;           // ceiling allowed at the current right boundary
  let keep = 0;                 // how many original elements survive
  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] <= cur) {
      keep++;                   // this element fits under the ceiling, keep it
      cur = nums[i];            // it becomes the new (lower) ceiling on its left
    }
    // else: nums[i] > cur, absorb it into the subarray on its right
  }
  return keep;
}

int maximumPossibleSize(int[] nums) {
    long cur = Long.MAX_VALUE;  // ceiling allowed at the current right boundary
    int keep = 0;               // how many original elements survive
    for (int i = nums.length - 1; i >= 0; i--) {
        if (nums[i] <= cur) {
            keep++;             // this element fits under the ceiling, keep it
            cur = nums[i];      // it becomes the new (lower) ceiling on its left
        }
        // else: nums[i] > cur, absorb it into the subarray on its right
    }
    return keep;
}

int maximumPossibleSize(vector<int>& nums) {
    long long cur = LLONG_MAX;  // ceiling allowed at the current right boundary
    int keep = 0;               // how many original elements survive
    for (int i = (int)nums.size() - 1; i >= 0; i--) {
        if (nums[i] <= cur) {
            keep++;             // this element fits under the ceiling, keep it
            cur = nums[i];      // it becomes the new (lower) ceiling on its left
        }
        // else: nums[i] > cur, absorb it into the subarray on its right
    }
    return keep;
}

Explanation

An operation replaces a subarray with its maximum. The maximum of a block never decreases, so the only way an element can stay is if everything kept to its right is large enough that the sequence stays non-decreasing. This points to a greedy right-to-left scan.

Scan from the last index toward the first, carrying a value cur = the largest value still allowed at the current boundary (it starts at +∞ because the rightmost element is unconstrained). When we look at nums[i]:

If nums[i] <= cur the element fits below the ceiling, so we keep it (increment keep) and tighten the ceiling to cur = nums[i] — whatever sits further left must not exceed this kept value.

If nums[i] > cur the element is too big to keep here. We absorb it: it joins the subarray on its right whose maximum is at least nums[i], so that block keeps the same max and our running ceiling is unchanged. The element simply disappears from the final array, and keep is not incremented.

The relationship to a monotonic stack: reading right-to-left, the kept values form a non-increasing chain, exactly the values a monotonic (non-increasing) stack would retain. The single variable cur stands in for the stack top.

Example [4,2,5,3,5]: keep 5 (cur=5), keep 3 (cur=3), 5>3 absorb, keep 2 (cur=2), 4>2 absorb. Three elements survive, so the answer is 3.

Time: O(n) Space: O(1)