game of stacks in which number is removed from top until it amounts to greater that given max sum

Question

I'm trying to solve this hacker rank problem, which gives us two integer stacks and a maxSum variable assigned to a particular value and asks us to find total number of elements removed from top from both the stacks until sum of all number removed from stacks does not become greater than the given maxSum.

example;

stack 1 is; 4 2 4 6 1
stack 2 is; 2 1 8 5
maxSum=10
output=4 as we can remove 4,2,2, 1 & 4+2+2+1=9 which is less than 10.

I used below approach to implement my function to solve it and according to me everything in my code looks fine, but still i'm unable to pass many of the testcases. Kindly looking for help.

ps: i'm beginner in DSA.

int twoStacks(int maxSum, vector<int> a, vector<int> b) {
    int count=0;
    int sum=0;
    int i=0;
    int j=0;
    while(sum<=maxSum){
        if(i<a.size() && j<b.size() && sum+min(a[i],b[j])<=maxSum){
            sum+=min(a[i],b[j]);
            count++;
            if(min(a[i],b[j])==a[i]){
                i++;
            }
            else{
                j++;
            }
        }
        else if(i>=a.size() && j<b.size() && sum+b[j]<=maxSum){
            sum+=b[j];
            count++;
            j++;
        }
        else if(i<a.size() && j>=b.size() && sum+a[i]<=maxSum){
            sum+=a[i];
            count++;
            i++;
        }
        else{
            break;
        }
    }
    return count;
}

Answer 1

Your code assumes that there is a "greedy" approach to ensure you find the maximum possible number of removals. But this is not true. It is not always best to take the minimum value among the two stack tops. For example, stack B could start with a rather great value, but have many small values after it, which would make it interesting to still take that first great value and then profit from the many subsequent values you can take from it:

maxSum: 10
A: {5, 5, 5, 5}
B: {6, 1, 1, 1, 1, 1, 1}

Your algorithm would take twice from A, while it is better to take 5 times from B.

So first take as many as possible from A, and if you can take them all, also continue taking as many from B. This represents one possible solution.

Then continue to take one less value from A and see if you then can take more from B. This again represents a potential solution. Continue this process until either no elements from A can be returned to it, or all values of B have been taken.

Among all potential solutions keep track of the most removals that could be done.

Code:

int twoStacks(int maxSum, vector<int> a, vector<int> b) {
    int i = 0;
    int j = 0;
    int maxTakes = 0;
    // Take as many as possible from A
    while (i < a.size() && maxSum >= a[i]) {
        maxSum -= a[i++];
    }
    while (true) {
        // Take as many as possible from B
        while (j < b.size() && maxSum >= b[j]) {
            maxSum -= b[j++];
        }
        maxTakes = max(maxTakes, i + j);
        if (i == 0 || j >= b.size()) return maxTakes;
        // Return one value back to A so to make room for more from B
        maxSum += a[--i];
    }
    return maxTakes;
}