Design a Stack With Increment Operation - Practice Coding Problems

Design a Stack With Increment Operation - Problem

Design a stack that supports increment operations on its elements.

Implement the CustomStack class:

CustomStack(int maxSize) - Initializes the object with maxSize which is the maximum number of elements in the stack.
void push(int x) - Adds x to the top of the stack if the stack has not reached the maxSize.
int pop() - Pops and returns the top of the stack or -1 if the stack is empty.
void inc(int k, int val) - Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, increment all the elements in the stack.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["CustomStack","push","push","pop","increment","pop","pop","pop"], values = [[3],[1],[2],[],[2,100],[],[],[]]

› Output: [null,null,null,2,null,101,100,-1]

💡 Note: Create stack with maxSize=3, push 1 and 2, pop returns 2, increment bottom 2 elements by 100, then pop returns 101, 100, and -1 (empty)

Example 2 — Full Stack

$ Input: operations = ["CustomStack","push","push","push","push"], values = [[2],[1],[2],[3],[4]]

› Output: [null,null,null,null,null]

💡 Note: Stack has maxSize=2, so only first 2 push operations add elements, remaining pushes are ignored

Example 3 — Empty Stack Operations

$ Input: operations = ["CustomStack","pop","increment"], values = [[1],[],[3,100]]

› Output: [null,-1,null]

💡 Note: Pop from empty stack returns -1, increment on empty stack does nothing

Constraints

1 ≤ maxSize ≤ 1000
1 ≤ x ≤ 1000
1 ≤ k ≤ 1000
0 ≤ val ≤ 100
At most 1000 calls will be made to each method of push, pop and increment.

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of operations: push(1), push(2), pop(), increment(2,100)

Process

Stack maintains elements and applies increments efficiently

Output

Returns values: [2, 101, 100, -1]

Key Takeaway

🎯 Key Insight: Use lazy propagation to defer increment operations until elements are popped, achieving O(1) time complexity for all operations.

Asked in

a Amazon 12 G Google 8 M Microsoft 6 f Facebook 4

The key insight is to use lazy propagation with an additional increment array. Instead of updating elements immediately, store increment values and apply them during pop operations. The optimal approach uses lazy propagation achieving O(1) time for all operations. Time: O(1), Space: O(maxSize).

Common Approaches

Approach	Time	Space	Notes
✓ Array with Direct Increment	O(k)	O(n)	Use array as stack and directly increment elements during inc operation
Lazy Propagation with Increment Array	O(1)	O(n)	Use additional array to store pending increments and apply them during pop

Array with Direct Increment — Algorithm Steps

Use array to store stack elements
Track current size with pointer
For inc(), iterate and add value to each element

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Operations

Elements added to stack array

Increment Operation

Iterate through bottom k elements

Pop Operations

Remove elements from top

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* stack;
    int size;
    int maxSize;
} CustomStack;

CustomStack* createStack(int maxSize) {
    CustomStack* stack = (CustomStack*)malloc(sizeof(CustomStack));
    stack->stack = (int*)malloc(maxSize * sizeof(int));
    stack->size = 0;
    stack->maxSize = maxSize;
    return stack;
}

void push(CustomStack* stack, int x) {
    if (stack->size < stack->maxSize) {
        stack->stack[stack->size++] = x;
    }
}

int pop(CustomStack* stack) {
    if (stack->size == 0) {
        return -1;
    }
    return stack->stack[--stack->size];
}

void increment(CustomStack* stack, int k, int val) {
    int limit = (k < stack->size) ? k : stack->size;
    for (int i = 0; i < limit; i++) {
        stack->stack[i] += val;
    }
}

int main() {
    CustomStack* stack = createStack(3);
    
    push(stack, 1);
    push(stack, 2);
    printf("%d,", pop(stack));
    increment(stack, 2, 100);
    printf("%d,", pop(stack));
    printf("%d\n", pop(stack));
    
    free(stack->stack);
    free(stack);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Push/pop are O(1), but increment takes O(k) time to update k elements

✓ Linear Growth

Space Complexity

O(n)

Array to store up to maxSize elements

⚡ Linearithmic Space

89.6K Views

Medium Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Array with Direct Increment — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler