- Arrays, Greedy, Hash, subarray-sum, TrueGeek, TrueGeek-2021

Maximum length of subarray with same sum at corresponding indices from two Arrays

Given two arrays A[] and B[] both consisting of N integers, the task is to find the maximum length of subarray [i, j] such that the sum of A[i… j] is equal to B[i… j].Examples:Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.Input: A[] = {1, 1, 0, 1}, B[] = {0, 1, 1, 0}Output: 3Explanation: For (i, j) = (0, 2), sum of A[0… 2] = sum of B[0… 2] (i.e, A[0]+A[1]+A[2] = B[0]+B[1]+B[2] => 1+1+0 = 0+1+1 => 2 = 2). Similarly, for (i, j) = (1, 3), sum of A[1… 3] = B[1… 3]. Therefore, the length of the subarray with equal sum is 3 which is the maximum possible.Input: A[] = {1, 2, 3, 4}, B[] = {4, 3, 2, 1}Output: 4Approach: The given problem can be solved by using a Greedy Approach with the help of unordered maps. It can be observed that for a pair (i, j), if the sum of A[i… j] = sum of B[i… j], then   must hold true. Therefore, a prefix sum array of the difference (A[x] – B[x]) can be created. It can be observed that the repeated values in the prefix sum array represent that the sum of a subarray between the two repeated values must be 0. Hence, keep a track of the maximum size of such subarrays in a variable maxSize which will be the required answer.Below is the implementation of the above approach:C++#include “bits/stdc++.h”using namespace std;  int maxLength(vector& A, vector& B){    int n = A.size();          int maxSize = 0;              unordered_map pre;    int diff = 0;    pre[0] = 0;          for (int i = 0; i < n; i++) {                          diff += (A[i] - B[i]);                  if (pre.find(diff) == pre.end()) {            pre = i + 1;        }                          else {            maxSize = max(maxSize, i - pre + 1);        }    }          return maxSize;}  int main(){    vector A = { 1, 2, 3, 4 };    vector B = { 4, 3, 2, 1 };      cout