A stack answers one question in O(1): what is the most recent thing still open? Brackets, undo, expressions and nested strings all ask it. Nine moves, fifteen problems.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.
Push every opener. A closer must match the top, the most recent opener still open. Last in, first out.
isValid("([)]"). What is returned, and at which character is it decided?
At the ), the top is [, not (. The pairs cross, so it returns there.
A solution keeps one counter per kind, fails if any goes below 0, and accepts if all end at 0. Which input does it wrongly accept?
Each counter stays ≥ 0 and ends at 0, yet the pairs cross. Counters cannot see order.
GIVEN · ASKEDA string of ()[]{}. Return true if every bracket is closed by the same kind, in the right order.
Three kinds of bracket, and every closer must close the most recent opener still open.
Push each opener. A closer pops the top and must be its partner. At the end nothing may be left open.
bool isValid(string s) { stack<char> st; for (char c : s) { if (c == '(' || c == '[' || c == '{') st.push(c); // an opener waits else { if (st.empty()) return false; // nothing is open char open = st.top(); st.pop(); if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false; // the pairs cross } } return st.empty(); // all closed? }
public boolean isValid(String s) { Deque<Character> st = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') st.push(c); // an opener waits else { if (st.isEmpty()) return false; // nothing is open char open = st.pop(); if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false; // the pairs cross } } return st.isEmpty(); // all closed? }
def isValid(s): match = {')': '(', ']': '[', '}': '{'} st = [] for c in s: if c in '([{': st.append(c) # an opener waits for its closer elif not st or st.pop() != match[c]: return False # nothing open, or the pairs cross return not st # anything left was never closed
Counting each kind separately. ([)] has one of each pair and is still invalid. Order matters, and only a stack keeps it.
Build the answer as a stack. A letter equal to the top removes it, and the letter below becomes the next one's neighbour.
Each entry is a letter and its run length. A run that reaches k is popped whole, and the run below can grow again.
removeDuplicates("azxxzy") with pairs. What is returned?
xx goes, which makes the two z's neighbours, and they go too. a and y are left.
s = "pbbcggttciiippooaais" and k = 2. What is left?
Pairs vanish as they form: bb, gg and tt, then the two c's, the i's, p's, o's and a's.
GIVEN · ASKEDA string of lowercase letters. Repeatedly remove two adjacent equal letters until none are left. Return the final string.
Two equal letters side by side vanish, and a removal can make new neighbours equal.
Build the answer as a stack. A letter equal to the top cancels it; any other letter is pushed. A removal is handled for free: the next letter meets whatever was below.
string removeDuplicates(string s) { string st; // the answer is the stack for (char c : s) { if (!st.empty() && st.back() == c) st.pop_back(); // c cancels the top else st.push_back(c); } return st; }
public String removeDuplicates(String s) { StringBuilder st = new StringBuilder(); // the answer is the stack for (char c : s.toCharArray()) { int n = st.length(); if (n > 0 && st.charAt(n - 1) == c) st.deleteCharAt(n - 1); // c cancels the top else st.append(c); } return st.toString(); }
def removeDuplicates(s): st = [] # the answer, built as a stack for c in s: if st and st[-1] == c: st.pop() # c cancels the top else: st.append(c) return "".join(st)
Rescanning after each removal. while a pair exists, delete it and start again is O(n²) and times out at n = 10⁵.
GIVEN · ASKEDA string and an integer k. Repeatedly remove k adjacent equal letters until none are left. Return the final string.
As #02, but a run must reach k equal letters to vanish, and k can be large.
Store runs, not letters: each entry is a letter and the length of its run. A letter equal to the top grows the run; a run that reaches k is popped whole.
string removeDuplicates(string s, int k) { vector<pair<char, int>> st; // (letter, length of its run) for (char c : s) { if (!st.empty() && st.back().first == c) st.back().second++; else st.push_back({c, 1}); if (st.back().second == k) st.pop_back(); // k in a row vanish } string out; for (auto& p : st) out.append(p.second, p.first); return out; }
public String removeDuplicates(String s, int k) { Deque<int[]> st = new ArrayDeque<>(); // {letter, length of its run} for (char c : s.toCharArray()) { if (!st.isEmpty() && st.peek()[0] == c) st.peek()[1]++; else st.push(new int[]{c, 1}); if (st.peek()[1] == k) st.pop(); // k in a row vanish } StringBuilder out = new StringBuilder(); while (!st.isEmpty()) { // the bottom run comes first int[] r = st.pollLast(); for (int j = 0; j < r[1]; j++) out.append((char) r[0]); } return out.toString(); }
def removeDuplicates(s, k): st = [] # [letter, length of its run] for c in s: if st and st[-1][0] == c: st[-1][1] += 1 else: st.append([c, 1]) if st[-1][1] == k: st.pop() # k in a row vanish return "".join(ch * cnt for ch, cnt in st)
Peeking k − 1 letters back. Checking the last k − 1 letters on every push is O(nk). The count on top already knows the run's length.
GIVEN · ASKEDAn absolute Unix path. Return its canonical form: one slash between names, no . or .., no trailing slash.
A Unix path with ., .. and repeated slashes, reduced to its canonical form.
Split on '/'. A name opens a directory, so push it. .. closes the most recent one, so pop. Empty parts and . change nothing.
string simplifyPath(string path) { vector<string> st; // the directories still open stringstream ss(path); string part; while (getline(ss, part, '/')) { if (part.empty() || part == ".") continue; // "//" and "." change nothing if (part == "..") { if (!st.empty()) st.pop_back(); } // up one level else st.push_back(part); // "..." is an ordinary name } string out; for (auto& d : st) out += "/" + d; return out.empty() ? "/" : out; }
public String simplifyPath(String path) { Deque<String> st = new ArrayDeque<>(); // the directories still open for (String part : path.split("/")) { if (part.equals("..")) { if (!st.isEmpty()) st.pop(); } // up one level else if (!part.isEmpty() && !part.equals(".")) st.push(part); } StringBuilder out = new StringBuilder(); while (!st.isEmpty()) out.append("/").append(st.pollLast()); // bottom first return out.length() == 0 ? "/" : out.toString(); }
def simplifyPath(path): st = [] # the directories still open for part in path.split("/"): if part == "..": if st: st.pop() # up one level; at the root, stay elif part and part != ".": st.append(part) # "..." is an ordinary name return "/" + "/".join(st)
Treating any run of dots as special. Only . and .. are. ... is a directory name and must be pushed.
In Simplify Path, which part plays the letter that cancels the top?
".." closes the most recent directory. "." and "" do nothing, and "..." is a name.
Keep indices. After a pop, the top is the last index that cannot be in the run, so i − top is its length.
s = "()(())". What is on the stack when the loop ends?
Every ( closed, so only the first base is left. The last pop measured 5 − (−1) = 6.
Why does the stack start with −1 instead of empty?
i − top needs an index before the run. For a run that starts at 0, that index is −1.
GIVEN · ASKEDA string of ( and ). Return the length of the longest well-formed substring.
The length of the longest valid substring, not just whether the string is valid.
Keep indices. The bottom of the stack is a base: the last index that cannot be in the current run. After a pop, i − top is the length of the valid run ending at i.
int longestValidParentheses(string s) { stack<int> st; st.push(-1); // the index just before the current run int best = 0; for (int i = 0; i < (int)s.size(); i++) { if (s[i] == '(') st.push(i); else { st.pop(); // close the most recent '(' if (st.empty()) st.push(i); // an unmatched ')' is the new base else best = max(best, i - st.top()); } } return best; }
public int longestValidParentheses(String s) { Deque<Integer> st = new ArrayDeque<>(); st.push(-1); // the index just before the current run int best = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') st.push(i); else { st.pop(); // close the most recent '(' if (st.isEmpty()) st.push(i); // an unmatched ')' is the new base else best = Math.max(best, i - st.peek()); } } return best; }
def longestValidParentheses(s): st, best = [-1], 0 # -1: the index just before the current run for i, c in enumerate(s): if c == '(': st.append(i) else: st.pop() # close the most recent '(' if not st: st.append(i) # an unmatched ')' is the new base else: best = max(best, i - st[-1]) return best
Counting matched pairs. ()(() has two pairs but the longest valid run is 2, not 4. Lengths come from indices, never from counts.
Push (x, min(x, top's min)). That min cannot change while the entry is on the stack, so a pop needs no repair.
push 4, push 2, push 6, pop, push 1, pop. What does getMin return?
(1, 1) was popped. The top is (2, 2), and it stored its own min when it was pushed.
A min stack keeps one variable mn, lowered on push. What breaks?
After the min is popped, the next smallest is unknown without scanning the stack.
GIVEN · ASKEDDesign a stack with push, pop, top and getMin, each in O(1).
A stack that must also answer getMin() in O(1), through any mix of pushes and pops.
Each entry stores its value and the minimum of itself and everything below it. That minimum never changes while the entry is on the stack, so a pop needs no repair.
class MinStack { stack<pair<int, int>> st; // (value, minimum at or below it) public: void push(int val) { int m = st.empty() ? val : min(val, st.top().second); st.push({val, m}); } void pop() { st.pop(); } int top() { return st.top().first; } int getMin() { return st.top().second; } };
class MinStack { private final Deque<int[]> st = new ArrayDeque<>(); // {value, min at or below} public void push(int val) { int m = st.isEmpty() ? val : Math.min(val, st.peek()[1]); st.push(new int[]{val, m}); } public void pop() { st.pop(); } public int top() { return st.peek()[0]; } public int getMin() { return st.peek()[1]; } }
class MinStack: def __init__(self): self.st = [] # (value, minimum at or below it) def push(self, val): m = min(val, self.st[-1][1]) if self.st else val self.st.append((val, m)) def pop(self): self.st.pop() def top(self): return self.st[-1][0] def getMin(self): return self.st[-1][1]
One global min variable. It is right until the minimum is popped. Then the next smallest is unknown without a scan, which is O(n).
Push numbers. An operator pops two and pushes one. The first pop is the right operand.
tokens = ["4", "13", "5", "/", "+"]. What is returned?
13 / 5 truncates to 2, and 4 + 2 = 6.
The / branch is written st.push(b / a) after b = pop, a = pop. What does ["6", "3", "/"] return?
b is 3, the right operand. Swapping computes 3 / 6, which truncates to 0.
GIVEN · ASKEDTokens of an expression in reverse Polish notation, with + − * /. Return its value; division truncates toward zero.
An expression in postfix: every operator comes after its two operands, and there are no parentheses.
Push numbers. An operator pops two, applies itself and pushes the result, which is then an operand like any other. The first pop is the right operand.
int evalRPN(vector<string>& tokens) { stack<int> st; for (string& t : tokens) { if (t == "+" || t == "-" || t == "*" || t == "/") { int b = st.top(); st.pop(); // the right operand comes off first int a = st.top(); st.pop(); if (t == "+") st.push(a + b); else if (t == "-") st.push(a - b); else if (t == "*") st.push(a * b); else st.push(a / b); // truncates toward zero, as asked } else st.push(stoi(t)); } return st.top(); }
public int evalRPN(String[] tokens) { Deque<Integer> st = new ArrayDeque<>(); for (String t : tokens) { switch (t) { case "+": { int b = st.pop(), a = st.pop(); st.push(a + b); break; } case "-": { int b = st.pop(), a = st.pop(); st.push(a - b); break; } case "*": { int b = st.pop(), a = st.pop(); st.push(a * b); break; } case "/": { int b = st.pop(), a = st.pop(); st.push(a / b); break; } default: st.push(Integer.parseInt(t)); } } return st.pop(); }
def evalRPN(tokens): st = [] for t in tokens: if t in ("+", "-", "*", "/"): b = st.pop() # the right operand comes off first a = st.pop() if t == "+": st.append(a + b) elif t == "-": st.append(a - b) elif t == "*": st.append(a * b) else: q = abs(a) // abs(b) # truncate toward zero, not floor st.append(q if (a < 0) == (b < 0) else -q) else: st.append(int(t)) return st[0]
Python's //. It floors, so -7 // 2 is −4 where the judge wants −3. Divide the absolute values and put the sign back.
Operands go straight out. Before pushing an operator, pop every waiting one that binds at least as tightly. ^ groups right to left.
A stack of signed terms. When a number ends, + and − push it; * and / fold it into the term on top. Then add up.
What is the postfix form of a+b*c-d?
* leaves before +. Then − pops +, because they bind equally and read left to right.
GIVEN · ASKEDAn infix expression over letters and digits with + − * / ^ and parentheses. Return its postfix form.
Infix in, postfix out, with ^, * / and + − and parentheses. The statement says ^ groups right to left.
Operands go straight to the output. An operator waits on a stack; before it is pushed, every waiting operator that binds at least as tightly leaves first. A ')' empties back to its '('.
int prec(char c) { if (c == '^') return 3; if (c == '*' || c == '/') return 2; if (c == '+' || c == '-') return 1; return 0; // '(' never wins } string infixToPostfix(string& s) { string out; stack<char> ops; for (char c : s) { if (isalnum(c)) out += c; // operands go straight out else if (c == '(') ops.push(c); else if (c == ')') { while (ops.top() != '(') { out += ops.top(); ops.pop(); } ops.pop(); // drop the '(' } else { // pop what binds at least as tightly; ^ groups right to left while (!ops.empty() && (prec(ops.top()) > prec(c) || (prec(ops.top()) == prec(c) && c != '^'))) { out += ops.top(); ops.pop(); } ops.push(c); } } while (!ops.empty()) { out += ops.top(); ops.pop(); } return out; }
static int prec(char c) { if (c == '^') return 3; if (c == '*' || c == '/') return 2; if (c == '+' || c == '-') return 1; return 0; // '(' never wins } public static String infixToPostfix(String s) { StringBuilder out = new StringBuilder(); Deque<Character> ops = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (Character.isLetterOrDigit(c)) out.append(c); // operands go straight out else if (c == '(') ops.push(c); else if (c == ')') { while (ops.peek() != '(') out.append(ops.pop()); ops.pop(); // drop the '(' } else { // pop what binds at least as tightly; ^ groups right to left while (!ops.isEmpty() && (prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c != '^'))) out.append(ops.pop()); ops.push(c); } } while (!ops.isEmpty()) out.append(ops.pop()); return out.toString(); }
def infixToPostfix(s): prec = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1, '(': 0} out, ops = [], [] for c in s: if c.isalnum(): out.append(c) # operands go straight out elif c == '(': ops.append(c) elif c == ')': while ops[-1] != '(': out.append(ops.pop()) ops.pop() # drop the '(' else: # pop what binds at least as tightly; ^ groups right to left while ops and (prec[ops[-1]] > prec[c] or (prec[ops[-1]] == prec[c] and c != '^')): out.append(ops.pop()) ops.append(c) while ops: out.append(ops.pop()) return "".join(out)
Treating ^ like the others. a^b^c is a^(b^c), so the answer is abc^^. Popping equal precedence for ^ gives ab^c^.
GIVEN · ASKEDA string with non-negative integers, + − * / and spaces. Return its value; division truncates toward zero.
Non-negative integers with + − * / and spaces, but no parentheses.
Keep a stack of signed terms. When a number ends, look at the operator before it: + and − push it as a new term, * and / combine it with the term on top at once. Sum the stack.
int calculate(string s) { vector<int> st; // signed terms, added at the end long num = 0; char op = '+'; // the operator before num for (int i = 0; i <= (int)s.size(); i++) { char c = i < (int)s.size() ? s[i] : '+'; // a sentinel closes the last number if (isdigit(c)) { num = num * 10 + (c - '0'); continue; } if (c == ' ') continue; if (op == '+') st.push_back(num); else if (op == '-') st.push_back(-num); else if (op == '*') st.back() *= num; // * and / bind now else st.back() /= num; op = c; num = 0; } int sum = 0; for (int t : st) sum += t; return sum; }
public int calculate(String s) { Deque<Integer> st = new ArrayDeque<>(); // signed terms, added at the end long num = 0; char op = '+'; // the operator before num for (int i = 0; i <= s.length(); i++) { char c = i < s.length() ? s.charAt(i) : '+'; // a sentinel closes the last number if (Character.isDigit(c)) { num = num * 10 + (c - '0'); continue; } if (c == ' ') continue; if (op == '+') st.push((int) num); else if (op == '-') st.push((int) -num); else if (op == '*') st.push(st.pop() * (int) num); // * and / bind now else st.push(st.pop() / (int) num); op = c; num = 0; } int sum = 0; for (int t : st) sum += t; return sum; }
def calculate(s): st, num, op = [], 0, '+' # op: the operator before num for c in s + '+': # a sentinel closes the last number if c.isdigit(): num = num * 10 + int(c) elif c != ' ': if op == '+': st.append(num) elif op == '-': st.append(-num) elif op == '*': st.append(st.pop() * num) # * and / bind now else: t = st.pop() # truncate toward zero, not floor st.append(abs(t) // num if t >= 0 else -(abs(t) // num)) op, num = c, 0 return sum(st)
Forgetting the last number. The loop acts when an operator arrives, and the last number has none after it. The sentinel '+' closes it.
Basic Calculator II on "14-3/2". Which terms are on the stack before the sum?
− pushes −3, then / folds 2 into it: −3 / 2 truncates to −1. 14 − 1 = 13.
[ pushes the text so far and its count. ] repeats the inside and joins it back onto the parked text.
decodeString("3[a2[c]]")?
The inner frame gives "cc", so each outer copy is "acc", three times.
GIVEN · ASKEDAn encoded string where k[s] means s repeated k times, possibly nested. Return the decoded string.
k[...] repeats what is inside, and brackets nest: 3[a2[c]].
Each '[' opens a frame. Park the text built so far and the count on the stack, then build the inside from empty. At ']' the inside is repeated and joined to the parked text.
string decodeString(string s) { stack<pair<string, int>> st; // (text before '[', its repeat count) string cur; int k = 0; for (char c : s) { if (isdigit(c)) k = k * 10 + (c - '0'); // counts can be 100 else if (c == '[') { st.push({cur, k}); cur = ""; k = 0; } else if (c == ']') { pair<string, int> f = st.top(); st.pop(); string rep; for (int j = 0; j < f.second; j++) rep += cur; cur = f.first + rep; // fold the inner frame into the outer } else cur += c; } return cur; }
public String decodeString(String s) { Deque<String> texts = new ArrayDeque<>(); // text before each '[' Deque<Integer> counts = new ArrayDeque<>(); // and its repeat count StringBuilder cur = new StringBuilder(); int k = 0; for (char c : s.toCharArray()) { if (Character.isDigit(c)) k = k * 10 + (c - '0'); else if (c == '[') { texts.push(cur.toString()); counts.push(k); cur.setLength(0); k = 0; } else if (c == ']') { StringBuilder next = new StringBuilder(texts.pop()); int times = counts.pop(); for (int j = 0; j < times; j++) next.append(cur); cur = next; // fold the inner frame into the outer } else cur.append(c); } return cur.toString(); }
def decodeString(s): st, cur, k = [], "", 0 # st: (text before '[', its repeat count) for c in s: if c.isdigit(): k = k * 10 + int(c) # counts can be 100 elif c == '[': st.append((cur, k)) cur, k = "", 0 elif c == ']': prev, times = st.pop() cur = prev + cur * times # fold the inner frame into the outer else: cur += c return cur
Reading the count as one digit. 12[a] is twelve a's. Build k digit by digit, and reset it after the '['.
GIVEN · ASKEDA string with integers, + −, parentheses and spaces; − may be unary. Return its value without eval.
+, −, parentheses and a unary minus, as in -(2 + 3). No * or /.
Without * and / the value is a signed sum. A '(' parks the running result and the sign in front of the group; ')' finishes the group and folds it back in with that sign.
int calculate(string s) { stack<pair<long, int>> st; // (result before '(', sign in front of it) long result = 0, num = 0; int sign = 1; for (char c : s) { if (isdigit(c)) num = num * 10 + (c - '0'); else if (c == '+' || c == '-') { result += sign * num; num = 0; sign = c == '+' ? 1 : -1; // a unary minus is handled the same way } else if (c == '(') { st.push({result, sign}); // park the outer frame result = 0; sign = 1; } else if (c == ')') { result += sign * num; num = 0; pair<long, int> f = st.top(); st.pop(); result = f.first + f.second * result; // fold the group back in } } return result + sign * num; }
public int calculate(String s) { Deque<long[]> st = new ArrayDeque<>(); // {result before '(', sign in front of it} long result = 0, num = 0; int sign = 1; for (char c : s.toCharArray()) { if (Character.isDigit(c)) num = num * 10 + (c - '0'); else if (c == '+' || c == '-') { result += sign * num; num = 0; sign = c == '+' ? 1 : -1; // a unary minus is handled the same way } else if (c == '(') { st.push(new long[]{result, sign}); // park the outer frame result = 0; sign = 1; } else if (c == ')') { result += sign * num; num = 0; long[] f = st.pop(); result = f[0] + f[1] * result; // fold the group back in } } return (int) (result + sign * num); }
def calculate(s): st, result, num, sign = [], 0, 0, 1 # st: (result before '(', sign in front of it) for c in s: if c.isdigit(): num = num * 10 + int(c) elif c in '+-': result += sign * num num, sign = 0, (1 if c == '+' else -1) # a unary minus too elif c == '(': st.append((result, sign)) # park the outer frame result, sign = 0, 1 elif c == ')': result += sign * num num = 0 r, sg = st.pop() result = r + sg * result # fold the group back in return result + sign * num
Flipping the signs inside the group by hand. Only the sign in front of the '(' matters, and it is parked with the frame. Multiply the finished group by it once.
Basic Calculator on "1 - (2 - 3)". The frame parked at ( is (1, −1) and the group is −1. What is returned?
Fold the group in with the parked sign: 1 + (−1)·(−1) = 2.
GIVEN · ASKEDA boolean expression of t, f, !(…), &(…) and |(…). Return its value.
Nested !(…), &(…,…) and |(…,…) over t and f, any depth.
Push every character except commas. A ')' closes the innermost frame: pop its values down to '(', pop the operator, and push the frame's one-letter value.
bool parseBoolExpr(string expression) { stack<char> st; for (char c : expression) { if (c == ',') continue; if (c != ')') { st.push(c); continue; } // operators, '(' and values wait int t = 0, f = 0; // close the innermost frame while (st.top() != '(') { if (st.top() == 't') t++; else f++; st.pop(); } st.pop(); // the '(' char op = st.top(); st.pop(); bool v = op == '!' ? f > 0 : op == '&' ? f == 0 : t > 0; st.push(v ? 't' : 'f'); // the frame becomes one value } return st.top() == 't'; }
public boolean parseBoolExpr(String expression) { Deque<Character> st = new ArrayDeque<>(); for (char c : expression.toCharArray()) { if (c == ',') continue; if (c != ')') { st.push(c); continue; } // operators, '(' and values wait int t = 0, f = 0; // close the innermost frame while (st.peek() != '(') { if (st.pop() == 't') t++; else f++; } st.pop(); // the '(' char op = st.pop(); boolean v = op == '!' ? f > 0 : op == '&' ? f == 0 : t > 0; st.push(v ? 't' : 'f'); // the frame becomes one value } return st.peek() == 't'; }
def parseBoolExpr(expression): st = [] for c in expression: if c == ',': continue if c != ')': st.append(c) # operators, '(' and values wait continue t = f = 0 # close the innermost frame while st[-1] != '(': if st.pop() == 't': t += 1 else: f += 1 st.pop() # the '(' op = st.pop() v = f > 0 if op == '!' else (f == 0 if op == '&' else t > 0) st.append('t' if v else 'f') # the frame becomes one value return st[-1] == 't'
Evaluating the operator before its frame closes. An operand of & may itself be a frame. Only a ')' says every operand is known.
In &(t,|(f,t),f), which frame is evaluated first?
The first ) closes the innermost frame. Its value, t, then waits on the stack for &.
head and count are the whole state. The rear is (head + count) % k. Nothing is ever shifted.
k = 3. enQueue 1, 2, 3, then deQueue, then enQueue 4. Where is 4, and what is head?
head = 1 and count = 2, so the rear is (1 + 2) % 3 = 0.
Why keep count instead of only head and tail indices?
With only two indices, a full ring and an empty one look the same.
GIVEN · ASKEDDesign a circular queue of capacity k: enQueue, deQueue, Front, Rear, isEmpty, isFull.
A queue of fixed capacity k, every operation O(1), and no shifting.
A fixed array, a head index and a count. The rear is (head + count) % k, so both ends wrap round. Dequeue only moves head; the old value is simply no longer counted.
class MyCircularQueue { vector<int> a; int head = 0, count = 0; // the front slot, how many are live public: MyCircularQueue(int k) : a(k) {} bool enQueue(int value) { if (isFull()) return false; a[(head + count) % a.size()] = value; // the rear wraps round count++; return true; } bool deQueue() { if (isEmpty()) return false; head = (head + 1) % a.size(); // the old front is simply forgotten count--; return true; } int Front() { return isEmpty() ? -1 : a[head]; } int Rear() { return isEmpty() ? -1 : a[(head + count - 1) % a.size()]; } bool isEmpty() { return count == 0; } bool isFull() { return count == (int)a.size(); } };
class MyCircularQueue { private final int[] a; private int head = 0, count = 0; // the front slot, how many are live public MyCircularQueue(int k) { a = new int[k]; } public boolean enQueue(int value) { if (isFull()) return false; a[(head + count) % a.length] = value; // the rear wraps round count++; return true; } public boolean deQueue() { if (isEmpty()) return false; head = (head + 1) % a.length; // the old front is simply forgotten count--; return true; } public int Front() { return isEmpty() ? -1 : a[head]; } public int Rear() { return isEmpty() ? -1 : a[(head + count - 1) % a.length]; } public boolean isEmpty() { return count == 0; } public boolean isFull() { return count == a.length; } }
class MyCircularQueue: def __init__(self, k): self.a = [0] * k self.head = 0 # the front slot self.count = 0 # how many are live def enQueue(self, value): if self.isFull(): return False self.a[(self.head + self.count) % len(self.a)] = value # the rear wraps round self.count += 1 return True def deQueue(self): if self.isEmpty(): return False self.head = (self.head + 1) % len(self.a) # the old front is forgotten self.count -= 1 return True def Front(self): return -1 if self.isEmpty() else self.a[self.head] def Rear(self): return -1 if self.isEmpty() else self.a[(self.head + self.count - 1) % len(self.a)] def isEmpty(self): return self.count == 0 def isFull(self): return self.count == len(self.a)
head and tail with nothing else. When they meet, the queue could be full or empty. Keep a count, or leave one slot unused.
Push onto in, serve from out. Pour only when out is empty: each value moves once, O(1) amortised.
After a push, move the size − 1 older values from the front to the back. The front is always the top.
Queue from two stacks: push 1, push 2, pop, push 3, pop, pop. How many values move from in to out in total?
The first pop pours 1 and 2. The second finds 2 waiting. The third pours 3. Three moves.
GIVEN · ASKEDImplement a FIFO queue (push, pop, peek, empty) using only two stacks.
A FIFO queue using only stack operations, with every operation O(1) on average.
Push onto in. Serve from out. When out runs dry, pour all of in into it, which reverses it and puts the oldest on top. Each value is poured once.
class MyQueue { stack<int> in, out; // in: newest on top · out: oldest on top void shift() { if (out.empty()) // pour only when out has run dry while (!in.empty()) { out.push(in.top()); in.pop(); } } public: void push(int x) { in.push(x); } int pop() { shift(); int x = out.top(); out.pop(); return x; } int peek() { shift(); return out.top(); } bool empty() { return in.empty() && out.empty(); } };
class MyQueue { private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>(); private void shift() { // pour only when out has run dry if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop()); } public void push(int x) { in.push(x); } public int pop() { shift(); return out.pop(); } public int peek() { shift(); return out.peek(); } public boolean empty() { return in.isEmpty() && out.isEmpty(); } }
class MyQueue: def __init__(self): self.inn, self.out = [], [] # in: newest on top · out: oldest on top def _shift(self): if not self.out: # pour only when out has run dry while self.inn: self.out.append(self.inn.pop()) def push(self, x): self.inn.append(x) def pop(self): self._shift() return self.out.pop() def peek(self): self._shift() return self.out[-1] def empty(self): return not self.inn and not self.out
Pouring on every pop. Moving in to out while out still holds values buries older values under newer ones, and the order breaks.
GIVEN · ASKEDImplement a LIFO stack (push, pop, top, empty) using only queues.
A LIFO stack using only queue operations: push to the back, pop from the front, size.
Keep the queue in stack order, newest at the front. After pushing x to the back, move the size − 1 older values from the front to the back, one at a time.
class MyStack { queue<int> q; // the front of q is the top of the stack public: void push(int x) { q.push(x); for (int i = 0; i + 1 < (int)q.size(); i++) { // rotate the older ones behind x q.push(q.front()); q.pop(); } } int pop() { int x = q.front(); q.pop(); return x; } int top() { return q.front(); } bool empty() { return q.empty(); } };
class MyStack { private final Queue<Integer> q = new ArrayDeque<>(); // front of q = top of the stack public void push(int x) { q.add(x); for (int i = 0; i + 1 < q.size(); i++) q.add(q.poll()); // rotate the older ones behind x } public int pop() { return q.poll(); } public int top() { return q.peek(); } public boolean empty() { return q.isEmpty(); } }
from collections import deque class MyStack: def __init__(self): self.q = deque() # the front of q is the top of the stack def push(self, x): self.q.append(x) for _ in range(len(self.q) - 1): # rotate the older ones behind x self.q.append(self.q.popleft()) def pop(self): return self.q.popleft() def top(self): return self.q[0] def empty(self): return not self.q
Rotating size times instead of size − 1. One rotation too many moves x itself to the back, and the order is lost.
Stack from one queue, holding 3, 2, 1 from the front. After push 4, how many rotations were made, and what is the queue?
size − 1 = 3 rotations move 3, 2 and 1 behind 4, which now leads.
Nine moves, and each has a phrase in the statement that gives it away.
push the openers; a closer must match the top
MATCH THE TOPO(n)each item cancels the top or is pushed; the survivors are the answer
CANCEL WITH THE TOPO(n)store indices; the index below the run is a base, and i − top is its length
STACK OF INDICESO(n)each entry carries a summary of everything below it
CARRY A SUMMARYO(1) eachpush numbers; an operator pops two and pushes one
POSTFIX EVALUATIONO(n)pop what binds at least as tightly before pushing; * and / at once, + and − at the end
PRECEDENCEO(n)park the outer frame at the opener, fold the inner one back in at the closer
NESTED FRAMESO(n)head and count in a fixed array; both ends wrap with %
RING BUFFERO(1) eachpour in → out when out is empty; rotate size − 1 after a push
BUILD ONE FROM THE OTHERO(1) amortised · O(n) pushEach * in a string deletes the closest letter to its left that is not a star, and the star goes too. Which move solves it in one pass?
A star cancels the top letter. Push letters, pop on a star; the stack is the answer.
Score a balanced bracket string: () is 1, AB is A + B and (A) is 2·A. Which move?
Each '(' opens a frame that is scored at its ')' and folded into the frame around it.
Which of these needs the stack to start with a sentinel index, −1?
−1 is the base before index 0, so a run that starts at 0 can be measured as i − (−1).
A queue built from two stacks takes n pushes and n pops, in any order. What do they cost in total?
Each value is pushed, poured once and popped once: three stack operations each, 3n in all.
None of these crash on the samples. Each one fails a hidden test.
([)] has a closer for every opener and is still invalid. Only the order on a stack catches crossed pairs.
A closer or an operator with nothing below it. Check empty() first: in C++, top() on an empty stack is undefined.
The first pop is the right operand. a − b and a / b change if you swap them, and tests with only + and * never notice.
-7 // 2 is −4. The judges truncate toward zero and want −3.
a^b^c is a^(b^c). A ^ already waiting must stay when another ^ arrives.
In a ring, equal ends mean full or empty. Keep a count, or leave one slot unused.
Nine moves on one page. The right column is the cue for each.
Brackets matched against the top; letters cancelled it; indices measured runs; pairs carried a minimum; operators waited their turn; frames nested; a ring wrapped; and each structure was built from the other.
Module 12. Fifteen problems: fourteen on LeetCode, one on GeeksforGeeks. Next: the monotonic stack.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.