Maximize the sum
You are given two sorted arrays of distinct integers, ‘ARR1’ and ‘ARR2’. If you find a common element in both arrays, you can switch from one array to another.

Your task is to find a path through the intersections i.e common integers of ‘ARR1’ and ‘ARR2’, that produces maximum sum and return that maximum sum as the answer.

For example:

Let ‘ARR1’ = [1, 5, 10, 15, 20] and ‘ARR2’ = [2, 4, 5, 9, 15] In this example, common points are 5, 15. First, we start with ARR2 and take the sum till 5 (i.e. sum = 11). Then we will switch to ‘ARR1’ at element 10 and take the sum till 15. So sum = 36. Now no element is left in ‘ARR2’ after 15, so we will continue in array 1. Hence sum is 56. And the path is 2 - 4 - 5 - 10 - 15 - 20.

Input Format:

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains two space-separated integers, ‘N’ and ‘M,’ representing the number of elements in ‘ARR1’ and ‘ARR2’. The second line of each test case contains ‘N’ single space-separated integers denoting the values of ‘ARR1’. The third line of each test case contains ‘M’ single space-separated integers denoting the values of ‘ARR2’.

Output Format :

For each test case, print the maximum sum value. Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Maximize the sum

You are given two sorted arrays of distinct integers, ‘ARR1’ and ‘ARR2’. If you find a common element in both arrays, you can switch from one array to another.

Your task is to find a path through the intersections i.e common integers of ‘ARR1’ and ‘ARR2’, that produces maximum sum and return that maximum sum as the answer.

For example:

Let ‘ARR1’ = [1, 5, 10, 15, 20]  and ‘ARR2’ = [2, 4, 5, 9, 15]
In this example, common points are 5, 15.

First, we start with ARR2 and take the sum till 5 (i.e. sum = 11). Then we will switch to ‘ARR1’ at element 10 and take the sum till 15. So sum = 36. Now no element is left in ‘ARR2’ after 15, so we will continue in array 1. Hence sum is 56. And the path is 2 -> 4 -> 5 -> 10 -> 15 -> 20.

array

Input Format:

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M,’ representing the number of elements in ‘ARR1’ and ‘ARR2’.

The second line of each test case contains ‘N’ single space-separated integers denoting the values of ‘ARR1’.

The third line of each test case contains ‘M’ single space-separated integers denoting the values of ‘ARR2’.

Output Format :

For each test case, print the maximum sum value.

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 100
1 <= ‘N’, ’M’ <= 10^4
1 <= ‘ARR1[i]’, ‘ARR2[j]’ <= 10^5

Time Limit: 1 second

Accepted Answer

Recursive

In this problem, our primary focus is on the common elements i.e. an element that is present in both the arrays. Then, we have to decide whether we have to make a switch. So for that, first we store all the elements of ‘ARR1’ and ‘ARR2’ into ‘MAP1’ and ‘MAP2’ respectively.

Now we call our ‘maximiseSumHelper’ function. We call this function for both cases i.e starting with ‘ARR1’ and starting with ‘ARR2’. Then we return the maximum of the two cases. During the recursive call, if we find a common element that is present in both the arrays, then we have two options at that point i.e. either we can switch to the other array or ontinue with the same array.

Here is the algorithm :

We declare two HashMaps i.e. ‘MAP1’ and ‘MAP2’ in which we store elements of ‘ARR1’ and ‘ARR2’ respectively.
Return max(maximiseSumHelper(‘ARR1’, ‘ARR2’, 1, 0),maximiseSumHelper(‘ARR1’, ‘ARR2’, 2, 0))

maximiseSumHelper(‘ARR1’, ‘ARR2’, ‘currArr’, ‘currInd’) function works as follows:

Base Case:
- If the ‘currInd’ is greater than or equal to the current array's size, we have reached the end of the array. So we return 0.
We declare a variable ‘maximumSum’ in which we store our answer.
If ‘currArr’ == 1:
- ‘maximumSum’ = ‘ARR1[‘currInd’]’ + maximiseSumHelper(‘ARR1’, ‘ARR2’, ‘currArr’, ‘currInd’ + 1)
- If ‘ARR1[currInd]’ is present in both the arrays:
  - Now we take both the cases i.e. we can either switch from the current array to the other array or we will continue with the same array.
Else
- ‘maximumSum’ = ‘ARR2[‘currInd’]’ + ‘maximiseSumHelper(‘ARR1’, ‘ARR2’, ‘currArr’, ‘currInd’ + 1)
- If ‘ARR2[currInd]’ is present in both the arrays:
  - Again, we take both cases i.e. we can switch from the current array to the other array or we will continue with the same array.
Finally, return ‘maximumSum’.

Space Complexity: O(n)Explanation:

O(max(N, M)) where 'N’ and ‘M’ denote the number of elements in ‘ARR1’ and ‘ARR2’, respectively.

Because we use hashMaps to store all the elements of ‘ARR1’ and ‘ARR2’. And the recursion stack also goes up to max(N, M).

Let’s take an example: Let ‘ARR1’ = [1, 2, 3] and ‘ARR2’ = [4, 5, 6]. In this example, there is no common point so our recursive function first goes to all the elements of ‘ARR1’, returns an answer, and then it goes to all the elements.

Time Complexity: O(2^n)Explanation:

O(2 ^ max(N, M)) where ‘N’ and ‘M’ denote the number of elements in ‘ARR1’ and ‘ARR2’, respectively.

Because in the worst case we have at most 2 recursive calls at every index.

Let’s take an example:

If both the arrays contain the same values, let ‘ARR1’ = [1, 2, 3, 4] and ‘ARR2’ = [1, 2, 3, 4]. So, in this case, at every index, we have two choices i.e either we can switch to the other array or we can continue with the same array.

Accepted Answer

Memoization

In our previous approach, we use a recursive solution for solving this problem. But there are a lot of repetitive calculations in our previous approach. Let's assume a case in which both the arrays contain the same values, say ‘ARR1’ = [1, 2, 3, 4] and ‘ARR2’ = [1, 2, 3, 4].

So in this case at every index, we have two choices i.e either we can switch to the other array or we can continue with the same array. So here we can use memoization to get rid of repetitive calls.

Here is the algorithm :

This approach is similar to the previous approach with some additions. In this approach, we use the ‘memo’ array.

Here ‘memo[0][j]’ stores the maximum sum till now when ‘ARR1’ has ‘i’ elements.

And ‘memo[1][j]’ stores the maximum sum till now when ‘ARR2’ has ‘j’ elements.

maximiseSumHelper(‘ARR1’, ‘ARR2’, ‘currArr’, ‘currInd’, ’memo’) function is the same as described in the previous approach with some additions:

If we already have calculated the result for ‘memo[i][j]’ i.e. ‘memo[‘currArr’][‘currInd’]’ != -1’
- Return memo[‘currArr’][‘currInd’]’ .
We declare a variable ‘maximumSum’ in which we store our answer.
If ‘currArr’ == 1
- We calculate ‘maximumSum’ as stated in the previous approach as set ‘memo[0][currInd]’ = ‘maximumSum’ .
Else:
- We calculate ‘maximumSum’ as stated in the previous approach as set ‘memo[1][currInd]’ = ‘maximumSum’.

Space Complexity: O(n)Explanation:

O(max(N, M)) where ‘N’ and ‘M’ denote the number of elements in ‘ARR1’ and ‘ARR2’, respectively.

We are using hashMaps to store all the elements of ‘ARR1’ and ‘ARR2’. Also, we are using a ‘memo’ array to store the already calculated results. The size of ‘memo’ is 2 * max(N, M). So, the overall space complexity is O(max(N, M).

Time Complexity: O(n)Explanation:

O(N + M) where ‘N’ and ‘M’ denote the number of elements in ‘ARR1’ and ‘ARR2’, respectively.

In the worst case, we have at most O(‘N’ + ‘M’) recursive calls because we are using a ‘memo’ array to store the already calculated results. So that if there is any repeated recursive call, for that call we already have a result that is stored in the ‘memo’ array.

C++ (g++ 5.4)

/*



    Time complexity: O(N + M))

    Space complexity: O(max(N, M)) 



    Where 'N' and 'M' denote the number of elements in 

    ARR1 and ARR2 respectively.



*/



#include 



int maximiseSumHelper(vector &arr1, vector &arr2, unordered_map &map1, unordered_map &map2, int currArr, int currInd, vector> &memo)

{

    // If we reach end of arr1, return 0

    if (currArr == 1 && currInd >= arr1.size())

    {

        return 0;

    }



    // If we reach end of arr2, return 0

    if (currArr == 2 && currInd >= arr2.size())

    {

        return 0;

    }



    // If current array is arr1 and result of recursive call is pre-computed

    if (currArr == 1 && memo[0][currInd] != -1)

    {

        return memo[0][currInd];

    }



    // If current array is arr2 and result of recursive call is pre-computed

    if (currArr == 2 && memo[1][currInd] != -1)

    {

        return memo[1][currInd];

    }



    int maximumSum = 0;



    // If current array is arr1

    if (currArr == 1)

    {

        maximumSum = arr1[currInd] + maximiseSumHelper(arr1, arr2, map1, map2, currArr, currInd + 1, memo);



        // If current element is present in both arrays

        if (map1.find(arr1[currInd]) != map1.end() && map2.find(arr1[currInd]) != map2.end())

        {

            maximumSum = max(maximumSum, arr1[currInd] + maximiseSumHelper(arr1, arr2, map1, map2, 2, map2[arr1[currInd]] + 1, memo));

        }



        // Store result in memo table

        memo[0][currInd] = maximumSum;



        return memo[0][currInd];

    }



    // If current array is arr2

    else

    {

        maximumSum = arr2[currInd] + maximiseSumHelper(arr1, arr2, map1, map2, currArr, currInd + 1, memo);



        // If current element is present in both arrays

        if (map1.find(arr2[currInd]) != map1.end() && map2.find(arr2[currInd]) != map2.end())

        {

            maximumSum = max(maximumSum, arr2[currInd] + maximiseSumHelper(arr1, arr2, map1, map2, 1, map1[arr2[currInd]] + 1, memo));

        }



        // Store result in memo table

        memo[1][currInd] = maximumSum;

        return memo[1][currInd];

    }

}



int maximiseSum(vector &arr1, vector &arr2, int n, int m)

{

    // Initialize hash map to store elements of arrays

    unordered_map map1;

    unordered_map map2;



    // Initialze 2-D array to store results of recursive calls

    vector> memo(2, vector(max(n, m), -1));



    // Adding index of elements of arr1 to map1

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

    {

        map1[arr1[i]] = i;

    }



    // Adding index of elements of arr2 to map2

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

    {

        map2[arr2[i]] = i;

    }



    // Recursive function

    return max(maximiseSumHelper(arr1, arr2, map1, map2, 1, 0, memo), maximiseSumHelper(arr1, arr2, map1, map2, 2, 0, memo));

}

Python (3.5)

'''



    Time complexity: O(N + M))

    Space complexity: O(max(N, M)) 



    Where N and M denote the number of elements in 

    ARR1 and ARR2 respectively.



'''



def maximiseSumHelper(arr1, arr2, map1, map2, currArr, currInd,  memo): 



    # If we reach end of arr1, return 0

    if (currArr == 1 and currInd >= len(arr1)): 

        return 0

    

    # If we reach end of arr2, return 0

    if (currArr == 2 and currInd >= len(arr2)): 

        return 0

    

    # If current array is arr1 and result of recursive call is pre-computed

    if (currArr == 1 and memo[0][currInd] != -1): 

        return memo[0][currInd]

    

    # If current array is arr2 and result of recursive call is pre-computed

    if (currArr == 2 and memo[1][currInd] != -1): 

        return memo[1][currInd]

    



    maximumSum = 0



    # If current array is arr1

    if (currArr == 1): 

        maximumSum = arr1[currInd] + maximiseSumHelper(arr1, arr2, map1, map2, currArr, currInd + 1, memo)



        # If current element is present in both arrays

        if (arr1[currInd] in map1 and arr1[currInd] in map2):

            maximumSum = max(maximumSum, arr1[currInd] + maximiseSumHelper(arr1, arr2, map1, map2, 2, map2[arr1[currInd]] + 1, memo))

        

        # Store result in memo table

        memo[0][currInd] = maximumSum

        return memo[0][currInd]



    # If current array is arr2

    else: 

        maximumSum = arr2[currInd] + maximiseSumHelper(arr1, arr2, map1, map2, currArr, currInd + 1, memo)



        # If current element is present in both arrays

        if (arr2[currInd] in map1 and arr2[currInd] in map2):

            maximumSum = max(maximumSum, arr2[currInd] + maximiseSumHelper(arr1, arr2, map1, map2, 1, map1[arr2[currInd]] + 1, memo))

        

        # Store result in memo table

        memo[1][currInd] = maximumSum

        return memo[1][currInd]





def maximiseSum(arr1, arr2, n, m): 



    # Initialize hash map to store elements of arrays

    map1 = {}

    map2 = {}

    

    # Initialze 2-D array to store results of recursive calls

    memo = [[-1] * max(n, m) for _ in range(2)]



    # Adding index of elements of arr1 to map1

    for i in range(n):

        map1[arr1[i]] = i

    

    # Adding index of elements of arr2 to map2

    for i in range(m):

        map2[arr2[i]] = i

    

    # Recursive function

    return max(maximiseSumHelper(arr1, arr2, map1, map2, 1, 0, memo), maximiseSumHelper(arr1, arr2, map1, map2, 2, 0, memo))

Accepted Answer

Two Pointer Approach

In this problem, our primary focus is on the common elements, i.e., elements present in both the arrays. Then, we have to decide whether we have to make a switch. So for that, we take two variables‘ currSumArr1’ and ‘currSumArr2’ in which we store the sum of all the elements between the current common element and the last common element of ‘ARR1’ and ‘ARR2’, respectively. And when we encounter a common element, we compare the accumulated sum in both paths, and we pick the bigger one. Then add this into ‘maximumSum.’

Here is the algorithm :

We declare two variables, ‘i’ and ‘j,’ in which we store the current index of ‘ARR1’ and ‘ARR2’, respectively, and declare a ‘maximumSum’ in which we store our answer.
We declare two variables, ‘currSumArr1’ and ‘currSumArr2’, in which we store the sum of all the elements between the current common element and the last common element of ‘ARR1’ and ‘ARR2’, respectively.
We run a loop while ‘i’ < ‘ARR1.Length’ and ‘j’ < ‘ARR2.Length’:
- If ‘ARR1[i]' < ‘ARR2[j]’:
  - ‘currSumArr1’ += ‘ARR1[i]’
  - ‘i++’
- Else if ‘ARR1[i]' > ‘ARR2[j]’:
  - ‘currSumArr2’ += ‘ARR2[j]’
  - ‘J++’
- Else, when we get the common element, we add the maximum of ‘currSumArr1’ and ’currSumArr2’ to our resultant answer:
  - ‘maximumSum’ += max(‘currSumArr1’,’currSumArr2’)
  - ‘maximumSum’ += ‘ARR1[i]’
  - ‘currSumArr1’ = 0 , ‘currSumArr2’ = 0
  - ‘i’ += 1
  - ‘j’ += 1
We run a loop while ‘i’ < ‘ARR1.Length’:
- ‘currSumArr1’ += ‘ARR1[i]’
- ‘i++’
We run a loop while ‘j’ < ‘ARR2.Length’
- ‘currSumArr2’ += ‘ARR2[j]’
- ‘j++’
‘maximumSum’ += max(‘currSumArr1’,’currSumArr2’).
Finally, we return ‘maximumSum’.

Space Complexity: O(1)Explanation:

O(1)

Since we are not taking any extra space.

Time Complexity: O(n)Explanation:

O(max(N, M)) where ‘N’ and ‘M’ denote the number of elements in ‘ARR1’ and ‘ARR2’, respectively.

For finding the path that produces the maximum sum, we have to iterate once through ‘ARR1’ and ‘ARR2’.

Python (3.5)

'''



    Time complexity: O(max(N, M))

    Space complexity: O(1)



    Where N and M denote the number of elements in 

    ARR1 and ARR2 respectively.

    

'''



def maximiseSum(arr1, arr2, n, m): 



    # Variable to store index of arr1 and arr2

    maximumSum = 0

    i = 0 

    j = 0

    currSumArr1 = 0

    currSumArr2 = 0

    

    # Iterate while i    while (i < n and j < m): 

        

        # If current element of arr1 is smaller than arr2, increment 'i'

        # and add current element currSumArr1 

        if (arr1[i] < arr2[j]): 

            currSumArr1 += arr1[i]

            i += 1

        

        # If current element of arr2 is smaller than arr1, increment 'j'

        # and add current element currSumArr2 

        elif (arr1[i] > arr2[j]): 

            currSumArr2 += arr2[j]

            j += 1



        # Otherwise, update maximumSum

        else: 

            maximumSum += max(currSumArr1,currSumArr2)

            maximumSum += arr1[i]

            currSumArr1 = 0

            currSumArr2 = 0

            i += 1

            j += 1

    

    

    while (i < n): 

       currSumArr1 += arr1[i]

       i += 1

    

    while (j < m): 

      currSumArr2 += arr2[j]

      j += 1

    

    

    maximumSum += max(currSumArr1, currSumArr2)

    

    return maximumSum

Java (SE 1.8)

/*

    Time complexity: O(max(M, N))

    Space complexity: O(1) 



     Where 'M' and 'N' is the number of elements in ARR1 and ARR2 respectively.

 */



public class Solution

{

    public static int maximiseSum(int arr1[], int arr2[], int n, int m)

    {

        // Variable to store index of arr1 and arr2

        int i = 0, j = 0;



        int currSumArr1 = 0, currSumArr2 = 0, maximumSum = 0;



        // Iterate while i        while (i < n && j < m)

        {

            /*

            If current element of arr1 is smaller than arr2, increment 'i'

            and add current element currSumArr1

            */

            if (arr1[i] < arr2[j])

            {



                currSumArr1 += arr1[i];

                i++;

            }



            /*

            If current element of arr2 is smaller than arr1, increment 'j'

            and add current element currSumArr2

            */

            else if (arr1[i] > arr2[j])

            {

                currSumArr2 += arr2[j];

                j++;

            }



            // Otherwise, update maximumSum

            else

            {

                maximumSum += Math.max(currSumArr1, currSumArr2);

                maximumSum += arr1[i];

                currSumArr1 = 0;

                currSumArr2 = 0;

                i++;

                j++;

            }

        }



        while (i < n)

        {

            currSumArr1 += arr1[i];

            i++;

        }



        while (j < m)

        {

            currSumArr2 += arr2[j];

            j++;

        }



        maximumSum += Math.max(currSumArr1, currSumArr2);



        return maximumSum;

    }

}

C++ (g++ 5.4)

/*

    Time complexity: O(max(N, M))

    Space complexity: O(1)



    Where 'N' and 'M' denote the number of elements in

    ARR1 and ARR2 respectively.

*/



int maximiseSum(vector &arr1, vector &arr2, int n, int m)

{

    int maximumSum = 0;



    // Variable to store index of arr1 and arr2

    int i = 0, j = 0;



    int currSumArr1 = 0, currSumArr2 = 0;



    // Iterate while i    while (i < n && j < m)

    {

        /*

        If current element of arr1 is smaller than arr2, increment 'i'

        and add current element currSumArr1

        */

        if (arr1[i] < arr2[j])

        {

            currSumArr1 += arr1[i];

            i++;

        }



        /*

        If current element of arr2 is smaller than arr1, increment 'j'

        and add current element currSumArr2

        */

        else if (arr1[i] > arr2[j])

        {

            currSumArr2 += arr2[j];

            j++;

        }



        // Otherwise, update maximumSum

        else

        {

            maximumSum += max(currSumArr1, currSumArr2);

            maximumSum += arr1[i];

            currSumArr1 = 0;

            currSumArr2 = 0;

            i++;

            j++;

        }

    }



    while (i < n)

    {

        currSumArr1 += arr1[i];

        i++;

    }



    while (j < m)

    {

        currSumArr2 += arr2[j];

        j++;

    }



    maximumSum += max(currSumArr1, currSumArr2);



    return maximumSum;

}

You are given two sorted arrays of distinct integers, ‘ARR1’ and ‘ARR2’. If you find a common element in both arrays, you can switch from one array to another.

Your task is to find a path through the intersections i.e common integers of ‘ARR1’ and ‘ARR2’, that produces maximum sum and return that maximum sum as the answer.

For example:

Input Format:

Output Format :

Note:

Constraints:

Top Zomato Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern