3523. Make Array Non-decreasing LeetCode Solution

In this guide, you will get 3523. Make Array Non-decreasing LeetCode Solution with the best time and space complexity. The solution to Make Array Non-decreasing problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Make Array Non-decreasing solution in C++
4. Make Array Non-decreasing solution in Java
5. Make Array Non-decreasing solution in Python
6. Additional Resources

Problem Statement of Make Array Non-decreasing

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 * 105
1 <= nums[i] <= 2 * 105

Complexity Analysis

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

3523. Make Array Non-decreasing LeetCode Solution in C++

class Solution {
 public:
  int maximumPossibleSize(vector<int>& nums) {
    int ans = 0;
    int prev = 0;

    for (const int num : nums)
      if (num >= prev) {
        prev = num;
        ++ans;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

3523. Make Array Non-decreasing LeetCode Solution in Java

class Solution {
  public int maximumPossibleSize(int[] nums) {
    int ans = 0;
    int prev = 0;

    for (final int num : nums)
      if (num >= prev) {
        prev = num;
        ++ans;
      }

    return ans;
  }
}
// code provided by PROGIEZ

3523. Make Array Non-decreasing LeetCode Solution in Python

class Solution:
  def maximumPossibleSize(self, nums: list[int]) -> int:
    ans = 0
    prev = 0

    for num in nums:
      if num >= prev:
        prev = num
        ans += 1

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.