DDSA Solutions

1381. Design a Stack With Increment Operation

UnknownView on LeetCode
StackDesignArray

Problem Overview

Custom stack with increment operation on bottom k elements.

Intuition

Custom stack with increment operation on bottom k elements. Use lazy increment array to handle increment in O(1) amortized.

Algorithm

  1. 1Stack + inc[] array. inc[i] = pending increment for elements at positions 0..i.
  2. 2push: push value. pop: return stack.top + inc[top_index], propagate inc down.
  3. 3increment(k, val): inc[min(k,size)-1] += val.

Common Pitfalls

  • •Lazy propagation: when popping, add inc[i] to value and propagate: inc[i-1] += inc[i], inc[i]=0.
1381.cs
C#
// Approach: Lazy increment array; increment(k, val) adds val to pendingIncrements[k-1]; propagates down on pop.
// Time: O(1) per op Space: O(n)

public class CustomStack
{
    private int maxSize;
    private Stack<int> stack = new Stack<int>();
    private List<int> pendingIncrements = new List<int>();
    public CustomStack(int maxSize)
    {
        this.maxSize = maxSize;
    }

    public void Push(int x)
    {
        if (stack.Count == maxSize)
            return;
        stack.Push(x);
        pendingIncrements.Add(0);
    }

    public int Pop()
    {
        if (stack.Count == 0)
            return -1;
        int i = stack.Count - 1;
        int pendingIncrement = pendingIncrements[i];
        pendingIncrements.RemoveAt(i);
        if (i > 0)
            pendingIncrements[i - 1] += pendingIncrement;
        return stack.Pop() + pendingIncrement;
    }

    public void Increment(int k, int val)
    {
        if (stack.Count == 0)
            return;
        int i = Math.Min(k - 1, stack.Count - 1);
        pendingIncrements[i] += val;
    }
}
Was this solution helpful?

Related Problems