Maximum length of same indexed subarrays from two given arrays satisfying the given condition

Approach 1 (Naive)

A simple solution would be to consider all possible subarrays. Check for each subarray if it satisfies the given condition and print the maximum length subarray among those that meet the given condition.

But the time complexity of this approach would be O(N^3), which is not so impressive. 

Approach 2

Observation: Here, the possible value of K ( length of selected subarray ) follows a monotonic order. Let’s say some array of length ‘x’ satisfies the given condition. Then even after removing a few elements ( i.e., decreasing its length ), this subarray would still meet the given condition. On the other hand, if we extend the subarray’s length by adding elements, some large elements may be added, increasing the total cost. And the subarray might not fulfill the condition.

Using the above observation, we can solve this problem by binary search. We can use binary search to find the possible value of K. To check whether there exists a subarray of length K, we can use maximum segment tree(for getting maximum over a range from array A) and sliding window technique(for getting a sum of subarray from array B).

Algorithm

1. Declare and build a segment tree over array A[ ] to efficiently find maximum value in all possible intervals.

2. Apply binary search on an interval [0, N] to find the subarray’s largest possible value of length K. Initialize lo=0 and hi=N.

a. Compute the value of mid = lo + (hi-lo)/2.

b. Check if a subarray of length ‘mid’ exists, satisfying the given condition. If yes, save the value of mid as one possible answer(in variable ‘mxLength’) and try to get a better answer(set lo=mid+1); otherwise, set hi=mid-1.

Check if there exists a subarray of length ‘mid’ :

i. Calculate the sum of the first subarray of length K by iterating over the array B and find the maximum element by querying the segment tree. Check if this subarray satisfies the given condition, if it does return true.

ii. Iterate from index i=K to i=N-1. 

iii. Use the sliding window technique to find the sum of the current window and segment tree to find the maximum element. And check whether this subarray is valid or not. 

iv. If no subarray satisfies the given condition, then return false.

Program

#include <bits/stdc++.h>
using namespace std;
 
class MaxSegTree{
public:
    /* NOTATIONS
        si - Index of current node in segment tree
             The initial value is passed as 0.
        [ss, se] - Starting and ending indexes of array elements
                   covered under this node of the segment tree.
                   Initial values passed as 0 and n-1.
        [qs, qe] - Starting and ending indexes of the query.
        [us, ue] - Starting and ending indexes of an update query.
    */
    int n;
    vector<int> tree;
 
    //initializing segment tree
    MaxSegTree(int x){
        n = x;
        tree.resize(4*n + 5, 0);
    }
   
    // Function to build segment tree.
    void build(int si, int ss, int se, vector<int>&a){
        // Base Case.
        if(ss == se){
            tree[si] = a[ss];
            return;
        }
 
        // Find Left and Right child's tree index.
        int left = si << 1, right = si << 1 | 1;
 
        // Break the range into two equal parts.
        int mid = ss + ((se-ss) >> 1);
 
        // Recursively Build left and right subtree.
        build(left, ss, mid, a);
        build(right, mid+1, se, a);
 
        // Update max value at current node.
        tree[si] = max(tree[left], tree[right]);
    }
 
    // Function that finds the maximum in given range [qs, qe].
    int getMax(int qs, int qe){
        return _getMax(1, 0, n-1, qs, qe);
    }
 
    // Helper function for 'getMax' function.
    int _getMax(int si, int ss, int se, int qs, int qe){
 
        /****** no intersection ******/
        if(ss > se || ss > qe || se < qs)return 0;
 
        /****** complete overlap ******/
        if(qs <= ss && se <= qe){
            return tree[si];
        }
 
        /****** some overlap ******/
 
        // Find Left and Right child's tree index.
        int left = si << 1, right = si << 1 | 1;
 
        // Break the range into two equal parts.
        int mid = ss + ((se-ss) >> 1);
 
        // Recursively find max in left and right subtree.
        int q1 = _getMax(left, ss, mid, qs, qe);
        int q2 = _getMax(right, mid+1, se, qs, qe);
 
        // Return max of left & right subtree.
        return max(q1, q2);
    }
};
 
 
// This functions checks whether it is possible to have
// a subarray of length K that satisfies mentioned conditions.
bool check(int N, vector<int>&a, vector<int>&b, int C, int K, MaxSegTree &seg){
   
    // First check for the starting window of size K.
    int sum = 0;
    for(int i=0; i<K; i++)sum += a[i];
 
    // Find totalSum and check if it <= C.
    int totalSum = sum*K + seg.getMax(0, K-1);
    if(totalSum <= C)return true;
 
    for(int i=K; i<N; i++){
        // Calculating the sum of next window
        // using sliding window technique.
        sum += (a[i] - a[i-K]);
 
        // Find totalSum and check if it <= C.
        totalSum = sum*K + seg.getMax(i-K+1, i);
 
        // If such subarray is possible return true.
        if(totalSum <= C)return true;
    }
 
    // If no such subarray can be found.
    return false;
}
 
 
// Function that finds the maximum length of subarray
// such that the mentioned condition satisfies.
// max(b[i, i+k]) + sum(a[i, i+k])*k <= C
int solve(int N, vector<int> &a, vector<int> &b, int C){
    // Declare a Segment tree.
    MaxSegTree seg(N);
 
    // Build the Segment tree.
    seg.build(1, 0, N-1, b);
 
    // Initialize mxLength with 0.
    int mxLength = 0;
 
    /****** Use Binary Search to find the max length over subarray of all length.******/
    int lo=0, hi=N;
    while(lo <= hi){
 
        int mid = lo + ((hi-lo)>>1);
 
        // Checking if current length satisfies
        // the given conditions.
        if(check(N, a, b, C, mid, seg)){
           
            // Save the current length.
            mxLength = mid;
 
            // And look for a better answer (larger length).
            lo = mid+1;
        }
        else{
            hi = mid-1;
        }
    }
 
    // Return the final Ans.
    return mxLength;
}
 
 
// Driver Function.
int main(){
    int tt = 1;
    cin >> tt;
    while(tt--){
        int N; cin >> N;
        int C; cin >> C;
 
        vector<int>a(N), b(N);
        for(int i=0; i<N; i++)cin >> a[i];
        for(int i=0; i<N; i++)cin >> b[i];
 
       
        if(N == 0){
            cout << 0 << endl;
            continue;
        }
 
        cout << solve(N, a, b, C) << endl;
    }
    return 0;
}

INPUT

2
5 25
2 1 3 4 5
3 6 1 3 4
8 40
1 2 1 6 5 5 6 1
14 8 15 15 9 10 7 12

OUTPUT

3
3

Time Complexity

In this approach, we have used binary search. We are checking whether the current subarray satisfies the given condition, for each selection by using the max segment tree and sliding window technique. 

So the time complexity of the above approach would be O( N * (logN)² ). 

Space Complexity

The auxiliary space complexity of the program is O( N  ). 

Approach 3

In the above approach, while checking for a valid subarray, a segment tree is used to find the maximum in a range. The segment tree takes O(logN) to find the maximum element in a range.

We can reduce this logN factor by optimizing the method to find the maximum in each subarray of size K. We can use a Monotone Queue such that for each subarray of fixed size, we can get the maximum element in O(1). This would improve the overall time complexity from O( N * (logN)² ) to O( N * logN ). 

Algorithm

The algorithm is the same as from the above approach except for the part where we check the existence of a subarray of length K.

Check if there exists a subarray of length ‘mid’ :

i. Calculate the sum of the first subarray of length K by iterating over the array B and find the maximum element by querying the segment tree. Check if this subarray satisfies the given condition, if it does return true.

ii. Iterate from index i=K to i=N-1. 

iii. Use the monotone queue technique to find the sum of the current window and the segment tree to find the maximum element. And check whether this subarray is valid or not. 

iv. If no subarray satisfies the given condition, then return false.

Program

#include <bits/stdc++.h>
using namespace std;
 
 
// This functions checks whether it is possible to have
// a subarray of length K that satisfies mentioned conditions.
bool check(int N, vector<int>&a, vector<int>&b, int C, int K){
 
    // Declaring a deque for finding maximum element in
    // each window of size k.
    deque<int>dq;
   
    // First check for the starting window of size K.
    int sum = 0;
    for(int i=0; i<K; i++){
        sum += a[i];
 
        while(dq.size() > 0 && b[dq.back()] < b[i]) dq.pop_back();
 
        dq.push_back(i);
    }
 
    // Find totalSum and check if it <= C.
    int totalSum = sum*K + b[dq.front()];
    if(totalSum <= C)return true;
 
    for(int i=K; i<N; i++){
        // Calculating the sum of next window
        // using sliding window technique.
        sum += (a[i] - a[i-K]);
 
        // Remove elements which are before this windwow.
        while(dq.size() > 0 && dq.front() <= i-K) dq.pop_front();
 
        while(dq.size() > 0 && b[dq.back()] < b[i]) dq.pop_back();
 
        dq.push_back(i);
 
        // Find totalSum and check if it <= C.
        totalSum = sum*K + b[dq.front()];
 
        // If such subarray is possible return true.
        if(totalSum <= C)return true;
    }
 
    // If no such subarray can be found.
    return false;
}
 
 
// Function that finds the maximum length of subarray
// such that the mentioned condition satisfies.
// max(b[i, i+k]) + sum(a[i, i+k])*k <= C
int solve(int N, vector<int> &a, vector<int> &b, int C){
    // Initialize mxLength with 0.
    int mxLength = 0;
 
    /****** Use Binary Search to find the max length over subarray of all length.******/
    int lo=0, hi=N;
    while(lo <= hi){
 
        int mid = lo + ((hi-lo)>>1);
 
        // Checking if current length satisfies
        // the given conditions.
        if(check(N, a, b, C, mid)){
           
            // Save the current length.
            mxLength = mid;
 
            // And look for a better answer (larger length).
            lo = mid+1;
        }
        else{
            hi = mid-1;
        }
    }
 
    // Return the final Ans.
    return mxLength;
}
 
 
// Driver Function.
int main(){
    int tt = 1;
    cin >> tt;
    while(tt--){
        int N; cin >> N;
        int C; cin >> C;
 
        vector<int>a(N), b(N);
        for(int i=0; i<N; i++)cin >> a[i];
        for(int i=0; i<N; i++)cin >> b[i];
 
       
        if(N == 0){
            cout << 0 << endl;
            continue;
        }
 
        cout << solve(N, a, b, C) << endl;
    }
    return 0;
}

INPUT

2
5 25
2 1 3 4 5
3 6 1 3 4
8 40
1 2 1 6 5 5 6 1
14 8 15 15 9 10 7 12

OUTPUT

3
3

Time Complexity

The time complexity of update and query in Binary Indexed Tree is O(log(sizeofTree)). Here size of the tree is maxElement of the input array. Therefore time complexity of update and query will be O(log(maxElement)).

The overall time complexity of this approach is O(N * log(maxElement)).

Space Complexity

The auxiliary space complexity of the program is O(maxElement).

FAQs

1. What is a Segment Tree?
   A Segment tree is a data structure that stores information about array segments and allows efficient processing of range queries along with updates.
    
2. What is the time complexity of insertion and query in a Segment Tree?
   The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).
    
3. What is the advantage of Fenwick tree over Segment tree?
   The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.
    
4. What is the disadvantage of the Fenwick tree over the Segment tree?
   We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.

Key Takeaways

Cheers if you reached here!! 

This article discussed an intriguing problem using the Segment tree. Segment tree-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!