Push onto a Stack with a Capacity Limit
Solve this ProblemEasy10 min
Topics
BasicsStack
Companies
TCSInfosysWipro
Push each value of
values, in order, onto an empty stack that can hold at most capacity items. A push onto a full stack is ignored. Return the stack's contents from bottom to top.
A stackStackA last-in, first-out (LIFO) collection: items are added and removed only at the top. only lets you work at one end, the top. PushPushAdding an item to the top of a stack. adds there — but a stack stored in a fixed-size array can run out of room, and pushing anyway is a stack overflowStack OverflowTrying to push onto a stack that is already full.. Checking for space before every push is the core habit this exercise practises.
Test Case 1:
Input:values = [4, 7, 1, 9], capacity = 3
Output:[4, 7, 1]
Explanation:After three pushes the stack is full; pushing 9 would overflow, so it is refused.
Test Case 2:
Input:values = [5, 6], capacity = 4
Output:[5, 6]
Explanation:Plenty of room — both values are pushed.
Constraints
- ◆
1 ≤ values.length ≤ 1000 - ◆
1 ≤ capacity ≤ 1000 - ◆
-1000000 ≤ values[i] ≤ 1000000
Try the Dry Run
Approach & Solutions
Array with a Top IndexOptimal
A stack can live in a plain array of size capacity plus an index top that marks the last filled slot (−1 when empty). To push, first check there is room (top + 1 < capacity), then move top up by one and store the value there. A push onto a full stack — an overflow — is refused. Return the filled part, bottom to top.
Time
O(n)Space
O(capacity)Java
class Solution {
public int[] pushWithCapacity(int[] values, int capacity) {
int[] stack = new int[capacity];
int top = -1;
for (int value : values) {
if (top + 1 < capacity) {
stack[++top] = value;
}
}
return Arrays.copyOf(stack, top + 1);
}
}Growable List with a Size CheckGood
Use a growable list as the stack — push appends to its end — and enforce the limit yourself by checking the size before each push. C has no growable list, so it keeps the array and top index.
Time
O(n)Space
O(capacity)Java
class Solution {
public int[] pushWithCapacity(int[] values, int capacity) {
List<Integer> stack = new ArrayList<>();
for (int value : values) {
if (stack.size() < capacity) {
stack.add(value);
}
}
return stack.stream().mapToInt(Integer::intValue).toArray();
}
}