Maximum length of same indexed subarrays

Moderate
0/80
profile
Contributed by
1 upvote
Asked in company
Kellton Tech Solutions Limited

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.

Detailed explanation ( Input/output format, Notes, Images )
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.

Sample Input 1 :

2
6 23
5 19 13 2 4 0 
10 4 7 4 5 14 
5 46
15 18 2 18 3 
14 15 9 19 1

Sample Output 1 :

2
1

Explanation of the Sample Input 1:

In the first test case, 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. 

In the second test case, The max-length subarray will be 1, consider the subarray from 2 to 2 (0-based indexing), and here, the subarray sum of ‘A’ = 2 max element in ‘B’ = 9. Therefore 2*2 + 9 = 13, Which is less than 46. Hence 1 is the final answer.

Sample Input 2 :

2
6 36
4 17 12 16 5 12 
1 10 4 14 13 8 
5 16
3 4 13 0 9 
19 16 16 17 19

Sample Output 2 :

1
0
Hint

 Can we check for each length?

Approaches (2)
Brute force

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

O(N ^ 2*log(N)), where ‘N’ is the number given.

 

Since in the worst case, we are traversing the whole array for each length, the final time Complexity will be O(N ^ 2). 

Space Complexity

O(N), where ‘N’ is the number given.
 

Since we are using heaps to store data hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Maximum length of same indexed subarrays
Full screen
Console