We need to take out elements in order with a little help of one stack. We need to solve this by eliminating every possible element starting from the left and also taking out those very same elements from the stack if it's their turn ( the phrase "their turn" means that we already eliminated all the elements up to the current one , and we can eliminate him if he is one the leftmost spot or on top of the stack). We need to loop over the given array from left to right and see, if it's his turn then eliminate it (this can be understood in many ways, just ignoring and passing to the next one or removing it from the array, it depends on your preference ). (note that we keep a variable cur (current) which shows which is the current element to be eliminated), now if we can't eliminate it we add it to our stack waiting for it's turn, (NOTE there is no other way, if our current element can;t be eliminated now because it's not his turn then we do not have any other option but to push him into stack). And in every step we also check "if it's now the turn of the top element of stack", if yes we need to keep removing them until we either reach an element which can't be eliminated now or our stack gets empty. We need to keep doing those until we have looped over all elements. If we were able to successfully remove all of them then the answer is yes.
No comments:
Post a Comment