Find Maximum Non-decreasing Array Length solution and explanation
Google
3 more videos on this problem
2945. Find Maximum Non-decreasing Array Length | Leetcode Biweekly 118codingMohan · 57:04 · 4K views
2945. Find Maximum Non-decreasing Array Length (Leetcode Hard)Programming Live with Larry · 3:04:02 · 1K views
【每日一题】LeetCode 2945. Find Maximum Non-decreasing Array LengthHuifeng Guan · 31:55 · 864 views
LeetCode Hard 2945 - 100% Speed & Memory! Explained! Find Maximum Non-decreasing Array LengthH William Polenz · 18:47 · 58 views
The problem
You are given a 0-indexed integer array nums.
You can perform any number of operations, where each operation involves selecting a subarray of the array and replacing it with the sum of its elements. For example, if the given array is [1,3,5,6] and you select subarray [3,5] the array will convert to [1,8,6].
Return the maximum length of a non-decreasing array that can be made after applying operations.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [5,2,2] Output: 1 Explanation: This array with length 3 is not non-decreasing. We have two ways to make the array length two. First, choosing subarray [2,2] converts the array to [5,4]. Second, choosing subarray [5,2] converts the array to [7,2]. In these two ways the array is not non-decreasing. And if we choose subarray [5,2,2] and replace it with [9] it becomes non-decreasing. So the answer is 1.
Example 2:
Input: nums = [1,2,3,4] Output: 4 Explanation: The array is non-decreasing. So the answer is 4.
Example 3:
Input: nums = [4,3,2,6] Output: 3 Explanation: Replacing [3,2] with [5] converts the given array to [4,5,6] that is non-decreasing. Because the given array is not non-decreasing, the maximum possible answer is 3.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Approach overview
Problem Overview: You are given an integer array and may repeatedly merge adjacent elements into a single value equal to their sum. The goal is to maximize the length of the resulting array such that the final sequence is non‑decreasing. The challenge is deciding where to merge so each segment sum is at least the previous one.
Approach 1: Simple Greedy Segment Merging (O(n log n) time, O(n) space)
This approach processes the array left to right while maintaining segment sums. Start by treating every element as its own segment. If the current segment sum becomes smaller than the previous segment sum, merge segments until the non‑decreasing property holds again. A stack-like structure keeps track of segment sums. When a violation occurs, pop previous segments, combine their sums, and push the merged result back. This greedy merging works because once a segment violates the order, the only fix is merging with previous segments to increase its value. The method relies on properties similar to a monotonic stack. Time complexity is O(n log n) or amortized close to O(n) depending on merge operations, with O(n) space for storing segment sums.
Approach 2: Dynamic Programming with Prefix Sums and Monotonic Queue (O(n) time, O(n) space)
The optimal strategy models the problem using dynamic programming. Let dp[i] represent the maximum number of valid segments considering the first i elements. Use prefix sums so the sum of any segment (j+1..i) can be computed in O(1). The transition checks whether the new segment sum is at least the previous segment’s sum. To avoid O(n²) comparisons, maintain candidate states in a monotonic structure based on the minimum valid previous segment sum. A monotonic queue helps quickly discard suboptimal states while preserving the best transition for each position.
The key insight is that each DP state can be represented by the minimum possible last segment sum that achieves a certain number of segments. As the array grows, earlier states that can never produce a better result are removed from the queue. This keeps transitions constant time on average, producing an overall O(n) solution with O(n) additional space.
Recommended for interviews: Interviewers expect the dynamic programming solution with prefix sums and a monotonic optimization. The greedy merging idea helps build intuition about why segments must sometimes collapse into larger sums, but the optimized DP shows stronger algorithmic control and handles worst‑case inputs efficiently. Demonstrating both ideas—first the greedy intuition, then the O(n) DP—signals strong problem‑solving depth.
Approach 1: Simple Greedy Approach
The idea is to iterate over the array and keep track of the longest non-decreasing subarray found so far. Merge only when necessary to maintain non-decreasing order.
def max_non_decreasing_length(nums):
max_length = 1
current_length = 1
for i in range(1, len(nums)):
if nums[i] >= nums[i - 1]:
current_length += 1
max_length = max(max_length, current_length)
else:
current_length = 1
return max_length
print(max_non_decreasing_length([4, 3, 2, 6]))public class Main {
public static int maxNonDecreasingLength(int[] nums) {
int maxLength = 1, currentLength = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] >= nums[i - 1]) {
currentLength++;
if (currentLength > maxLength) {
maxLength = currentLength;
}
} else {
currentLength = 1;
}
}
return maxLength;
}
public static void main(String[] args) {
int[] nums = {4, 3, 2, 6};
System.out.println(maxNonDecreasingLength(nums));
}
}#include <iostream>
#include <vector>
int maxNonDecreasingLength(const std::vector<int>& nums) {
int maxLength = 1, currentLength = 1;
for (size_t i = 1; i < nums.size(); ++i) {
if (nums[i] >= nums[i - 1]) {
++currentLength;
maxLength = std::max(maxLength, currentLength);
} else {
currentLength = 1;
}
}
return maxLength;
}
int main() {
std::vector<int> nums = {4, 3, 2, 6};
std::cout << maxNonDecreasingLength(nums) << std::endl;
return 0;
}function maxNonDecreasingLength(nums) {
let maxLength = 1;
let currentLength = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] >= nums[i - 1]) {
currentLength++;
maxLength = Math.max(maxLength, currentLength);
} else {
currentLength = 1;
}
}
return maxLength;
}
console.log(maxNonDecreasingLength([4, 3, 2, 6]));#include <stdio.h>
int maxNonDecreasingLength(int* nums, int numsSize) {
int maxLength = 1;
int currentLength = 1;
for (int i = 1; i < numsSize; ++i) {
if (nums[i] >= nums[i - 1]) {
currentLength++;
if (currentLength > maxLength) {
maxLength = currentLength;
}
} else {
currentLength = 1;
}
}
return maxLength;
}
int main() {
int nums[] = {4, 3, 2, 6};
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxNonDecreasingLength(nums, length));
return 0;
}using System;
public class Program {
public static int MaxNonDecreasingLength(int[] nums) {
int maxLength = 1, currentLength = 1;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] >= nums[i - 1]) {
currentLength++;
maxLength = Math.Max(maxLength, currentLength);
} else {
currentLength = 1;
}
}
return maxLength;
}
public static void Main() {
int[] nums = {4, 3, 2, 6};
Console.WriteLine(MaxNonDecreasingLength(nums));
}
}A Python implementation utilizing a standard loop and if condition to maintain running and maximum subarray lengths.
Time Complexity: O(n), Space Complexity: O(1)
Approach 2: Dynamic Programming Approach
Use a DP table to store the maximum length of non-decreasing subarrays ending at each position. This uses the relation to previous subarray lengths.
def max_non_decreasing_length(nums):
if not nums:
return 0
dp = [1] * len(nums)
max_length = 1
for i in range(1, len(nums)):
if nums[i] >= nums[i - 1]:
dp[i] = dp[i - 1] + 1
max_length = max(max_length, dp[i])
return max_length
print(max_non_decreasing_length([4, 3, 2, 6]))public class Main {
public static int maxNonDecreasingLength(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
dp[0] = 1;
int maxLength = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] >= nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
dp[i] = 1;
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
public static void main(String[] args) {
int[] nums = {4, 3, 2, 6};
System.out.println(maxNonDecreasingLength(nums));
}
}#include <iostream>
#include <vector>
int maxNonDecreasingLength(const std::vector<int>& nums) {
if (nums.empty()) return 0;
std::vector<int> dp(nums.size(), 1);
int maxLength = 1;
for (size_t i = 1; i < nums.size(); ++i) {
if (nums[i] >= nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
}
maxLength = std::max(maxLength, dp[i]);
}
return maxLength;
}
int main() {
std::vector<int> nums = {4, 3, 2, 6};
std::cout << maxNonDecreasingLength(nums) << std::endl;
return 0;
}function maxNonDecreasingLength(nums) {
if (nums.length === 0) return 0;
let dp = Array(nums.length).fill(1);
let maxLength = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] >= nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
console.log(maxNonDecreasingLength([4, 3, 2, 6]));#include <stdio.h>
#include <stdlib.h>
int maxNonDecreasingLength(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int* dp = (int*)malloc(numsSize * sizeof(int));
dp[0] = 1;
int maxLength = 1;
for (int i = 1; i < numsSize; ++i) {
if (nums[i] >= nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
dp[i] = 1;
}
if (dp[i] > maxLength) {
maxLength = dp[i];
}
}
free(dp);
return maxLength;
}
int main() {
int nums[] = {4, 3, 2, 6};
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxNonDecreasingLength(nums, length));
return 0;
}using System;
public class Program {
public static int MaxNonDecreasingLength(int[] nums) {
if (nums.Length == 0) return 0;
int[] dp = new int[nums.Length];
dp[0] = 1;
int maxLength = 1;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] >= nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
dp[i] = 1;
}
maxLength = Math.Max(maxLength, dp[i]);
}
return maxLength;
}
public static void Main() {
int[] nums = {4, 3, 2, 6};
Console.WriteLine(MaxNonDecreasingLength(nums));
}
}A `dp` array is used to keep track of the longest non-decreasing lengths, iteratively updated.
Time Complexity: O(n), Space Complexity: O(n)
Approach 3: Default Approach
function findMaximumLength(nums: number[]): number {
const n = nums.length;
const f: number[] = Array(n + 1).fill(0);
const pre: number[] = Array(n + 2).fill(0);
const s: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
const search = (nums: number[], x: number): number => {
let [l, r] = [0, nums.length];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let i = 1; i <= n; ++i) {
pre[i] = Math.max(pre[i], pre[i - 1]);
f[i] = f[pre[i]] + 1;
const j = search(s, s[i] * 2 - s[pre[i]]);
pre[j] = i;
}
return f[n];
}func findMaximumLength(nums []int) int {
n := len(nums)
f := make([]int, n+1)
pre := make([]int, n+2)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
for i := 1; i <= n; i++ {
pre[i] = max(pre[i], pre[i-1])
f[i] = f[pre[i]] + 1
j := sort.SearchInts(s, s[i]*2-s[pre[i]])
pre[j] = max(pre[j], i)
}
return f[n]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simple Greedy Approach | Time Complexity: O(n), Space Complexity: O(1) |
| Dynamic Programming Approach | Time Complexity: O(n), Space Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Segment Merging (Stack) | O(n log n) amortized | O(n) | Good for building intuition and implementing quickly when constraints are moderate. |
| Dynamic Programming + Prefix Sum + Monotonic Queue | O(n) | O(n) | Best for large inputs and interview settings where optimal performance is required. |
Frequently asked questions
Is Find Maximum Non-decreasing Array Length easy or hard?
Find Maximum Non-decreasing Array Length is classified as a Hard problem with a low acceptance rate around 18%. The difficulty comes from recognizing the need for dynamic programming and applying monotonic queue optimization to reduce the naive O(n²) transition to O(n).
Find Maximum Non-decreasing Array Length Python/Java solution
Python and Java implementations typically compute prefix sums, maintain a DP array, and use a deque to implement the monotonic queue optimization. Each index processes transitions in constant time, ensuring the final solution runs in O(n) time with O(n) space.
How to solve Find Maximum Non-decreasing Array Length in O(n)?
Compute prefix sums so any segment sum can be evaluated in constant time. Use dynamic programming where dp[i] represents the maximum valid segments up to index i. Maintain candidate states in a monotonic queue ordered by the minimum feasible last segment sum. This structure allows constant-time transitions, reducing the overall complexity to O(n).
What is the best approach for Find Maximum Non-decreasing Array Length?
The most efficient approach uses dynamic programming combined with prefix sums and a monotonic queue. Each DP state tracks the maximum number of segments while maintaining the minimum possible last segment sum. The monotonic structure removes dominated states and keeps transitions constant time, producing an overall O(n) time and O(n) space solution.
Is Find Maximum Non-decreasing Array Length asked at Google/Amazon/Meta?
Hard array and dynamic programming problems with monotonic structures commonly appear in interviews at companies like Google, Amazon, and Meta. The problem tests understanding of prefix sums, DP optimization, and monotonic data structures, which are standard topics in high-level algorithm interviews.
What data structure is used in Find Maximum Non-decreasing Array Length?
The optimal solution uses prefix sums, dynamic programming arrays, and a monotonic queue or stack to manage candidate states efficiently. These structures help track valid segment transitions while discarding states that cannot produce better results.
What is the time complexity of Find Maximum Non-decreasing Array Length?
The optimal solution runs in O(n) time using dynamic programming with prefix sums and a monotonic queue. A simpler greedy stack-based merging method may take around O(n log n) in practice depending on merge operations. Both approaches use O(n) additional space for tracking segment sums or DP states.