javaalgorithmdata-structuresstack

How is my algorithm for stock span problem incorrect?


The question :

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate the span of stocks price for all n days. The span Si of the stocks price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the given day is less than or equal to its price on the current day. For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}.

My SOlution:

class Solution {
    
    public static int[] calculateSpan(int price[], int n) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        int[] count = new int[price.length];
        
        for(int i = 0 ; i < n; i++) {
            int size = 0;
            
            while(!s1.empty() && price[i] > s1.peek()) {
                s2.push(s1.pop());
            }
            if(!s2.empty()) {
                size = s2.size();
            }
            while(!s2.empty() && price[i] > s2.peek()) {
                s1.push(s2.pop());
            }
            
            s1.push(price[i]);
            count[i] = size + 1;
        }
        
        return count;
    }
}

For input:

n = 134
74 665 742 512 254 469 748 445 663 758 38 60 724 142 330 779 317 636 591 243 289 507 241 143 65 249 247 606 691 330 371 151 607 702 394 349 430 624 85 755 357 641 167 177 332 709 145 440 627 124 738 739 119 483 530 542 34 716 640 59 305 331 378 707 474 787 222 746 525 673 671 230 378 374 298 513 787 491 362 237 756 768 456 375 32 53 151 351 142 125 367 231 708 592 408 138 258 288 554 784 546 110 210 159 222 189 23 147 307 231 414 369 101 592 363 56 611 760 425 538 749 84 396 42 403 351 692 437 575 621 597 22 149 800

My output is:

1 2 3 1 1 2 7 1 2 10 1 2 3 1 2 16 1 2 1 1 2 3 1 1 1 4 1 10 13 1 2 1 4 18 1 1 3 4 1 24 1 2 1 2 3 6 1 2 3 1 11 12 1 2 3 4 1 6 1 1 2 3 4 6 1 66 1 2 1 2 1 1 2 1 1 5 11 1 1 1 4 5 1 1 1 2 3 4 1 1 7 1 11 1 1 1 2 3 5 23 1 1 2 1 4 1 1 2 8 1 10 1 1 14 1 1 17 18 1 2 3 1 2 1 4 1 6 1 2 3 1 1 2 134

while the expected output is :

1 2 3 1 1 2 7 1 2 10 1 2 3 1 2 16 1 2 1 1 2 3 1 1 1 4 1 10 13 1 2 1 4 18 1 1 3 4 1 24 1 2 1 2 3 6 1 2 3 1 11 12 1 2 3 4 1 6 1 1 2 3 4 6 1 66 1 2 1 2 1 1 2 1 1 5 77 1 1 1 4 5 1 1 1 2 3 4 1 1 7 1 11 1 1 1 2 3 5 23 1 1 2 1 4 1 1 2 8 1 10 1 1 14 1 1 17 18 1 2 3 1 2 1 4 1 6 1 2 3 1 1 2 134

The difference is that one value in the output is 77 and mine is 11.

I have been debugging this for last 5 hours but unable to understand. Would really appreciate help in understanding the issue.

Side note: I know we can do this with 1 stack and various other optimised approaches. But I just want to know how is my approach incorrect ? WHat is wrong in my algorithm ?

[EDIT] Original question here: https://www.geeksforgeeks.org/problems/stock-span-problem-1587115621/1


Solution

  • Looking at the input at and before the difference you have:

    Input:
    ..... 305 331 378 707 474 787 222 746 525 673 671 230 378 374 298 513 787
                                                                          ^^^
                                                                       Different
                                                                        result
                                                                          here
    

    So you have 11 while the expected result is 77.

    So let's count backwards from the failing point.

    Input:
    ..... 305 331 378 707 474 787 222 746 525 673 671 230 378 374 298 513 787
                                  11  10   9   8   7   6   5   4   3   2   1
    

    Now observe that the value at the failing location is 787. Further, observe that the value just before your result (11) is also 787.

    This strongly suggest that your algorithm treats equality wrong.

    Looking at your code all price compares are done using >. Consider replacing one (or more) with >=