Abstract / Summary

Design a stack that supports push pop top and increment operations on a range of elements.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 80% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Design
• Stack

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided CustomStack class implements a bounded stack with three core operations: initialization, push, pop, and an incremental update of the bottom elements. The design relies on Python’s built-in list to store stack elements and enforces a maximum capacity supplied at construction time. Each method contains conditional logic that guards against out-of-range actions, ensuring predictable behavior when the stack is empty, full, or when the increment request exceeds the current size.

Initialization

The constructor receives an integer maxSize that defines the stack’s capacity. Two instance attributes are created: data, an empty list that will hold the stack elements, and capacity, which stores the maximum allowed size.

def __init__(self, maxSize: int):
    self.data = []
    self.capacity = maxSize

By separating the storage (data) from the limit (capacity), the class can quickly check whether a new element can be added without scanning the list.

Push Operation

The push method adds a new integer x to the top of the stack only if the current number of elements is less than the predefined capacity. The length check is performed with len(self.data) < self.capacity, and when the condition holds, x is appended to the list.

def push(self, x: int) -> None:
    if len(self.data) < self.capacity:
        self.data.append(x)

Appending to a Python list is an amortized constant-time operation, making the push operation efficient while respecting the size constraint.

Pop Operation

The pop method removes and returns the top element of the stack. If the stack contains at least one element, list.pop() is invoked, which removes the last item. When the stack is empty, the method returns -1 as a sentinel value.

def pop(self) -> int:
    return self.data.pop() if self.data else -1

The conditional expression ensures that an attempt to pop from an empty stack does not raise an exception, providing a graceful fallback.

Increment Operation

The increment method adds a given value val to each of the bottom k elements of the stack. The loop iterates over the range defined by the smaller of the current stack size and k, preventing index errors when k exceeds the number of stored elements.

def increment(self, k: int, val: int) -> None:
    for i in range(min(len(self.data), k)):
        self.data[i] += val

By using min(len(self.data), k), the method automatically adapts to the actual stack depth, applying the increment only where elements exist.

Edge Cases

When the stack is empty, the pop method returns -1 instead of attempting to remove an element, thereby avoiding an IndexError. The push method silently discards any insertion request that would exceed the predefined capacity, ensuring the stack never grows beyond its limit. In the increment method, if k is larger than the current number of elements, the loop bounds are reduced to the actual size, so the operation affects only the existing elements without accessing invalid indices.

Performance Considerations

The implementation leverages Python’s list for storage, which provides fast append and pop operations at the end of the list. The capacity check in push is a simple length comparison, allowing the method to decide instantly whether to accept a new element. The increment method iterates only over the necessary portion of the stack, thanks to the min function that caps the loop at the smaller of k and the current size. This prevents unnecessary work when k is larger than the stack, keeping the operation proportional to the actual number of elements that need to be updated. The overall design keeps each operation as lightweight as possible while maintaining clear and deterministic behavior.

Imagine a special box that holds blocks stacked on top of one another. The box has a limit on how many blocks it can hold, so it cannot get too full.

The first part of the code sets up the box and decides how many blocks can fit inside.

When it is time to add a new block, the box checks to see if there is still enough space. If there is, the block goes right on top of the pile.

When it is time to take a block out, the box looks at the one sitting right on the very top of the stack and picks it up. If someone tries to take a block out but the box is empty, it just lets them know there is nothing there to grab.

Sometimes, you might want to make the blocks already inside the box a little bit taller. The last part of the code looks at the bottom few blocks in the stack and adds the same amount of height to each of them.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java				Go	TS
	Progiez	C++	Python		Java
github	BigEggStudy						C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	DimitrisJim							C
	everthis			JS
	fartem					Ruby
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	varunu28				Java
	wisdompeak	C++
	withaarzoo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
varunu28	Java
wisdompeak	C++
withaarzoo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality