Last Updated: 15 Jun, 2021

Maximum length of same indexed subarrays

Moderate

Asked in company

Solve now

Problem statement

Given two arrays ‘A’ and ‘B’ and an integer ‘C’, the task is to find the maximum possible length, say K, of the same indexed subarrays such that the sum of the maximum element in the K-length subarray in ‘B’ with the product between K and sum of the K-length subarray in ‘A’ does not exceed ‘C’.

More Formally you have to find the maximum length subarray, which starts and end at the same point in ‘A’ and ‘B’, and the sum of, maximum element of ‘B’ in that subarray, with the product of the length of the subarray and sum of a subarray in ‘A’ is less than or equal to ‘C’.

For example

Given:
‘N’ = 6, ‘C’ = 23
‘A’[] = {5, 19, 13, 2, 4, 0} 
‘B’[] = {10, 4, 7, 4, 5, 14}
The max-length subarray will be 2, consider the subarray from 3 to 4 (0-based indexing) and here, the subarray sum of ‘A’ = 6 max element in ‘B’ = 5. Therefore 6*2 + 5 = 17, Which is less than 23. Hence 2 is the final answer.

If there are multiple answers, you can choose any subarray.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N,’ where ‘N’ is the number of elements of the array and ‘C’ where ‘C’ is the given integer.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output Format :

For each test case, You are supposed to return an integer that denotes the maximum length subarray.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘N’ <= 5000
0 <= 'ARR[i]’ <= 10 ^ 6

Time Limit: 1sec.

Solve now

Approaches

01 Approach

The idea is to brute force to find the maximum length subarray which satisfies the given condition.

The steps are as follows:
Maintain a variable ‘ans’, which stores the final answer.
Loop from 1 to ‘N’ Using 'i:
'i' denotes the length of the subarray, which may satisfy the condition.
Maintain an array ‘prefixSum’ which stores the prefix sum of the array ‘a’.
To check whether the subarray of length 'i' satisfies the condition, we use a helper function, ‘isPossible’:
- ‘isPossible’ takes array ‘A’, ‘B’,’prefixSum’ and integer ‘C’, and length 'k' as input parameters.
- ‘isPossible’ finds if there exists any subarray, of size 'k' which satisfies the given condition.
- ‘isPossible’ considers all arrays of the size given in the input parameter, using priority queue ‘que’.
- We maintain a boolean variable ‘flag’ which denotes, if there exists a subarray of size 'k' which satisfies the condition.
- We first push the first 'k' elements in the ‘que’, then for each iteration from 'k' to ‘N’.
- Then loop from 'k' to ‘N’ using ‘i’ to check whether the condition, maximum element in the ‘B’ array and the product of the subarray in ‘A’ with 'k' is less than ‘C’, If we find any such array we mark ‘flag’ as true.
- Remove the elements which are not in the 'k' range by popping from ‘que’, which can be checked via, ‘que.top().second’ <= ‘i’ - ‘k’, where ‘que.top().second’ denotes the index of the element at the top of the ‘que’
- Return ‘flag’ which denotes if there exists a subarray of size ‘k’ satisfying the condition.
If ‘isPossible’ returns true we store 'k' as the ‘ans’.
Return ‘ans’ as the final answer.

Solve now

02 Approach

The idea is to optimize the above approach using binary search, since for some length ‘K’, if ‘K’ is possible, then obviously ‘K - 1’ will also be possible. Therefore we binary search over the length of the array.

The steps are as follows:

Maintain a variable ‘ans’, which stores the final answer.
Maintain a variable ‘low’ and ‘high’, for binary searching across the length of the array.
Maintain an array ‘prefixSum’ which stores the prefix sum of the array ‘a’.
While ‘low’ is less than equal to ‘high’:
- ‘mid’ is the average of ‘low’ and ‘high’.
- To check whether the subarray of length 'mid' satisfies the condition, we use a helper function, ‘isPossible’:
  - ‘isPossible’ takes array ‘A’, ‘B’,’prefixSum’ and integer ‘C’, and length 'k' as input parameters.
  - ‘isPossible’ finds if there exists any subarray, of size 'k' which satisfies the given condition.
  - ‘isPossible’ considers all arrays of the size given in the input parameter, using priority queue ‘que’.
  - We maintain a boolean variable ‘flag’ which denotes, if there exists a subarray of size 'k' which satisfies the condition.
  - We first push the first 'k' elements in the ‘que’, then for each iteration from 'k' to ‘N’.
  - Then loop from 'k' to ‘N’ using ‘i’ to check whether the condition, maximum element in the ‘B’ array and the product of the subarray in ‘A’ with 'k' is less than ‘C’, If we find any such array we mark ‘flag’ as true.
  - Remove the elements which are not in the 'k' range by popping from ‘que’, which can be checked via, ‘que.top().second’ <= ‘i’ - ‘k’, where ‘que.top().second’ denotes the index of the element at the top of the ‘que’
  - Return ‘flag’ which denotes if there exists a subarray of size ‘k’ satisfying the condition.
- If ‘isPossible’ returns true, we store ‘mid’ as the ‘ans’, and assign ‘mid + 1’ to low. Else, assign ‘mid-1’ to ‘high’.
Return ‘ans’ as the final answer.

Solve now