3523. Make Array Non-decreasing

Problem Description

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. The goal is to determine the maximum possible size of the array after performing zero or more operations such that the resulting array is non-decreasing.

Intuition

To solve this problem, the key is understanding that the operations allow us to condense sections of the array where the order is non-increasing into a single element, which is the maximum in that section. Since we want the resulting array to be non-decreasing, we want to identify every point where the order can be preserved or improved.

The solution iterates through the array while keeping track of the maximum value seen so far (mx). Each time an element greater than or equal to mx is found, it means a non-decreasing subarray can continue or start, and thus, we increment our counter ans, which signifies a point where we could potentially place an element in the resulting non-decreasing array. Effectively, ans represents the maximum possible size of the resulting non-decreasing array.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution Approach

The solution approach to this problem is fairly straightforward. We employ the following strategy:

Initialize Variables: Start by setting two variables, ans and mx, to zero. The variable ans will keep track of the maximum possible size of the resulting array, while mx will track the current maximum value encountered.
Iterate Through the Array: Loop through each element x in the array nums.
Check for Non-Decreasing Sequence: For each element x, check if mx, the current maximum, is less than or equal to x. If it is, this indicates that the current element can potentially extend or begin a new non-decreasing subsequence.
Update Variables:
- Increment ans by 1, since we have the potential to add or continue a non-decreasing sequence at this point.
- Update mx to x because this becomes the new maximum threshold for forming a non-decreasing sequence moving forward.
Return the Result: Once the loop is complete, ans will contain the maximum size of the resulting non-decreasing array that can be achieved, which is returned as the final result.

The code implementation in Python can be represented as follows:

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

By iterating through the list and keeping track of the current maximum, the algorithm efficiently determines the maximum size of a non-decreasing array possible through the allowed modification operations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example using the solution approach described:

Consider the input array nums = [5, 3, 4, 6, 2, 8].

Initialize Variables: We start with ans = 0 and mx = 0.
First Element (5):
- Since mx (0) <= 5, we can potentially form a non-decreasing sequence.
- Update ans to ans + 1 = 1 and set mx to 5.
Second Element (3):
- mx (5) > 3, so 3 cannot continue the current sequence.
- Continue without updating ans and mx.
Third Element (4):
- mx (5) > 4, so no update here either.
- Continue without updating ans and mx.
Fourth Element (6):
- Since mx (5) <= 6, we can extend the sequence.
- Update ans to ans + 1 = 2 and set mx to 6.
Fifth Element (2):
- mx (6) > 2, thus 2 cannot extend the sequence.
- Continue without updating ans and mx.
Sixth Element (8):
- Since mx (6) <= 8, we can extend the sequence.
- Update ans to ans + 1 = 3 and set mx to 8.

After iterating through the array, the maximum possible size of a non-decreasing array is 3.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumPossibleSize(self, nums: List[int]) -> int:
5        # Initialize answer and maximum value seen so far
6        answer = 0
7        max_value_seen = 0
8      
9        # Iterate over each number in the list
10        for number in nums:
11            # Check if the current number is greater or equal to the maximum value seen so far
12            if max_value_seen <= number:
13                # If it is, increment the answer counter
14                answer += 1
15                # Update the maximum value seen
16                max_value_seen = number
17      
18        # Return the maximum possible size
19        return answer
20

1class Solution {
2    public int maximumPossibleSize(int[] nums) {
3        int answer = 0; // Initialize the count of potential maximum size subsequence
4        int currentMax = 0; // Initialize the variable to track the current maximum value
5
6        // Iterate over each element in the array
7        for (int num : nums) {
8            // If the current number is greater than or equal to currentMax
9            if (currentMax <= num) {
10                ++answer; // Increment the count
11                currentMax = num; // Update currentMax with the current number
12            }
13        }
14        return answer; // Return the calculated count
15    }
16}
17

1#include <vector>
2
3class Solution {
4public:
5    // Function to determine the maximum possible size of non-decreasing subsequence
6    int maximumPossibleSize(std::vector<int>& nums) {
7        int ans = 0; // Initialize answer to count the non-decreasing subsequence size
8        int currentMax = 0; // Variable to track the current maximum element in subsequence
9      
10        // Iterate through each number in the input vector
11        for (int num : nums) {
12            // If the current number is greater than or equal to the current max,
13            // it can be part of the non-decreasing subsequence
14            if (currentMax <= num) {
15                ++ans; // Increment the size of the valid subsequence
16                currentMax = num; // Update current maximum to the current number
17            }
18        }
19      
20        return ans; // Return the size of the largest non-decreasing subsequence
21    }
22};
23

1// Function to calculate the maximum possible size of a subarray where each element is greater than or equal to the previous
2function maximumPossibleSize(nums: number[]): number {
3    let [ans, mx] = [0, 0]; // Initialize answer and the current maximum value variable
4    for (const x of nums) {
5        if (mx <= x) { // Check if the current number is greater than or equal to the current maximum
6            ++ans; // Increment the size of the subarray
7            mx = x; // Update the current maximum value
8        }
9    }
10    return ans; // Return the size of the maximum possible subarray
11}
12

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of elements in the nums list. This is because the code iterates over each element of the list once.

The space complexity of the code is O(1), as it uses a constant amount of extra space regardless of the size of the input list nums.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know