Urgently Need help!! Min Stack problem .

Question

Problem link-. https://leetcode.com/problems/min-stack/
My solution- https://code.sololearn.com/czFU6C0SVET1/?ref=app
In normal test case my solution is giving correct output .But fails in a testcase which I had written in my solution of sololearn though my solution seems to be correct.
Testcase Is very long so i am not able to know why that test case is failing.
In LeetCode only the required part of solution have to write so if anyone want to check it the can put my solution in LeetCode problem link given above

Answer 1

maybe the time constraint isn't satisfied? It's my first thought seeing your code.

I don't have an account on that site to try, plus I'm on the phone, but see if this solution works:

https://code.sololearn.com/cZhKWVrdGUvm

EDIT: I just made an account and can confirm it worked.

Answer 2

it says "Design a stack that supports push, pop, top, and retrieving the minimum element in CONSTANT TIME" <- see, time constraint.

Answer 3

ok, I'm sorry, only now I realized: you do:

MAX = 3*10^4;

but operator ^ is XOR, not exponentiation.

Otherwise your solution works, even with the time constraint, I just tried.

Sorry sorry sorry 😇

Answer 4

if there is no memory constraint, have a second array with indexes of minimum elements as they are pushed.

When you push a new element, check if it's smaller than the last minimum, and add its index to the minimum array.

When you pop an element, check if its index is the last one in the minimum array, to eliminate it from there, because now you will have remained with the previous minimum. And so on.

getMin() should just retrieve (from the main array) the element with the index stored at the top of the minimum array.

Answer 5

But why my solution is giving wrong answer on that input

Answer 6

Srishti Jaiswal the requirement specified constant time, aka O(1) complexity. Your getMin() method tried to determine the minimum when it was called, making it of O(n) complexity, that's why it probably failed.

See my solution from the previous reply, which implemented the suggestion I gave you in the first reply. It seems it works as an accepted solution.

Answer 7

If my solution exceeds req time complexity then it will give tle but my solution has some answer as wrong .Yeah i will optimized it further but my solution must work

Answer 8

Yes ,I missed that .I understand mine has brute force approach but atleast my solution have to give correct answer for all test cases irrespective of time constraints.My Sol seems correct according to brute force approach atleast.But why giving wrong answer

Answer 9

lion

Answer 10

Haa thanks.If hadn't point out this i will not able to find it .😓.How could you able to debug that ? 🙂lion

Answer 11

Did you login in LeetCode ?

Answer 12

yes