+ 2

# Urgently Need help!! Min Stack problem .

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

12 Antworten

+ 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.

+ 1

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

+ 1

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 😇

0

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.

0

But why my solution is giving wrong answer on that input

0

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.

0

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

0

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

0

0

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

0

Did you login in LeetCode ?

0

yes