Design a stack with increment operation

Array Stack Design

79.9% acceptance

Feb 23, 2026

2365

112

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

pub struct CustomStack {
  data: Vec<i32>,
  inc: Vec<i32>, // lazy increment array
  max_size: usize,
}

impl CustomStack {
  pub fn new(max_size: i32) -> Self {
    let max_size = max_size as usize;
    CustomStack { data: Vec::new(), inc: vec![0; max_size], max_size }
  }

  pub fn push(&mut self, x: i32) {
    if self.data.len() < self.max_size {
      self.data.push(x);
    }
  }

  pub fn pop(&mut self) -> i32 {
    if self.data.is_empty() { return -1; }
    let top = self.data.len() - 1;
    let val = self.data.pop().unwrap() + self.inc[top];
    if top > 0 { self.inc[top - 1] += self.inc[top]; }
    self.inc[top] = 0;
    val
  }

  pub fn increment(&mut self, k: i32, val: i32) {
    let n = self.data.len();
    if n == 0 { return; }
    let idx = (k as usize).min(n) - 1;
    self.inc[idx] += val;
  }
}