Intuition behind the O(N) solution


#1

Stack Sortable.
Please refer to this link for better understanding.