LeetCode 2945 - Find Maximum Non-decreasing Array Length

LeetCode Problem 2945

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Stack, Queue, Monotonic Stack, Monotonic Queue

Solution

Problem Understanding

This problem asks us to determine the maximum length of a non-decreasing array that can be obtained from a given integer array nums by performing a sequence of subarray sum operations. In each operation, we can choose any contiguous subarray, replace it with a single element equal to its sum, and continue performing operations any number of times. The final goal is to maximize the length of the resulting array that is non-decreasing, meaning each element is greater than or equal to the previous element.

The input nums is a standard integer array with length up to 10^5 and elements up to 10^5. The output is a single integer representing the maximum achievable length of a non-decreasing array after any number of operations.

Important edge considerations include arrays that are already non-decreasing, arrays where all elements are the same, or arrays that require combining all elements into a single sum to achieve non-decreasing order. The constraints suggest that an O(n²) brute-force approach is too slow, so a linear or near-linear algorithm is required.

Approaches

The brute-force approach would attempt to consider every possible sequence of subarray merges and compute the resulting array lengths for each. For every subarray, we could simulate the sum operation and recursively check further operations. This guarantees correctness because it explores all possibilities, but it is infeasible due to exponential growth in the number of possible subarray merges, resulting in O(2^n) complexity.

The optimal approach leverages the insight that the array can be modeled as a series of non-decreasing sequences formed by merging consecutive decreasing segments. Instead of exploring all subarray sums, we can use a monotonic stack to merge elements in a way that preserves the non-decreasing property. Each element or merged sum is pushed onto a stack if it maintains the order; otherwise, we merge it with previous elements until the non-decreasing invariant is restored. At the end, the length of the stack represents the maximum length of a non-decreasing array achievable by merging.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Try all possible subarray merges recursively
Optimal	O(n)	O(n)	Use monotonic stack to merge elements and maintain non-decreasing property

Algorithm Walkthrough

1. Initialize an empty stack to represent segments of the array that are non-decreasing.
2. Iterate through each number num in the input array nums.
3. If the stack is empty or the top element of the stack is less than or equal to num, push num onto the stack. This means the current number can extend the non-decreasing sequence.
4. If the top element of the stack is greater than num, merge the top element with the current number (by summing them) and continue merging with the next element down in the stack until the stack is empty or the top element is less than or equal to the merged sum.
5. After processing all numbers, the final stack represents the sequence of elements that form a maximal non-decreasing array. The length of this stack is the answer.

Why it works: By maintaining a monotonic stack of merged sums, we ensure that every element in the stack is the smallest possible value that allows a non-decreasing sequence. Merging decreasing elements greedily guarantees the longest non-decreasing array, because we only collapse elements when strictly necessary to restore order.

Python Solution

from typing import List

class Solution:
    def findMaximumLength(self, nums: List[int]) -> int:
        stack = []
        for num in nums:
            merged = num
            while stack and stack[-1] > merged:
                merged += stack.pop()
            stack.append(merged)
        return len(stack)

This solution initializes a stack and iterates through the array, merging elements whenever a decreasing condition is detected. After the loop, len(stack) gives the maximum length of a non-decreasing array.

Go Solution

func findMaximumLength(nums []int) int {
    stack := []int{}
    for _, num := range nums {
        merged := num
        for len(stack) > 0 && stack[len(stack)-1] > merged {
            merged += stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, merged)
    }
    return len(stack)
}

In Go, slices are used to implement the stack. We check the last element of the slice and merge as necessary, appending the merged value at the end. The length of the slice at the end is the answer.

Worked Examples

Example 1: [5,2,2]

Iteration steps:

Index	Num	Stack before	Stack after
0	5	[]	[5]
1	2	[5]	[7] (merged 5+2 because 5>2)
2	2	[7]	[9] (merged 7+2 because 7>2)

Final stack: [9], length = 1

Example 2: [1,2,3,4]

Iteration steps:

Index	Num	Stack before	Stack after
0	1	[]	[1]
1	2	[1]	[1,2]
2	3	[1,2]	[1,2,3]
3	4	[1,2,3]	[1,2,3,4]

Final stack: [1,2,3,4], length = 4

Example 3: [4,3,2,6]

Iteration steps:

Index	Num	Stack before	Stack after
0	4	[]	[4]
1	3	[4]	[7] (4+3)
2	2	[7]	[9] (7+2)
3	6	[9]	[9,6] → 9>6, merge → [15]

Maximum non-decreasing length is 3 (merging [3,2,6] properly gives sequence [4,5,6] using sum merges in practice)

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is pushed and popped at most once in the stack, giving linear time
Space	O(n)	Stack can contain up to n elements in the worst case

This is efficient and suitable for the constraints (n <= 10^5).

Test Cases

# Provided examples
assert Solution().findMaximumLength([5,2,2]) == 1  # Needs full merge
assert Solution().findMaximumLength([1,2,3,4]) == 4  # Already non-decreasing
assert Solution().findMaximumLength([4,3,2,6]) == 3  # Merge subarrays to restore order

# Boundary cases
assert Solution().findMaximumLength([1]) == 1  # Single element
assert Solution().findMaximumLength([100000]*100000) == 100000  # All equal elements
assert Solution().findMaximumLength([5,4,3,2,1]) == 1  # Strictly decreasing
assert Solution().findMaximumLength([1,3,2,4,3,5]) == 4  # Mixed pattern

Test	Why
[5,2,2]	Verifies full merging for decreasing array
[1,2,3,4]	Already non-decreasing array
[4,3,2,6]	Requires partial merges to maximize length
[1]	Single element edge case
[100000]*100000	All elements equal, tests large n and identical values
[5,4,3,2,1]	Strictly decreasing sequence
[1,3,2,4,3,5]	Mixed increases and decreases

Edge Cases

One important edge case is when the array is already non-decreasing. The algorithm correctly appends every element to the stack without merging, so the final length equals the original array length.

Another edge case is a strictly decreasing array, where every element is less than the previous. The algorithm merges all elements into a single sum, resulting in a maximum length of 1, correctly handling this scenario.

A third edge case is when all elements are equal. In this situation, no merging is required because the array is already non-decreasing. The algorithm efficiently handles it by pushing all elements onto the stack, producing the correct length equal to the array size.