Monotonic stack complexity with binary search

Question

A monotonic stack is a stack whose elements are monotonically increasing or decreasing. To insert an element into the stack you need to remove elements that are greater/less than the provided element and then put the provided element on top keeping elements order. Usually, inserting in a monotonic stack performed by popping top until we can push an element. So, it is said that to preserve monotonic stack over N elements requires O(N) time complexity. For example.

However, what I don't get, if we represent monotonic stack by sorted array and its size, then, when we are inserting element, we can binary search the position where we are supposed to insert the element and discard the tail by reducing size. It seems like to be more efficient approach. The question is, does it change complexity? Is there a reason, why it is usually presented with the iterative "popping top" version?

• Rinkesh P: "Does it change complexity?" Depends on the implementation. A stack by convention supports the "push" and "pop" operations for insertion and deletion respectively, at a single location "top of stack".
• Irdis: @RinkeshP Sure conventional stack supports only push and pop, I'm interested in case when we represent stack as array and size as int. For example, we can empty array in constant time, this.size = 0. I also consider case when we don't have to resize in case it too short for simplicity
• D.W.: Is insert(x) supposed to add x to the stack and keep all of the existing elements? Or is it supposed to remove all elements greater than x, and not add them back in?
• D.W.: I'm asking a clarification question: should we add them back in, or not? I would like to see the question state the answer explicitly and specify what exactly the insert() operation is supposed to do. I can't tell, and before I answer, I want to be sure I understand what is the question.

Answer 1

Binary search worsens the time complexity from O(N) to O(N log N).

• Irdis: hmmmm.... it could be a thing but I find it hard to believe
• Kelly Bundy: @Irdis What's hard to believe?
• Irdis: your statement. I see the point that each time we spend log time to find insertion point, so it has to be like n log n. But using the same argument, I can say every time we spend linear time to find insertion point in linear version, so it has to be the square time. But it is incorrect.
• Irdis: I actually think you are right and it is simple as that, in the worst case for bin search when elements to insert are sorted in the same direction, linear version would clearly outperform.
• Kelly Bundy: @Irdis Tip for the future just in case you didn't know: There's no rush with awarding bounties. You had "paid" for a week of extra attention that could've attracted more/better answers (while I do think mine is pretty much all that needed to be said, more could be said). If you do what D.W. requested, maybe they'll still post something interesting.