Sort a Stack — Editorial

Opening the reading…

Intuitionthe returned array is the stack's pop order

The input describes the stack from bottom to top, but the output describes what repeated popping produces. After sorting, the smallest value must be at the bottom and the largest value must be at the top. Popping therefore removes values from largest to smallest, so the returned array must be in non-increasing order.

That means the stack operation does not require a special recursive rearrangement here. The array already contains the complete stack, and sorting it in descending order directly creates the required top-to-bottom representation. Sorting keeps equal values as separate occurrences, so duplicates need no special handling.

Approachtranslate the stack representation before choosing the sort direction

Receive the array by value so the method can rearrange its local stack representation without changing the caller's array, while the same storage can become the returned result.

Sort the entire array with the greater-than comparator, because the required output starts with the value at the sorted stack's top and continues downward.

Keep equal values during sorting rather than removing or combining them, because every occurrence in the input must appear in the returned stack.

Return the sorted array directly; descending order is already the required pop order, so reversing it would incorrectly produce bottom-to-top order.

Complexitycomparison sorting determines the bound

MEASURE	BOUND	WHY
Time	O(n log n)	std::sort performs comparison sorting over all n elements; its worst-case implementation guarantee keeps the number of comparisons within O(n log n), and each comparison takes constant time for integers.
Space	O(log n) extra	The returned array is required output and is excluded from the working-space bound. The array itself is rearranged in place, while std::sort uses recursion or equivalent bookkeeping whose stack space is O(log n); this remains logarithmic even for an already sorted or highly ordered input.

Here n is the number of values in the stack.

Annotated solutionC++ · in-place descending sort · complete judge-ready method

CPPSort the stack representation in descending order, which is exactly its required pop order.

#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> sortStack(vector<int> st) {
        sort(st.begin(), st.end(), greater<int>());
        return st;
    }
};

The comparator is the key line: the default sort order would place the smallest value first, which represents the bottom of the sorted stack rather than its first popped value. greater<int>() places the largest value first, so index 0 of the returned array represents the top element and each later index represents the next pop.