0% completed

Solution: Sorting a Stack

Problem Statement

Given a stack, sort it using only stack operations (push and pop).

You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The values in the stack are to be sorted in descending order, with the largest elements on top.

Examples

1. Input: [34, 3, 31, 98, 92, 23]
   Output: [3, 23, 31, 34, 92, 98]

2. Input: [4, 3, 2, 10, 12, 1, 5, 6]
   Output: [1, 2, 3, 4, 5, 6, 10, 12]

3. Input: [20, 10, -5, -1]
   Output: [-5, -1, 10, 20]

.....

Like the course? Get enrolled and start learning!

James Louie

· a year ago

Leszek Kalwa

· 2 years ago

Guys,

Either you treat stack as a stack, or as an array. What the heck is line:15 from your js solution? That's clearly accessing something by index.

            // While the temporary stack is not empty and the top element
            // of the temporary stack is greater than the current element,
            // push elements from the temporary stack back to the original stack.
            while (tempStack.length && tempStack[tempStack.length - 1] > temp) {
                stack.push(tempStack.pop());
            }

Show 1 reply

Leopoldo Hernandez

· 2 years ago

"""
My solution:
Time Complexity:
The main loop iterates through each element in the original stack once.
In the worst case, for each element, you might have to pop elements from the temporary stack until
the correct position is found.
Therefore, the time complexity is O(N^2), where N is the number of elements in the stack.
Space Complexity:
The space complexity is O(N) since you are using two additional stacks
(original_stack and temp_stack), and their combined size depends on the number of elements in the original stack.
"""
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Stack:

    def __init__(self):
        self.top = None
        self.count = 0
    def size(self):
        return self.count

    def is_empty(self):
        r

P P

· 5 months ago

F

fellainthewagon

· 2 years ago

Show 1 reply

Sourav Singh

· 2 years ago