 # 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, 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

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.