Maximum Equality

Moderate
0/80
profile
Contributed by
1 upvote
Asked in company
Deloitte

Problem statement

Ninja has an integer array 'A' of 'N' elements. He is allowed to perform at most 'X' operations on the array.

In one operation he can increment any one element of the array by 1. An operation can be performed repeatedly on the same element.

He wants to know the longest subarray he can obtain in which all the elements of the subarray are equal.

A subarray is a contiguous part of an array.

Example : 
‘N’ = '7'
'X' = 5
The following line contains 'Ai', the 'ith' element from the left.
3 4 8 5 9 6 1

Assuming 0-based indexing, Ninja can perform the operations on 'i'=2, 'A[i]' = 8 once and 'i'=3, 'A[i]' = 5 four times to obtain [3 4 9 9 9 6 1].

Thus, the longest subarray with equal elements that can be obtained is [9, 9, 9] i.e. of length 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two space-separated integers 'N' and 'X', denoting the total number of elements and the maximum number of allowed operations respectively.

The second line of each test case contains 'N' space-separated integers, the elements of the array 'A'.
Output format : 
For each test case, return the length of the longest subarray with the same elements that could be obtained after performing the operations.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
0 <= X < 2^31
1 <= Ai <= 10^9  (0 <= i <= N-1)

The sum of 'N' overall 'T' does not exceed 10^5.

Time Limit: 1 sec
Sample Input 1 :
2
4 2
1 1 2 3
3 0
2 3 4
Sample Output 1 :
3
1
Explanation Of Sample Input 1 :
For test case 1:
Ninja can apply the operation once on A[0] and A[1] to get [2,2,2,3]. Hence, the longest subarray with all elements as the same is A[0:2] i.e. length 3.


For test case 2:
Since all elements are distinct and 'X' = 0 i.e. no operation is allowed. The longest subarray is only a single element.
Sample Input 2 :
2
8 5
1 3 2 2 1 3 4 2
5 3
1 2 1 1 1
Sample Output 2 :
5
4
Hint

 If we can obtain a length 'Y' satisfying the condition, can we obtain a length of 'Y-1'?

Approaches (2)
Binary Search

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.
Time Complexity

O(N*log N)

 

Since we are binary searching, the time complexity of binary search is of the order O(log N) and the checker function traverses the entire array 'A' once, hence the time complexity is of the order O ( N log N ).

Space Complexity

O(N)

 

Since we will be using a deque to find and maintain a sliding window maximum, the space complexity is of the order O(N).

Code Solution
(100% EXP penalty)
Maximum Equality
Full screen
Console