Pop Items from a Stack
Solve this ProblemEasy10 min
Topics
BasicsStack
Companies
TCSInfosysWipro
A stack is given as an array from bottom to top. Pop up to
k items from it and return the popped values in the order they came off. If the stack runs empty first, stop.
PopPopRemoving and returning the item at the top of a stack. removes from the top — the most recently added item — which is the LIFOLIFO (Last In, First Out)The rule that the most recently added item is the first one removed. rule. Popping an empty stack is called stack underflowStack UnderflowTrying to pop from a stack that has no items., and every pop must guard against it.
Test Case 1:
Input:stack = [3, 8, 5], k = 2
Output:[5, 8]
Explanation:The top is the last element, 5; popping twice removes 5 then 8.
Test Case 2:
Input:stack = [3, 8], k = 4
Output:[8, 3]
Explanation:After two pops the stack is empty; further pops would underflow, so they stop.
Constraints
- ◆
0 ≤ stack.length ≤ 1000 (given bottom to top) - ◆
1 ≤ k ≤ 1000 - ◆
-1000000 ≤ stack[i] ≤ 1000000
Try the Dry Run
Approach & Solutions
Move the Top Index DownOptimal
The array holds the stack from bottom to top, so the top is the last index. Each pop reads stack[top] and moves top down by one. Stop after k pops or as soon as top drops below 0 — popping an empty stack is an underflow.
Time
O(k)Space
O(k)Java
class Solution {
public int[] popItems(int[] stack, int k) {
int top = stack.length - 1;
int[] popped = new int[Math.min(k, stack.length)];
int count = 0;
while (count < k && top >= 0) {
popped[count++] = stack[top--];
}
return popped;
}
}Built-in Pop on a CopyGood
Copy the values into the language's list and use its own pop: remove the last element in Java, pop() in Python and JavaScript, back() and pop_back() in C++. Working on a copy leaves the input untouched. C has no built-in, so it keeps the top index.
Time
O(n + k)Space
O(n)Java
class Solution {
public int[] popItems(int[] stack, int k) {
List<Integer> items = new ArrayList<>();
for (int value : stack) {
items.add(value);
}
List<Integer> popped = new ArrayList<>();
while (popped.size() < k && !items.isEmpty()) {
popped.add(items.remove(items.size() - 1));
}
return popped.stream().mapToInt(Integer::intValue).toArray();
}
}