Make Array Non-decreasing

Med

#3134Time: O(N^2), where N is the length of `nums`. There are two nested loops. The outer loop runs N times for `i`, and the inner loop runs up to `i+1` times for `j`. The work inside the inner loop is constant time because we maintain the running maximum.Space: O(N) to store the DP table of size N, where each entry holds a pair of integers.

Patterns

Greedy

Data structures

Array Stack Monotonic Stack

Prompt

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⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to build the solution iteratively. We define a DP state dp[i] that stores information about the optimal partition for the prefix nums[0...i]. Specifically, dp[i] will store a pair (size, last_val), representing the maximum size of a valid non-decreasing array and the minimum possible value of the last element for that maximum size.

Algorithm

Initialize a DP array dp of size N, where dp[i] will store a pair {max_size, min_last_element_value} for the prefix nums[0...i].
Set a base case for i=0: dp[0] = {1, nums[0]}.
Iterate i from 1 to N-1 to compute dp[i].
Inside this loop, initialize bestSize to 0 and minLastVal to infinity for the current i.
Start a nested loop, iterating j from i down to 0. This j represents the start of the last segment nums[j...i].
In the inner loop, maintain currentMax, the maximum value in nums[j...i].
Get the result for the prefix nums[0...j-1]. If j=0, the previous size is 0 and the previous last value is negative infinity. Otherwise, they are dp[j-1][0] and dp[j-1][1].
If the previous last value is less than or equal to currentMax, we have a valid partition. The new size is prevSize + 1.
Update bestSize and minLastVal for dp[i] if this new partition is better (larger size, or same size with smaller last value).
After the inner loop finishes, store the final bestSize and minLastVal in dp[i].
The final answer is the size component of dp[N-1].

Walkthrough

The core idea is to build the solution for nums[0...i] based on the solutions for smaller prefixes nums[0...j-1]. When we consider nums[0...i], the last element of our resulting non-decreasing array must be the maximum of some subarray nums[j...i]. Let this maximum be M. For the resulting array to be non-decreasing, the element before M must be less than or equal to M. This previous element is the last element of an optimal partition for the prefix nums[0...j-1].

This leads to the DP state dp[i] = (s_i, v_i), where s_i is the maximum possible size of the non-decreasing array for the prefix nums[0...i], and v_i is the minimum possible value of the last element among all partitions that achieve this maximum size. Minimizing the last element is a greedy choice that helps in extending the sequence later, as a smaller last element allows more options for the next element.

To compute dp[i], we iterate through all possible split points j (from i down to 0), considering nums[j...i] as the last group. We calculate its maximum m = max(nums[j...i]). We then check if m is greater than or equal to the last value of the optimal partition for nums[0...j-1]. If it is, we have found a candidate partition for nums[0...i]. We do this for all j and pick the one that maximizes the partition size, breaking ties by choosing the one with the minimum last element value.

1class Solution {2    public int makeArrayNonDecreasing(int[] nums) {3        int n = nums.length;4        if (n == 0) {5            return 0;6        }7 8        // dp[i] stores a pair: {max_size, min_last_element_value} for prefix nums[0...i]9        int[][] dp = new int[n][2];10 11        // Base case: i = 012        dp[0][0] = 1;13        dp[0][1] = nums[0];14 15        for (int i = 1; i < n; i++) {16            int bestSize = 0;17            int minLastVal = Integer.MAX_VALUE;18 19            int currentMax = 0;20            // Iterate backwards for the last segment nums[j...i]21            for (int j = i; j >= 0; j--) {22                currentMax = Math.max(currentMax, nums[j]);23                24                int prevSize = (j == 0) ? 0 : dp[j - 1][0];25                int prevLastVal = (j == 0) ? Integer.MIN_VALUE : dp[j - 1][1];26 27                if (prevLastVal <= currentMax) {28                    int currentSize = prevSize + 1;29                    if (currentSize > bestSize) {30                        bestSize = currentSize;31                        minLastVal = currentMax;32                    } else if (currentSize == bestSize) {33                        minLastVal = Math.min(minLastVal, currentMax);34                    }35                }36            }37            dp[i][0] = bestSize;38            dp[i][1] = minLastVal;39        }40 41        return dp[n - 1][0];42    }43}

Complexity

Time

O(N^2), where N is the length of `nums`. There are two nested loops. The outer loop runs N times for `i`, and the inner loop runs up to `i+1` times for `j`. The work inside the inner loop is constant time because we maintain the running maximum.

Space

O(N) to store the DP table of size N, where each entry holds a pair of integers.

Trade-offs

Pros

It is a systematic approach that correctly explores the problem space to find the optimal solution.
It serves as a good foundation for understanding the problem before moving to more optimized solutions.

Cons

The O(N^2) time complexity is too slow for the given constraints (N up to 2 * 10^5) and will likely result in a Time Limit Exceeded (TLE) error on most platforms.

A more efficient approach is to process the array from left to right and maintain a temporary result array that is always non-decreasing. This can be achieved using a structure that behaves like a monotonic stack. When a new number is introduced that violates the non-decreasing property, we greedily merge it with the previous element(s) by taking their maximum until the property is restored.

Algorithm

Initialize an empty list or stack, let's call it res, to store the elements of the resulting non-decreasing array.
Iterate through each number num in the input array nums.
For each num, add it to the end of res.
After adding num, check if res has at least two elements and if the last element is smaller than the second to last element (res.get(res.size() - 1) < res.get(res.size() - 2)).
If the condition is true, it means the non-decreasing property is violated. To fix this, merge the last two groups: remove the last two elements from res and add their maximum back to res.
Repeat the check and merge step in a while loop until the non-decreasing property is restored for res.
After iterating through all numbers in nums, the size of res is the maximum possible size of the non-decreasing array.

Walkthrough

This approach is based on a greedy strategy. We process the input array nums one element at a time and build the final non-decreasing array, let's call it res. We can use a list or a stack to represent res.

For each num from nums, we first add it to res. This corresponds to creating a new group [num]. However, this might break the non-decreasing property of res.

If res has more than one element and its last element is smaller than the one before it (res.back() < res[res.size()-2]), we must perform a merge operation. The two groups corresponding to the last two elements of res must be merged into a single group. The value of this new group is the maximum of the two merged values. So, we pop the last two elements from res and push their maximum back.

This merge operation might create a new violation (the new maximum might be smaller than the element before it). Therefore, we need to repeat this merging process in a loop until res is non-decreasing again. This behavior is characteristic of a monotonic stack (in this case, a non-decreasing one).

Let's trace nums = [4, 2, 5, 3, 5]:

res = []
Process 4: res.add(4). res is [4].
Process 2: res.add(2). res is [4, 2]. 2 < 4, so merge. Pop 2, pop 4, add max(4, 2) = 4. res is [4].
Process 5: res.add(5). res is [4, 5]. 5 >= 4, ok.
Process 3: res.add(3). res is [4, 5, 3]. 3 < 5, so merge. Pop 3, pop 5, add max(5, 3) = 5. res is [4, 5]. 5 >= 4, ok.
Process 5: res.add(5). res is [4, 5, 5]. 5 >= 5, ok.

The final size is res.size(), which is 3.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int makeArrayNonDecreasing(int[] nums) {6        List<Integer> res = new ArrayList<>();7        for (int num : nums) {8            res.add(num);9            while (res.size() > 1 && res.get(res.size() - 1) < res.get(res.size() - 2)) {10                int last = res.remove(res.size() - 1);11                int secondLast = res.remove(res.size() - 1);12                res.add(Math.max(last, secondLast));13            }14        }15        return res.size();16    }17}

Complexity

Time

O(N), where N is the length of `nums`. Each number is added to the list once. The `while` loop performs remove operations. Since each element can be removed at most once over the entire execution, the total number of operations in the `while` loop is O(N). Thus, the amortized time complexity for processing each number is O(1).

Space

O(N) in the worst case for the `res` list. This happens when the input array is already non-decreasing, and `res` will store all its elements.

Trade-offs

Pros

Highly efficient with a linear time complexity, which is optimal.
The logic is relatively simple to implement using a list or a stack.
Passes for large constraints where O(N^2) solutions fail.

Cons

The greedy logic might not be immediately obvious to prove its correctness without careful reasoning.

Solutions

Solution

1class Solution {2public3  int maximumPossibleSize(int[] nums) {4    int ans = 0, mx = 0;5    for (int x : nums) {6      if (mx <= x) {7        ++ans;8        mx = x;9      }10    }11    return ans;12  }13}

1class Solution {2public:3  int maximumPossibleSize(vector<int> &nums) {4    int ans = 0, mx = 0;5    for (int x : nums) {6      if (mx <= x) {7        ++ans;8        mx = x;9      }10    }11    return ans;12  }13};

1class Solution:2    def maximumPossibleSize(self, nums: List[int]) -> int: ans = mx = 0 for x in nums: if mx <= x: ans += 1 mx = x return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem