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:

  1. Start by initializing an array s to keep the prefix sums of the nums array. This allows us to determine the sum of any subarray quickly.

  2. Initialize two arrays – f which will hold the dynamic programming states representing the maximum length of the non-decreasing subarray, and pre which helps track the indices relevant for our subarray replacements.

  3. Iterate through the array nums with i going from 1 to n, where n is the length of nums. For each i, we perform the following steps:

    • Set pre[i] to the maximum of pre[i] and pre[i - 1], ensuring pre[i] always holds the largest index so far where subarray replacement can start.

    • Calculate f[i] as f[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 index j where s[j] >= s[i] * 2 - s[pre[i]]. The sought j represents the potential end of a replacement subarray.

    • Update the pre[j] index to i, but only if i is greater than the current value of pre[j]. This prepares the pre array for the next elements to make decisions on whether they can extend the current non-decreasing subarray.

  4. The dynamic programming array f accumulates the information about the maximum length of a non-decreasing array that can be achieved up to each index i.

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 Evaluator

Example Walkthrough

Let us illustrate the solution approach with a small example:

Suppose our array nums is [1, 2, 4, 1, 2, 4, 1].

  1. We first compute the prefix sums array s. The prefix sum at index i is the sum of all nums[j] where j <= i:

    1nums: [1, 2, 4, 1, 2, 4, 1]
    2s:    [1, 3, 7, 8, 10, 14, 15] (each `s[i]` is the sum of all elements up to and including `i` in `nums`)
  2. Initialize the f and pre arrays of the same length as nums, with initial values of 0 for f and indices of 0 for pre.

    1f:   [0, 0, 0, 0, 0, 0, 0]
    2pre: [0, 0, 0, 0, 0, 0, 0]
  3. Start iterating through nums:

    • For i = 1, pre[1] is set to the maximum of pre[0] and 0, yielding pre[1] = pre[0]. For i = 1, the non-decreasing subarray can only include nums[i], so f[1] = 1.
    1nums: [1, 2, 4, 1, 2, 4, 1]
    2f:    [0, 1, 0, 0, 0, 0, 0]
    3pre:  [0, 0, 0, 0, 0, 0, 0]
    • For i = 2, since nums[2] is greater than or equal to nums[1], we can extend the current non-decreasing subarray. Thus, f[2] = f[1] + 1 = 2.
    1nums: [1, 2, 4, 1, 2, 4, 1]
    2f:    [0, 1, 2, 0, 0, 0, 0]
    3pre:  [0, 0, 0, 0, 0, 0, 0]
    • At i = 3, since nums[3] is less than nums[2], we need to perform a replacement operation. We perform a binary search to find the least index j where s[j] >= s[i] * 2 - s[pre[i]]. We find that j is 3 itself. We set pre[3] to the current index i and calculate f[3].
    1nums: [1, 2, 4, 1, 2, 4, 1]
    2f:    [0, 1, 2, 2, 0, 0, 0]
    3pre:  [0, 0, 0, 3, 0, 0, 0]
    • For i = 4, since nums[4] is greater than or equal to nums[3], we can extend the current non-decreasing subarray. Thus, f[4] = f[3] + 1 = 3.
    1nums: [1, 2, 4, 1, 2, 4, 1]
    2f:    [0, 1, 2, 2, 3, 0, 0]
    3pre:  [0, 0, 0, 3, 3, 0, 0]
    • For i = 5, since nums[5] is greater than or equal to nums[4], we can extend the current non-decreasing subarray. Thus, f[5] = f[4] + 1 = 4.
    1nums: [1, 2, 4, 1, 2, 4, 1]
    2f:    [0, 1, 2, 2, 3, 4, 0]
    3pre:  [0, 0, 0, 3, 3, 4, 0]
    • At i = 6, since nums[6] is less than nums[5], we need to perform a replacement operation. We perform a binary search to find the least index j where s[j] >= s[i] * 2 - s[pre[i]]. We find that j is 6 itself. We set pre[6] to the current index i and calculate f[6].
    1nums: [1, 2, 4, 1, 2, 4, 1]
    2f:    [0, 1, 2, 2, 3, 4, 4]
    3pre:  [0, 0, 0, 3, 3, 4, 6]
  4. 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:

  1. Accumulating the sum: The accumulate function is applied to the list nums, which takes O(n) time for a list of n elements.

  2. Iterative Calculation:

    • There is a for loop that runs from 1 to n. Inside the loop, the max function is called, and access/update operations on arrays are performed. These operations are O(1).
    • The bisect_left function is called within the for loop, which performs a binary search on the prefix sum array s. This takes O(log n) time. Since this is within the for loop, it contributes to O(n log n) time over the full loop.

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:

  1. Prefix Sum Array s: Stores the prefix sums, requiring O(n) space.
  2. Array f: An array of length n+1, also requiring O(n) space.
  3. Array pre: Another array of length n+2, contributing O(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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which two pointer techniques do you use to check if a string is a palindrome?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.

Navin Tiwari

nums: [1, 2, 4, 1, 2, 4, 1]

For the above array used in the example walk through, the answer should be 4 not 3. The example walk through incorrectly computes it to be 3.

Please correct it.

Sun Jul 21 2024