Is the stack needed?


#1

I feel like the stack is unneeded. Consider this solution:

vector<int> Solution::prevSmaller(vector<int> &A) {
    vector<int> ans;
    int len = A.size();
    int min = A[0], j;
    ans.push_back(-1);
    for (int i=1; i<len; i++) {
        if (A[i] <= min) {
            ans.push_back(-1);
            min = A[i];
        } else {
            j = i;
            while(A[j--] >= A[i]);
            ans.push_back(A[j+1]);
        }
    }
    return ans;
}

The number of times it goes back in the while should be equal to the number of times the stack is popped. So they should have similar time complexity.


#2

This is not true : “The number of times it goes back in the while should be equal to the number of times the stack is popped”
For I/P : 2 7 6 5 4 3 , while loop runs O(n^2) times but stack pop operation can’t be more than O(n).


#3

I think a good way to explain this would be with amortized analysis.
Suppose phi = size of stack
phi(0) = 0
Pushing elements: amortized cost = 1 + (phi(n) - phi(n - 1)) = 2
Popping k elements: amortized cost = k + (phi(n - k) - phi(n)) = 0
Popping elements is literally free in this context!
Since max n elements are pushed, we’re still O(n)


#4

What about this?

I agree with @aksh1618 why do we need stack?
@winner421 and @sachin-goel please have a look at the below code.

vector<int> Solution::prevSmaller(vector<int> &A) 
{
    vector<int> ans = {-1};
    for(int i=1; i<A.size(); i++)
    {
        if(A[i-1] < A[i])
            ans.push_back(A[i-1]);
        else
        {
            int j;
            for(j=i-1; j>0 && ans[j]>=A[i]; j--);

            ans.push_back(ans[j]);
        }
    }
    return ans;
}

#5

I also think stack is not required. Because pop() function for a particular iteration will call as same number of while loop iteration for that element. So both have same complexity.
Please someone clarify this.