Problem Statement
You are given three stacks with Non-negative elements in each of them. Your task is to find and return the maximum possible equal sum in the three stacks.
Prerequisites
Before we think of the approach to tackle the above problem, it is necessary to know the stack data structure and its operations.
Stack is a LIFO( Last in, first out) type data structure. Meaning, the elements that are input last are retrieved first. Think of a stack of books. The last book in the stack is kept at the bottom and wouldn’t be retrieved until all the other books above it are removed.
Stack has three basic operations:-
- Push: The push operation inserts the element in the stack. The time complexity of the operation is O(1).
- Pop: The pop operation retrieves the last inserted element in the stack. The time complexity of the operation is O(1).
- Peek: The Peek or Top operation prints the last inserted element in the stack without removing it. The time complexity of the operation is O(1).
It’s seemingly simple to understand and implement as well as the operations are cheap. That is what makes it a powerful tool in problem-solving. Stack finds its uses in a number of scenarios, one of which we will study now.
Approach
Our task is to find the maximum possible equal sum in three stacks.
So let’s consider three stacks A, B, and C with some elements-
A=[1, 3, 4, 2, 1, 6, 7] {Initial Sum = 24}
B=[3, 2, 2, 1, 5, 9] {Initial Sum = 22}
C=[5, 2, 1, 8] {Initial Sum = 16}
Since we want to find the maximum possible equal sum in three stacks, we start by popping out elements from the stack with the maximum sum and then rechecking which stack has the maximum sum. We will repeat the process until the sum of all three stacks is equal. Though it’s important to observe, this approach can only work when all the elements in the stack are non-negative.
- 7 is removed from A
Sum(A)=17
Sum(B)=22
Sum(C)=16
- 9 is removed from B
Sum(A)=17
Sum(B)=13
Sum(C)=16
- 6 is removed from A
Sum(A)=11
Sum(B)=13
Sum(C)=16
- 8 is removed from C
Sum(A)=11
Sum(B)=13
Sum(C)=8
- 8 is removed from C
Sum(A)=11
Sum(B)=13
Sum(C)=8
- 5 is removed from B
Sum(A)=11
Sum(B)=8
Sum(C)=8
- 1 is removed from A
Sum(A)=10
Sum(B)=8
Sum(C)=8
- 2 is removed from A
Sum(A)=8
Sum(B)=8
Sum(C)=8
The loop stops when all three sums reach a common value.
Algorithm
- Input non-negative elements for all three stacks.
- Store the sums of all three stacks in three variables.
- Check which stack has the maximum sum.
- From the stack with the maximum sum, pop out the last element.
- Subtract the last removed value from the sum of that stack.
- Repeat steps 3 to 5 until all three sums are equal.
- Return the common value of the three sums.
Code
def MaxSumInStacks(s1,s2,s3):
s1_length=len(s1)
s2_length=len(s2)
s3_length=len(s3) # calculate the size of the three stacks
sum1=sum(s1)
sum2=sum(s2)
sum3=sum(s3) # calculate the sum of the three stacks
while(True):
#return 0 once any of the three sums are reduced to 0
if sum1==0 or sum2==0 or sum3==0:
return 0
# return the sum once we find the common value of three sums
# else pop and subtract the last element from the stack with maximum sum
if sum1==sum2==sum3:
return sum1
elif sum1>=sum2 and sum1>=sum3:
ele=s1.pop()
sum1-=ele
elif sum2>=sum1 and sum2>=sum3:
ele=s2.pop()
sum2-=ele
elif sum3>=sum1 and sum3>=sum2:
ele=s3.pop()
sum3-=ele
arr1=[int(x) for x in input().split(" ")]
arr2=[int(x) for x in input().split(" ")]
arr3=[int(x) for x in input().split(" ")]
print(MaxSumInStacks(arr1,arr2,arr3))
Input:
1 3 4 2 1 6 7
3 2 2 1 5 9
5 2 1 8
Output:
8
Complexity Analysis
Time Complexity: In the worst case, we might have to iterate over all three stacks completely. So, if the size of each stack is N and we make 3N iterations, then the time complexity would be of the order O(N).
Space Complexity: We would require three stacks of size N to store the elements. Therefore, the space complexity is of the order O(N).
Check out this problem - Subarray With 0 Sum
Must Read Stack Operations
34+ registered 
