Find Maximum Sum Possible Equal Sum of Three Stacks

Last Updated on October 10, 2022 by Gokul Kannan

Problem Statement

You are given three stacks, you need to find the maximum sum possible of the three stacks. You are only allowed to remove the top of the stack.

Input: Three stacks are represented as arrays.
Output: Integer representing the maximum sum.

Test cases:

Input: S1 = [1, 1, 3, 4], S2 = [3, 2, 2], S3 = [4, 3, 4]
Output: 7

Explanation:

We can remove the first two elements of ‘S1’ and the first element of ‘S3’. Then the remaining sum of each stack will be 7.

Approach – Using Stack

1. Find the sum of each stack individually, ‘sum1’, ‘sum2’, and ‘sum3’.
2. Initialize three variables to keep track of the top of the stack.
3. While the sum1, sum2 and sum3 are different and all the three stacks have elements in them, will we remove the top of that stack which currently has the maximum sum.
4. After coming out of the loop in point 3, if sum1, sum2, and sum3 are equal, we will return any of them, otherwise we will return 0.

Algorithm

1. Initialize three variables, ‘sum1’, ‘sum2’, and ‘sum3’ to store the sum of each stack.

2. Find the sum of each stack, individually.

3. Initialize three variables, ‘i’, ‘j’, and ‘k’, to keep track of the top of each stack.

4. While (sum1 != sum2 and sum2 != sum3) and (i < S1.length) and (j < S2.length) and (k < S3.length)
   a. If sum1 is greater than sum2 and sum3.

   • sum1 -= top of S1

   b. If sum2 is greater than sum1 and sum2.

   • sum2 -= top of S2

   c. If sum3 is greater than sum2 and sum3.

   • sum3 -= top of S3

5. If sum1 is equal to sum2 and sum3, return sum1

6. return 0.

Dry Run:

Code Implementation:

public class Main
{

    public static int maxPossibleSum(int[] S1, int[] S2, int[] S3) {
        
        // Initialize three variables to store the sum of each stack.
        int sum1 = 0;
        int sum2 = 0;
        int sum3 = 0;
        
        // Find the sum of each stack, individually.
        for(int e : S1){
            sum1+=e;
        }
        for(int e : S2){
            sum2+=e;
        }
        for(int e : S3){
            sum3+=e;
        }
        
        // Initialize three variables to keep track of the top of each stack.
        int i = 0;
        int j = 0;
        int k = 0;
        
        // While the sum1, sum2 and sum3 are different 
        // and all the three stacks have elements in them, 
        // we will remove the top of that stack which currently has the maximum sum.
        while(!(sum1 == sum2 && sum2 == sum3) && (i<S1.length) && (j<S2.length) && (k<S3.length)){
            if(sum1 > sum2){
                if(sum1 > sum3){
                    sum1 -= S1[i];
                    i++;
                }
                else{
                    sum3 -= S3[k];
                    k++;
                }
            }
            else{
                if(sum2 > sum3){
                   sum2 -= S2[j]; 
                   j++;
                }
                else{
                    sum3 -= S3[k];
                    k++;
                }
            }

        }
        
        // If sum1, sum2 and sum3 are equal, return any of them
        if(sum1 == sum2 && sum2 == sum3){
            return sum1;
        }
        
        // Otherwise return 0.
        return 0;
    }
    
    public static void main(String[] args) {
	    int[] S1 = {1, 1, 3,  4};
	    int[] S2 = {3, 2, 2};
	    int[] S3 = {4, 3, 4};
	    
	System.out.println(maxPossibleSum(S1, S2, S3));
	}

}

Output:
7
Time complexity: O(n1 + n2 + n3), where n1 is the length of ‘S1’, n2 is the length of ‘S2’ and n3 is the length of ‘S3’.

Space Complexity: O(1). The auxiliary space used will be constant.

We tried to discuss The Find Maximum Sum Possible Equal Sum of Three Stacks. We hope this article gives you a better understanding of Find Maximum Sum Possible Equal Sum of Three Stacks. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.