Maximum length of same indexed subarrays
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

Question

Maximum length of same indexed subarrays

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.

Accepted Answer

Binary Search

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.

Space Complexity: O(1)Explanation:

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

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

Time Complexity: O(1)Explanation:

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

Since we are binary searching over the length of the array and using the helper function, the overall time complexity will be O(N*log ^ 2(N)).

Java (SE 1.8)

/*

	Time Complexity : O(N * log^2(N))

	Space Complexity : O(N)



	Where 'N' is the size of the array.

*/



import java.util.Queue;

import java.util.ArrayList;

import java.util.Comparator;

import java.util.PriorityQueue;

import java.util.Collections;



class Pair {

	public int x, y;



	Pair(int x, int y) {

		this.x = x;

		this.y = y;

	}

}



// Implements Comparator interface for max-heap

class PqComparator implements Comparator {

	public int compare(Pair pair1, Pair pair2) {

		if (pair1.x < pair2.x) {

			return 1;

		}



		if (pair1.x == pair2.x) {

			return 0;

		}

		return -1;

	}

}



public class Solution {



	private static boolean isPossible(ArrayList a, ArrayList b, ArrayList prefixSum, int c, int k) {



		int n = a.size();

		PriorityQueue que =  new PriorityQueue(new PqComparator());



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

			Pair temp = new Pair(b.get(i), i);

			que.add(temp);

		}



		boolean flag = false;



		if (k == n) {

			int mxElement = que.peek().x;

			int subarraySum = prefixSum.get(k - 1);

			if ((mxElement + (subarraySum * k)) <= c ) {

				return true;

			}

		}



		for (int i = k ; i < n ; i++) {



			int mxElement = que.peek().x;

			int subarraySum = prefixSum.get(i - 1);

			if (i - 1 - k >= 0) {

				subarraySum -= prefixSum.get(i - 1 - k);

			}



			if ((mxElement + (subarraySum * k)) <= c) {

				return true;

			}



			while (que.size() > 0 && que.peek().y <= i - k) {

				que.poll();

			}



			Pair temp = new Pair(b.get(i), i);

			que.add(temp);

		}

		return false;

	}





	public static int maxLengthArray(ArrayList a, ArrayList b, int c) {



		int n = a.size();



		ArrayList prefixSum = new ArrayList(n);



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



			if (i == 0) {

				prefixSum.add(a.get(i));



			} else {

				prefixSum.add(a.get(i) + prefixSum.get(i - 1));

			}

		}



		int low = 0, high = n ;

		int ans = 0;



		while (low <= high) {



			int mid = (low + high) / 2 ;



			if (mid == 0 || isPossible(a, b, prefixSum, c, mid)) {

				ans = mid;

				low = mid + 1;

			} else {

				high = mid - 1;

			}

		}



		return ans;

	}

}

Python (3.5)

'''Time Complexity : O(N * log ^ 2(N))

    Space Complexity : O(N)



    Where 'N' is the size of the array.'''







import heapq







def isPossible(a, b, prefixSum, c, k):

    n = len(a)

    que = []





    for i in range(k):

        #pushing the ith value and its index.

        heapq.heappush(que, [-b[i], i])



    flag = False

    if k == n:

        mxElement = -que[0][0]

        subarraySum = prefixSum[k - 1]



        # Checking if the given condition is satisfied.

        if (mxElement + (subarraySum * k) <= c):

            flag = True



    for i in range(k, n):

        mxElement = -que[0][0]

        subarraySum = prefixSum[i - 1]

        if(i - 1 - k >= 0):

            subarraySum -= prefixSum[i - 1 - k]



        # Checking if the given condition is satisfied.

        if((mxElement + (subarraySum * k)) <= c):

            flag = True

            break

            



        while (len(que) > 0 and que[0][1] <= i - k):

            heapq.heappop(que)

        heapq.heappush(que, [-b[i], i])



        

    return flag





def maxLengthArray(a, b, c):

    n = len(a)

    prefixSum = [0 for i in range(n)]



    for i in range(n):

        if i == 0:

            prefixSum[i] = a[i]

        else:

            prefixSum[i] = a[i] + prefixSum[i-1]

    low, high = 0, n

    ans = 0

    while(low <= high):

        mid = (low + high) // 2

        if mid == 0 or isPossible(a, b, prefixSum, c, mid):

            ans = mid

            low = mid + 1

        else:

            high = mid - 1

    return ans

C++ (g++ 5.4)

/*

	Time Complexity : O(N * log ^ 2(N))

	Space Complexity : O(N)



	Where 'N' is the size of the array.

*/



#include 



bool isPossible(vector &a, vector &b, vector &prefixSum, int c, int k)

{



	int n = a.size();



	priority_queue> que;



	for (int i = 0 ; i < k ; i++)

	{

		// pushing the ith value and its index.

		que.push({b[i], i});

	}



	bool flag = false;	

	if (k == n)

	{

		int mxElement = que.top().first;

		int subarraySum = prefixSum[k - 1];



		// Checking if the given condition is satisfied.

		if ((mxElement + (subarraySum * k)) <= c )

		{

			flag = true;

		}

	}



	for (int i = k ; i < n ; i++)

	{

		int mxElement = que.top().first;

		int subarraySum = prefixSum[i - 1];

		if (i - 1 - k >= 0)

		{

			subarraySum -= prefixSum[i - 1 - k];

		}



		// Checking if the given condition is satisfied.

		if ((mxElement + (subarraySum * k)) <= c)

		{

			flag = true;

			break;

		}



		while (!que.empty() and que.top().second <= i - k)

		{

			que.pop();

		}



		que.push({b[i], i});

	}



	return flag;

}



int maxLengthArray(vector &a, vector &b, int c)

{

	int n = a.size();



	vector prefixSum(n, 0);



	for (int i = 0 ; i < n ; i++)

	{

		if (i == 0)

		{

			prefixSum[i] = a[i];

		}

		else

		{

			prefixSum[i] = a[i] + prefixSum[i - 1];

		}

	}



	int low = 0, high = n ;

	int ans = 0;



	while (low <= high)

	{

		int mid = (low + high) / 2 ;



		if (mid == 0 or isPossible(a, b, prefixSum, c, mid))

		{

			ans = mid;

			low = mid + 1;

		}

		else

		{

			high = mid - 1;

		}

	}



	return ans;

}

Accepted Answer

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.

Space Complexity: O(1)Explanation:

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

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

Time Complexity: O(1)Explanation:

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).