Maximum Equality

Approach :

• If a particular length satisfies the criteria, we do not need to check for a list's size lower than this length. Hence, we can binary search for the answer.
• The minimum subarray length satisfying the criteria will be 1 and the maximum can be the length of the array.
• To check whether a particular length of subarray satisfies the criteria, we can use the concept of sliding window maximum.
• The number of operations required in a subarray of length A[i-j] is the maximum of elements (A[i], A[i+1], .. A[j] minus the sum of elements (A[i] + A[i+1]..A[j]).
• Hence, we can maintain a sliding window maximum and calculate the sum of elements in the window either using prefix sums or by subtracting the element exiting the window and adding the new element of the window.
• We will return the answer obtained by the binary search.

Algorithm:

• Initialise an integer variable 'low' as 1 and 'high' as 'N' since the longest subarray length can be in this range.
• Declare an integer variable 'ans' to store the answer found from binary search.
• Perform binary search and implement a 'checker' function as follows:
  • Initialize an integer variable 'sum' = 0 and 'idx' =0 and 'p' = 0.
  • Initialize an empty deque 'dq'. We will store indices in deque to maintain a sliding window max.
  • Iterate from 'i' = 0 to 'N-1':
    • While the deque is not empty and the front of the deque is less than or equal to '(i - mid)' i.e. we have more than 'mid' elements, we pop from the front of the deque.
    • While the deque is not empty and 'A[dq.back()]' is less than the current element, we pop from the back since the current element is a potential max element.
    • Increment the variable 'sum' by A[i] and push 'i' in the back of the deque.
    • If 'i' >= (mid-1) i.e. the length of the current window is at least 'mid', perform the following:
      • Since the front of the deque contains the index of the largest element in the window, initialize 'p' = A[dq.front()]. Since all elements have to be equal to this element, the total sum of the window should be 'p*mid', so update 'p' = 'p*mid'.
      • Now the total operations needed = mid*max element - sum of all elements in the window. So declare an integer variable 'operations' = '(p-sum)'.
      • If 'operations' is less than or equal to 'X', we return true, otherwise, we slide the window by decreasing the element at the left-most index pointed by 'idx' from the 'sum' and then incrementing 'idx'. i.e. 'sum-= A[idx] and 'idx++'.

• If we finish traversing the array and did not return 'true' at any point, then it means we could not find any subarray of length 'mid' that could satisfy the criteria so we return 'false'.
• If the 'checker' function returns true, we update 'ans' to 'mid' and expand our search space to the right i.e. update 'low' = 'mid+1'.
• Otherwise, we lower our search space and update 'high' = 'mid-1'.
• Return 'ans' as the final output.

Approach :

• We can establish the biggest window possible by discovering the max value inside the window and multiplying it by the number of elements in the window. Refer to this value as the 'required total'.
• We can compare the 'required total' by the actual sum of elements of the array and if the result is within limits 'X', we can try extending the window further.
• If at any point the result exceeds 'X', we can shift the whole window in an attempt to find a window that will fall within the limit.
• We require two important things to simplify the algorithm:
  • A prefix sum array to calculate the sum of elements in a range within the array quickly.
  • A monotonic deque to keep track of the maximum value inside the current window. The deque will not directly hold the values found within the array, but rather, holds the index of the value in the array. This will make it easier to remove values from the deque when they get dropped from the window.

Algorithm:

• Initialize an integer variable 'maxLength' to store the answer, 'l' to point to the left end of the window and 'r' to point to the right end of the window.
• Calculate prefix sum array 'prefixSum' with an offset of 1 using the elements of 'A'.
• Declare an integer deque 'window' to maintain the sliding window maximum.
• While( l < n and r < n ) proceed as following:
  • Initialize integer variable 'indexDiff' to calculate the length of the current window.
  • While 'window' is not empty and A[window.back()] is less than or equal to A[r], pop back from the deque to maintain the monotonic characteristic.
  • Push the index 'r' into the deque.
  • Calculate the required sum of the current window i.e. max element * length of the window i.e. 'A[windows.front()] x indexDiff' and store this in the integer variable 'expected'.
  • Calculate the actual total values of the window using the prefix sum computer earlier i.e. 'total' = prefixSum[r+1] - prefixSum[l].
  • Calculate the number of operations required which is basically the difference between the expected total sum and the actual sum i.e. 'diff' = 'expected' - 'total'.
  • If the number of operations required is less than 'X' then update 'maxLength' as the maximum of 'maxLength' and 'indexDiff'. And expand the window i.e. 'r++'.
  • Otherwise, shift the whole window.
    • If the element at the front of the queue is 'l' then pop from the front.
    • Increment 'r++' and 'l++'.
• Return 'maxLength' as the final output.