2945. Find Maximum Non-decreasing Array Length
Problem Description
The given problem presents an array nums
of integers and permits operations where you select a subarray and replace it with its sum. The task is to return the maximum length of a non-decreasing array that you can achieve by performing any number of these operations. A non-decreasing array means each element is greater than or equal to the previous element.
Intuition
To solve this problem, the intuition is to use dynamic programming along with binary search. Dynamic programming will store intermediate solutions to subproblems, while binary search will help us quickly find positions in the array relevant to our calculations.
We'll keep track of a running sum of the array and construct a DP array f
where f[i]
represents the maximum length of the non-decreasing subarray ending at position i
. We'll also maintain a pre
array where pre[i]
holds the highest index j < i
such that nums[j] <= 2 * nums[i]
.
While iterating over the array, we'll use binary search to find the index j
where we can replace a subarray [x...j]
that doubles the element nums[x]
. We then set pre[j]
to the current index i
if it's not already set to a larger index. By doing this, we can efficiently extend the non-decreasing subarray as we move through nums
.
The solution returns f[n]
, which by the end of the algorithm, holds the maximum length of a non-decreasing array that can be created.
Learn more about Stack, Queue, Binary Search, Dynamic Programming, Monotonic Queue and Monotonic Stack patterns.
Solution Approach
The implementation of the solution uses dynamic programming along with a binary search to effectively tackle the problem. Here's a step-by-step breakdown of how the algorithm and its components ā arrays f
and pre
, the sum array s
, and binary search ā work together in the solution:
-
Start by initializing an array
s
to keep the prefix sums of thenums
array. This allows us to determine the sum of any subarray quickly. -
Initialize two arrays ā
f
which will hold the dynamic programming states representing the maximum length of the non-decreasing subarray, andpre
which helps track the indices relevant for our subarray replacements. -
Iterate through the array
nums
withi
going from1
ton
, wheren
is the length ofnums
. For eachi
, we perform the following steps:-
Set
pre[i]
to the maximum ofpre[i]
andpre[i - 1]
, ensuringpre[i]
always holds the largest index so far where subarray replacement can start. -
Calculate
f[i]
asf[pre[i]] + 1
. This essentially adds the length of the optimal subarray before the current index plus one for the current element. -
Perform a binary search on the prefix sums array
s
to find the least indexj
wheres[j] >= s[i] * 2 - s[pre[i]]
. The soughtj
represents the potential end of a replacement subarray. -
Update the
pre[j]
index toi
, but only ifi
is greater than the current value ofpre[j]
. This prepares thepre
array for the next elements to make decisions on whether they can extend the current non-decreasing subarray.
-
-
The dynamic programming array
f
accumulates the information about the maximum length of a non-decreasing array that can be achieved up to each indexi
.
After iterating over the whole array nums
, f[n]
will contain the length of the maximum non-decreasing subarray possible after performing the allowed subarray replacement operations. The final result is then simply f[n]
.
The combination of prefix sums, binary search, and dynamic programming allows this algorithm to efficiently compute the maximum length of the non-decreasing subarray in an otherwise complex problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us illustrate the solution approach with a small example:
Suppose our array nums
is [1, 2, 4, 1, 2, 4, 1]
.
-
We first compute the prefix sums array
s
. The prefix sum at indexi
is the sum of allnums[j]
wherej <= i
:nums: [1, 2, 4, 1, 2, 4, 1] s: [1, 3, 7, 8, 10, 14, 15] (each `s[i]` is the sum of all elements up to and including `i` in `nums`)
-
Initialize the
f
andpre
arrays of the same length asnums
, with initial values of0
forf
and indices of0
forpre
.f: [0, 0, 0, 0, 0, 0, 0] pre: [0, 0, 0, 0, 0, 0, 0]
-
Start iterating through
nums
:- For
i = 1
,pre[1]
is set to the maximum ofpre[0]
and0
, yieldingpre[1] = pre[0]
. Fori = 1
, the non-decreasing subarray can only includenums[i]
, sof[1] = 1
.
nums: [1, 2, 4, 1, 2, 4, 1] f: [0, 1, 0, 0, 0, 0, 0] pre: [0, 0, 0, 0, 0, 0, 0]
- For
i = 2
, sincenums[2]
is greater than or equal tonums[1]
, we can extend the current non-decreasing subarray. Thus,f[2] = f[1] + 1 = 2
.
nums: [1, 2, 4, 1, 2, 4, 1] f: [0, 1, 2, 0, 0, 0, 0] pre: [0, 0, 0, 0, 0, 0, 0]
- At
i = 3
, sincenums[3]
is less thannums[2]
, we need to perform a replacement operation. We perform a binary search to find the least indexj
wheres[j] >= s[i] * 2 - s[pre[i]]
. We find thatj
is3
itself. We setpre[3]
to the current indexi
and calculatef[3]
.
nums: [1, 2, 4, 1, 2, 4, 1] f: [0, 1, 2, 2, 0, 0, 0] pre: [0, 0, 0, 3, 0, 0, 0]
- For
i = 4
, sincenums[4]
is greater than or equal tonums[3]
, we can extend the current non-decreasing subarray. Thus,f[4] = f[3] + 1 = 3
.
nums: [1, 2, 4, 1, 2, 4, 1] f: [0, 1, 2, 2, 3, 0, 0] pre: [0, 0, 0, 3, 3, 0, 0]
- For
i = 5
, sincenums[5]
is greater than or equal tonums[4]
, we can extend the current non-decreasing subarray. Thus,f[5] = f[4] + 1 = 4
.
nums: [1, 2, 4, 1, 2, 4, 1] f: [0, 1, 2, 2, 3, 4, 0] pre: [0, 0, 0, 3, 3, 4, 0]
- At
i = 6
, sincenums[6]
is less thannums[5]
, we need to perform a replacement operation. We perform a binary search to find the least indexj
wheres[j] >= s[i] * 2 - s[pre[i]]
. We find thatj
is6
itself. We setpre[6]
to the current indexi
and calculatef[6]
.
nums: [1, 2, 4, 1, 2, 4, 1] f: [0, 1, 2, 2, 3, 4, 4] pre: [0, 0, 0, 3, 3, 4, 6]
- For
-
The final result is the largest value in
f
, which in this case is 4. This indicates the maximum length of a non-decreasing subarray that we can achieve after performing these operations is 4.
Solution Implementation
1from itertools import accumulate
2from bisect import bisect_left
3from typing import List
4
5class Solution:
6 def findMaximumLength(self, nums: List[int]) -> int:
7 # Calculate the length of nums list
8 num_elements = len(nums)
9
10 # Create a prefix sum list of numbers with an initial value 0 for easier index management
11 prefix_sum = list(accumulate(nums, initial=0))
12
13 # Initialize DP array f with length of num_elements + 1, to store the maximum lengths
14 max_lengths = [0] * (num_elements + 1)
15
16 # Initialize DP array pre to keep track of previous indices in the
17 # prefix_sum at which new maximum lengths were calculated
18 previous_indices = [0] * (num_elements + 2)
19
20 # Iterate over the nums list to fill in the DP arrays
21 for i in range(1, num_elements + 1):
22 # Update the previous index with the maximum value between the current
23 # and the previous maximum index.
24 previous_indices[i] = max(previous_indices[i], previous_indices[i - 1])
25
26 # Set the current maximum length to be either the same as previous max length, or 1 more
27 # than the max length found at the previous maximum index.
28 max_lengths[i] = max_lengths[previous_indices[i]] + 1
29
30 # Find the next index in prefix_sum where a new segment can potentially be started
31 next_index = bisect_left(prefix_sum, prefix_sum[i] * 2 - prefix_sum[previous_indices[i]])
32
33 # Update the previous_indices list to indicate a new segment length has been found
34 previous_indices[next_index] = i
35
36 # Return the final maximum length from the last position of the max_lengths list
37 return max_lengths[num_elements]
38
1class Solution {
2 public int findMaximumLength(int[] nums) {
3 int length = nums.length;
4 long[] prefixSum = new long[length + 1];
5 // Building the prefix sum array
6 for (int i = 0; i < length; ++i) {
7 prefixSum[i + 1] = prefixSum[i] + nums[i];
8 }
9
10 // Initialize the array where f[i] stores the maximum length of the sequence ending at index i
11 int[] maxLength = new int[length + 1];
12 int[] maxIndexWithSum = new int[length + 2];
13 // Iterate over the array to populate maxIndexWithSum and maxLength
14 for (int i = 1; i <= length; ++i) {
15 maxIndexWithSum[i] = Math.max(maxIndexWithSum[i], maxIndexWithSum[i - 1]);
16 maxLength[i] = maxLength[maxIndexWithSum[i]] + 1;
17
18 // Perform a binary search to find the index with desired sum
19 int index = Arrays.binarySearch(prefixSum, prefixSum[i] * 2 - prefixSum[maxIndexWithSum[i]]);
20 if (index < 0) {
21 index = -index - 1; // convert to insertion point if element not found
22 }
23 // Update the maxIndexWithSum array with the current index
24 maxIndexWithSum[index] = i;
25 }
26
27 // The last element in maxLength array holds the maximum length of the sequence for the whole array
28 return maxLength[length];
29 }
30}
31
1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7 int findMaximumLength(vector<int>& nums) {
8 int n = nums.size(); // Number of elements in nums
9
10 // f represents the maximum length ending at position i
11 vector<int> max_length_ending_at(n + 1, 0);
12
13 // pre records the furthest position that can be reached from the current position
14 vector<int> furthest_reachable(n + 2, 0);
15
16 // Prefix sums of nums, with s[0] initialized to 0 for easier calculations
17 vector<long long> prefix_sum(n + 1, 0);
18 for (int i = 0; i < n; ++i) {
19 prefix_sum[i + 1] = prefix_sum[i] + nums[i];
20 }
21
22 // Iterate through positions of the array
23 for (int i = 1; i <= n; ++i) {
24 // Update the furthest reachable position for the current position i
25 furthest_reachable[i] = std::max(furthest_reachable[i], furthest_reachable[i - 1]);
26
27 // Update the maximum length at position i
28 max_length_ending_at[i] = max_length_ending_at[furthest_reachable[i]] + 1;
29
30 // Find the new furthest position that can be reached where the sum is doubled of segment up to i
31 int new_position = std::lower_bound(prefix_sum.begin(), prefix_sum.end(),
32 prefix_sum[i] * 2 - prefix_sum[furthest_reachable[i]]) - prefix_sum.begin();
33
34 // Update the furthest reachable index for the new position
35 furthest_reachable[new_position] = i;
36 }
37
38 // Return the maximum length at the last position which is the answer to the problem
39 return max_length_ending_at[n];
40 }
41};
42
1// Function to find the maximum length of a subarray with equal number of 0s and 1s
2function findMaximumLength(nums: number[]): number {
3 const n = nums.length;
4 // Initialize the array to store the furthest index with an equal number of 0s and 1s observed so far
5 const furthestEqualSubarrayEnds: number[] = Array(n + 1).fill(0);
6 // Initialize previous indices of the furthest index where a balanced subarray ends
7 const previousIndices: number[] = Array(n + 2).fill(0);
8 // Prefix sums of `nums`, s[i] is the sum of nums[0] to nums[i-1]
9 const prefixSums: number[] = Array(n + 1).fill(0);
10
11 // Compute Prefix Sums
12 for (let i = 1; i <= n; ++i) {
13 prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
14 }
15
16 // Binary search utility method to find the leftmost position where `x` can be inserted
17 // into an array `nums` without breaking the sorting
18 const binarySearch = (nums: number[], x: number): number => {
19 let [left, right] = [0, nums.length];
20 // Perform binary search
21 while (left < right) {
22 // Find the mid index
23 const mid = (left + right) >> 1;
24 if (nums[mid] >= x) {
25 right = mid;
26 } else {
27 left = mid + 1;
28 }
29 }
30 return left;
31 };
32
33 // Iterate through the array and update the furthestEqualSubarrayEnds and previousIndices
34 for (let i = 1; i <= n; ++i) {
35 previousIndices[i] = Math.max(previousIndices[i], previousIndices[i - 1]);
36 furthestEqualSubarrayEnds[i] = furthestEqualSubarrayEnds[previousIndices[i]] + 1;
37 // Binary search for the position where a balanced subarray can potentially end
38 const j = binarySearch(prefixSums, prefixSums[i] * 2 - prefixSums[previousIndices[i]]);
39 previousIndices[j] = i;
40 }
41
42 // Return the last element in furthestEqualSubarrayEnds which gives the length of the longest subarray
43 return furthestEqualSubarrayEnds[n];
44}
45
Time and Space Complexity
Time Complexity
The time complexity of the given code consists of several parts:
-
Accumulating the sum: The
accumulate
function is applied to the listnums
, which takesO(n)
time for a list ofn
elements. -
Iterative Calculation:
- There is a for loop that runs from
1
ton
. Inside the loop, themax
function is called, and access/update operations on arrays are performed. These operations areO(1)
. - The
bisect_left
function is called within the for loop, which performs a binary search on the prefix sum arrays
. This takesO(log n)
time. Since this is within the for loop, it contributes toO(n log n)
time over the full loop.
- There is a for loop that runs from
Combining these, the overall time complexity is O(n) + O(n log n)
. Since O(n log n)
dominates O(n)
, the final time complexity is O(n log n)
.
Space Complexity
The space complexity of the code is due to the storage used by several arrays:
- Prefix Sum Array
s
: Stores the prefix sums, requiringO(n)
space. - Array
f
: An array of lengthn+1
, also requiringO(n)
space. - Array
pre
: Another array of lengthn+2
, contributingO(n)
space.
The total space complexity sums up to O(n)
because adding the space requirements for s
, f
, and pre
does not change the order of magnitude.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Want a Structured Path to Master System Design Too? Donāt Miss This!