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:
Input: A[] = {1, 1, 0, 1}, B[] = {0, 1, 1, 0}
Output: 3
Explanation: 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: 4
Approach: 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 ![\sum_{x=i}^{j} (A[x] - B[x]) = 0](https://neveropen.co.uk/wp-content/uploads/2023/11/neveropen_quicklatex.com-1c4535a10b9252908866db5901db213c_l3.png "Rendered by QuickLaTeX.com")
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++
// C++ program for the above approach#include "bits/stdc++.h"using namespace std;// Function to find maximum length of subarray// of array A and B having equal sumint maxLength(vector<int>& A, vector<int>& B){ int n = A.size(); // Stores the maximum size of valid subarray int maxSize = 0; // Stores the prefix sum of the difference // of the given arrays unordered_map<int, int> pre; int diff = 0; pre[0] = 0; // Traverse the given array for (int i = 0; i < n; i++) { // Add the difference of the // corresponding array element diff += (A[i] - B[i]); // If current difference is not present if (pre.find(diff) == pre.end()) { pre = i + 1; } // If current difference is present, // update the value of maxSize else { maxSize = max(maxSize, i - pre + 1); } } // Return the maximum length return maxSize;}// Driver Codeint main(){ vector<int> A = { 1, 2, 3, 4 }; vector<int> B = { 4, 3, 2, 1 }; cout << maxLength(A, B); return 0;} |
Java
// Java program for the above approachimport java.util.HashMap;class GFG { // Function to find maximum length of subarray // of array A and B having equal sum public static int maxLength(int[] A, int[] B) { int n = A.length; // Stores the maximum size of valid subarray int maxSize = 0; // Stores the prefix sum of the difference // of the given arrays HashMap<Integer, Integer> pre = new HashMap<Integer, Integer>(); int diff = 0; pre.put(0, 0); // Traverse the given array for (int i = 0; i < n; i++) { // Add the difference of the // corresponding array element diff += (A[i] - B[i]); // If current difference is not present if (!pre.containsKey(diff)) { pre.put(diff, i + 1); } // If current difference is present, // update the value of maxSize else { maxSize = Math.max(maxSize, i - pre.get(diff) + 1); } } // Return the maximum length return maxSize; } // Driver Code public static void main(String args[]) { int[] A = { 1, 2, 3, 4 }; int[] B = { 4, 3, 2, 1 }; System.out.println(maxLength(A, B)); }}// This code is contributed by gfgking. |
Python3
# python program for the above approach# Function to find maximum length of subarray# of array A and B having equal sumdef maxLength(A, B): n = len(A) # Stores the maximum size of valid subarray maxSize = 0 # Stores the prefix sum of the difference # of the given arrays pre = {} diff = 0 pre[0] = 0 # Traverse the given array for i in range(0, n): # Add the difference of the # corresponding array element diff += (A[i] - B[i]) # If current difference is not present if (not (diff in pre)): pre = i + 1 # If current difference is present, # update the value of maxSize else: maxSize = max(maxSize, i - pre + 1) # Return the maximum length return maxSize# Driver Codeif __name__ == "__main__": A = [1, 2, 3, 4] B = [4, 3, 2, 1] print(maxLength(A, B))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find maximum length of subarray // of array A and B having equal sum public static int maxLength(int[] A, int[] B) { int n = A.Length; // Stores the maximum size of valid subarray int maxSize = 0; // Stores the prefix sum of the difference // of the given arrays Dictionary<int, int> pre = new Dictionary<int, int>(); int diff = 0; pre.Add(0, 0); // Traverse the given array for (int i = 0; i < n; i++) { // Add the difference of the // corresponding array element diff += (A[i] - B[i]); // If current difference is not present if (!pre.ContainsKey(diff)) { pre.Add(diff, i + 1); } // If current difference is present, // update the value of maxSize else { maxSize = Math.Max(maxSize, i - pre[(diff)] + 1); } } // Return the maximum length return maxSize; }// Driver Codepublic static void Main(){ int[] A = { 1, 2, 3, 4 }; int[] B = { 4, 3, 2, 1 }; Console.Write(maxLength(A, B));}}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach // Function to find maximum length of subarray // of array A and B having equal sum const maxLength = (A, B) => { let n = A.length; // Stores the maximum size of valid subarray let maxSize = 0; // Stores the prefix sum of the difference // of the given arrays let pre = {}; let diff = 0; pre[0] = 0; // Traverse the given array for (let i = 0; i < n; i++) { // Add the difference of the // corresponding array element diff += (A[i] - B[i]); // If current difference is not present if (!(diff in pre)) { pre = i + 1; } // If current difference is present, // update the value of maxSize else { maxSize = Math.max(maxSize, i - pre + 1); } } // Return the maximum length return maxSize; } // Driver Code let A = [1, 2, 3, 4]; let B = [4, 3, 2, 1]; document.write(maxLength(A, B));// This code is contributed by rakeshsahni.</script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
