DSA SheetMedium
EditorialPractice

RECURSION & BACKTRACKING › RECURSION PROBLEMS

Sort a Stack

MediumEditorial · 5 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

A stack and its top-to-bottom array representationOn the left, a sorted vertical stack has its smallest value at the bottom and its largest value at the top. An arrow from the top of the stack points to a horizontal returned array on the right, whose values are listed from largest to smallest. The picture makes clear that the output is not the bottom-to-top storage order; it is the order produced by popping.5432154321pop orderTOP — next pop: 5BOTTOM — smallest: 1RETURNED ARRAY — pop orderlargest at the topmeans descending output

Approachtranslate the stack representation before choosing the sort direction

  1. 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.
  2. 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.
  3. Keep equal values during sorting rather than removing or combining them, because every occurrence in the input must appear in the returned stack.
  4. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(log n) extraThe 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.

Common mistakesthe representation changes direction between input and output

Previous · Delete Middle Element of a Stack