+ 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

5th Jun 2022, 3:27 AM
Srishti Jaiswal
Srishti Jaiswal - avatar
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.
5th Jun 2022, 6:04 AM
lion
lion - avatar
+ 1
it says "Design a stack that supports push, pop, top, and retrieving the minimum element in CONSTANT TIME" <- see, time constraint.
5th Jun 2022, 7:05 AM
lion
lion - avatar
+ 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 ­čśç
5th Jun 2022, 7:31 AM
lion
lion - avatar
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.
5th Jun 2022, 5:38 AM
lion
lion - avatar
0
But why my solution is giving wrong answer on that input
5th Jun 2022, 5:39 AM
Srishti Jaiswal
Srishti Jaiswal - avatar
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.
5th Jun 2022, 6:46 AM
lion
lion - avatar
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
5th Jun 2022, 6:54 AM
Srishti Jaiswal
Srishti Jaiswal - avatar
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
5th Jun 2022, 7:11 AM
Srishti Jaiswal
Srishti Jaiswal - avatar
5th Jun 2022, 7:12 AM
Srishti Jaiswal
Srishti Jaiswal - avatar
0
Haa thanks.If hadn't point out this i will not able to find it .­čśô.How could you able to debug that ? ­čÖélion
5th Jun 2022, 7:39 AM
Srishti Jaiswal
Srishti Jaiswal - avatar
0
Did you login in LeetCode ?
5th Jun 2022, 7:39 AM
Srishti Jaiswal
Srishti Jaiswal - avatar
0
yes
5th Jun 2022, 7:40 AM
lion
lion - avatar