Longest Subarray whose Elements can be made Equal by Maximum K Increments

Approach

First we need to make an observation. Let’s say I have given you an array arr. Your task is to make the elements in the array equal with minimum possible increments. How will you approach this problem?

Think greedily! You should first decide what should be that value to which every element should convert to. Putting a little attention, you can realise there is no point of increasing the maximum element in the given array. And hence, all the elements in the array should converge to the maximum element. Now, we can simply sum the differences between the maximum element and rest of the array elements and that would be the answer.

Brute Force Approach

One straightforward approach would be to consider all possible subarrays in the array. Let's say the current subarray in consideration starts from index i and ends at index j, i.e., arr[i…j]. To calculate the cost of making all the elements in this subarray equal we can use our above discussion. Find the maximum element in this subarray and calculate the sum of differences of this element from the rest of the subarray elements. If this value does not exceed K, this subarray could be one of the possible answers. Then simply take the maximum of the current answer and the size of this subarray.

Efficient Approach

As you can see, in the previous approach we have considered all possible subarrays of the given array. Is it really necessary to consider all of them? In the efficient approach we will use the sliding window technique to solve this problem in a much more efficient way.

Let’s say we have initialised our current optimal subarray optimalSubarray with an empty array. Now, we will keep adding elements from the array beginning with index 0, till the cost of making all elements in the optimalSubarray array becomes greater than K. When it becomes greater than K, we will start popping elements from the optimalSubarray array from the front one by one till the cost becomes less than or equal to K. When the cost will become less than K, we will continue adding elements from the given array to the optimalSubarray array. This cycle will continue to execute till all the elements from the given array are taken into account.

We can implement this approach using prefix sum and deque data structure to compute the cost of making a subarray satisfy the criteria and find the maximum element in a subarray respectively. More detailed implementation is described in the algorithm below.

Algorithm

1. Create a deque and prefixSum array.
2. Compute the prefix sum of the given array by following the standard technique in O(N) time.
3. Create a variable start to denote the lower limit of the subarray that satisfies the given criteria of maximum increments to make the elements in the subarray equal.
4. Create variables maxSize and maxElem to hold the size of longest subarray and maximum element in a subarray respectively.
5. Run a loop from 0 to N - 1 with loop variable i and do the following:
   1. While the deque is not empty and the element represented by the back of the deque is less than the current element arr[i], pop the deque from the back.
   2. Push the current element into the deque.
   3. Update maxElem to check if the current element is the maximum element in the subarray under consideration i.e. arr[start…i].
   4. While the cost of making elements in the current subarray equal is greater than K and start < i (as there should be at least one element in the optimal subarray), do the following:
      1. Increment the lower limit start by one.
      2. Update the maximum element in the new subarray.
   5. Update maxSize with max(maxSize, start - i + 1) as the subarray arr[start…i] satisfies the given criteria.
6. Output the maxSize.

Program

#include<bits/stdc++.h>
using namespace std;

// Main driver code.
int main(){
   // Input array.
   int arr[] = {4, 5, 10, 3, 4};
   int N = sizeof(arr)/sizeof(arr[0]);

   // Maximum increment allowed.
   int K = 12;
  
   // Deque to find the maximum element in any subarray.
   deque<int> maxFind;

   // Prefix Sum storage.
   int prefixSum[N + 1];
   prefixSum[0] = 0;

   // Calculating the elements of the prefix sum array.
   for(int i = 1; i <= N; i++){
       prefixSum[i] = prefixSum[i-1] + arr[i-1];
   }

   // Starting point of the optimal subarray.
   int start = 0;

   // To store the maximum element in a subarray.
   int maxElem;

   // The maximum size of the subarray.
   int maxSize = 0;

   for(int i = 0; i < N; i++){

       // While the element represented by the back element of the deque is less than the current element, pop it.
       // It is because, for any subarray,
       // If we know that the current element is greater than the previous elements in the subarray arr[start...i],
       // We need not keep them as the maximum element in the subarray under consideration is the current element only.
       while(!maxFind.empty() && arr[maxFind.back()] < arr[i]){
           maxFind.pop_back();
       }
       // Push the current element after removing all the elements smaller than it in the subarray arr[start..i]
       maxFind.push_back(i);
       // Update the maxElem.
       if(i == 0){
           maxElem = arr[i];
       }
       else maxElem = max(maxElem, arr[i]);

       // Check if the cost associated with subarray arr[start..i] is greater than K.
       // Method to calculate the cost -
       // Let's say that the index of the maximum element in the subarray arr[start..i] is ind.
       // Then the cost can be calculated as
       // arr[ind] - arr[start] + arr[ind] - arr[start + 1] + ... + arr[ind] - arr[i] = (i - start + 1) * arr[ind] - (arr[start] + arr[start+1] + ... + arr[i])
       // Cost = (i - start + 1) * maxElem - (prefixSum[i + 1] - prefixSum[start])
       while((i-start+1)*maxElem - (prefixSum[i+1] - prefixSum[start]) > K && i>start){
           // Increment the lower limit of the optimal subarray.
           start++;
           // Update the maximum element in the new subarray.
           while(!maxFind.empty()&&maxFind.front() < start&&start<i){
               maxFind.pop_front();
               maxElem = arr[maxFind.front()];
           }
       }

       // Take the maximum of maxSize and current subarray satisfying the condition.
       maxSize = max(maxSize, i - start + 1);
   }

   // Output the maximum size.
   cout<<maxSize<<endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

N = 5

Array: {4, 5, 10, 3, 4}

K = 12

Output

3

Input

N = 5

Array: {1, 2, 1, 2, 4}

K = 10

Output

5

Time Complexity

The time complexity of the brute force approach is O(N^3) where N is the size of the array. This is because for computing the cost of each subarray we will require O(N) time and consideration of all subarrays is itself a O(N^2) time complexity process.

The time complexity of the efficient approach is O(N) over all iterations of the for loop in the program, the sliding window technique can do utmost O(2*N) operations by moving the front the back pointers of the subarrays which is equivalent to O(N).

Space Complexity

The space complexity of the above approach is O(N) where N is the size of the array. It is owing to the size of the prefix sum array and deque data structure.

FAQs

1. What is the time complexity of the sliding window technique?
   The general time complexity of the sliding window technique is O(N), where N is the size of the data structure to slide the window on. However, if we a O(X) time complexity operation in each iteration of the sliding window, the time complexity becomes O(N * X).
    
2. What is the difference between static and deque data structures?
   In deque data structure, we can add and remove elements from both ends of the data structure. However, in the stack data structure, we can do so from only the back side.
    
3. What is the difference between queue and deque data structures?
   In deque data structure, we can add and remove elements from both ends of the data structure. However, in the queue data structure, we can do so from only the front side.
    
4. Where can we apply the sliding window technique?
   Sliding window technique is a greedy algorithm. It is useful in scenarios where we need to find an optimal subarray satisfying a given criteria as illustrated in this blog. However there are some other points to consider as well. It should be taken care of that we can obtain the solution by moving the lower limit of the window in the forward direction only.

Key Takeaways

Cheers if you reached here!! 

In this blog, we discussed a comprehensive problem involving a lot of significant techniques. We discussed sliding window technique, used prefix sum to find the sum of any subarray in O(1) and explored the use of deque data structure to find the maximum element in any subarray. This blog combined these techniques to solve the coding challenge.

Check out this problem - Subarray With 0 Sum

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!