Practice/Google/Leetcode 1381. Design a Stack With Increment Operation

Leetcode 1381. Design a Stack With Increment Operation

CodingMust

Problem

Design and implement a specialized stack data structure that supports standard stack operations with a capacity limit, plus an efficient bulk increment operation.

Your CustomStack class should support the following operations:

• Constructor: Initialize the stack with a maximum capacity maxSize
• push(x): Add element x to the top of the stack if it hasn't reached maximum capacity
• pop(): Remove and return the top element of the stack. Return -1 if the stack is empty
• increment(k, val): Add val to the bottom k elements of the stack. If there are fewer than k elements, increment all elements in the stack

The key challenge is implementing the increment operation efficiently. A naive approach would iterate through k elements, resulting in O(k) time complexity. Your goal is to optimize this using lazy propagation or differential tracking techniques to achieve O(1) time complexity for all operations.

Requirements

1. Implement a bounded stack that respects the maxSize constraint
2. The push operation should only add elements when there's available space
3. The pop operation must return -1 for an empty stack
4. The increment operation should efficiently add values to the bottom portion of the stack
5. All operations should run in O(1) amortized time complexity

Constraints

• 1 ≤ maxSize ≤ 1000
• 1 ≤ x ≤ 1000 (values being pushed)
• 1 ≤ k ≤ 1000
• 0 ≤ val ≤ 100
• At most 1000 calls will be made to each method

Examples

Example 1:

` Operations: ["CustomStack", "push", "push", "pop", "push", "increment", "pop", "pop"] Arguments: [[3], [1], [2], [], [3], [2, 50], [], []] Output: [null, null, null, 2, null, null, 52, 51]

Explanation:

• CustomStack(3): Initialize with max size 3
• push(1): Stack becomes [1]
• push(2): Stack becomes [1, 2]
• pop(): Returns 2, stack becomes [1]
• push(3): Stack becomes [1, 3]
• increment(2, 50): Add 50 to bottom 2 elements, stack becomes [51, 53]
• pop(): Returns 53, stack becomes [51]
• pop(): Returns 51, stack becomes [] `

Example 2:

` Operations: ["CustomStack", "push", "push", "push", "push", "increment", "pop"] Arguments: [[2], [1], [2], [3], [4], [3, 100], []] Output: [null, null, null, null, null, null, 102]

Explanation:

• CustomStack(2): Initialize with max size 2
• push(1): Stack becomes [1]
• push(2): Stack becomes [1, 2]
• push(3): Stack is full, no change
• push(4): Stack is full, no change
• increment(3, 100): Only 2 elements exist, both get incremented, stack becomes [101, 102]
• pop(): Returns 102 `