Previous Smaller Element

▶

Steps

setup

Initialize stack and result array

Start with an empty stack and an empty result array before processing any elements.

💡 Initialization is crucial to prepare data structures for the iteration over the input array.

Line:

stack = []
result = []

💡 The stack will hold indexes, and the result array will store previous smaller elements.

traverse

Process element 4 at index 0

Start iterating: current element is 4 at index 0. Stack is empty, so no previous smaller element exists.

💡 When the stack is empty, it means no smaller element has appeared before the current one.

Line:

for i, num in enumerate(arr):
    while stack and arr[stack[-1]] >= num:
        stack.pop()
    if stack:
        result.append(arr[stack[-1]])
    else:
        result.append(-1)
    stack.append(i)

💡 No previous smaller element for the first element; output -1.

traverse

Process element 5 at index 1

Current element is 5 at index 1. Top of stack is index 0 with element 4, which is smaller than 5, so no pop occurs.

💡 If the top element is smaller, it is the previous smaller element for the current element.

Line:

while stack and arr[stack[-1]] >= num:
    stack.pop()
if stack:
    result.append(arr[stack[-1]])
else:
    result.append(-1)
stack.append(i)

💡 The previous smaller element for 5 is 4, found at the top of the stack.

shrink

Process element 2 at index 2 - pop elements

Current element is 2 at index 2. Top of stack is index 1 with element 5, which is >= 2, so pop index 1.

💡 Pop elements from stack that are not smaller than current element to maintain monotonicity.

Line:

while stack and arr[stack[-1]] >= num:
    stack.pop()

💡 Removing indexes with elements >= current element ensures stack top is previous smaller.

shrink

Process element 2 at index 2 - pop again

Top of stack now index 0 with element 4, which is >= 2, so pop index 0 as well.

💡 Continue popping until top element is smaller or stack is empty.

Line:

while stack and arr[stack[-1]] >= num:
    stack.pop()

💡 Multiple pops can occur to find the correct previous smaller element.

insert

Process element 2 at index 2 - output result and push

Stack is empty after popping, so output -1 for element 2, then push index 2 onto stack.

💡 Empty stack means no previous smaller element exists.

Line:

if stack:
    result.append(arr[stack[-1]])
else:
    result.append(-1)
stack.append(i)

💡 Correctly handles no previous smaller element case after popping.

traverse

Process element 10 at index 3

Current element is 10 at index 3. Top of stack is index 2 with element 2, which is smaller than 10, so no pop.

💡 If top element is smaller, it is the previous smaller element.

Line:

while stack and arr[stack[-1]] >= num:
    stack.pop()
if stack:
    result.append(arr[stack[-1]])
else:
    result.append(-1)
stack.append(i)

💡 Previous smaller element for 10 is 2.

shrink

Process element 8 at index 4 - pop elements

Current element is 8 at index 4. Top of stack is index 3 with element 10, which is >= 8, so pop index 3.

💡 Pop elements not smaller than current to maintain monotonic stack.

Line:

while stack and arr[stack[-1]] >= num:
    stack.pop()

💡 Removes invalid candidates for previous smaller element.

insert

Process element 8 at index 4 - output result and push

Top of stack is index 2 with element 2, which is smaller than 8, so output 2 and push index 4.

💡 Stack top after popping is previous smaller element.

Line:

if stack:
    result.append(arr[stack[-1]])
else:
    result.append(-1)
stack.append(i)

💡 Correctly identifies previous smaller element after popping.

reconstruct

Final result assembled

All elements processed. The result array contains previous smaller elements for each input element.

💡 The final result array is the output of the algorithm.

Line:

return result

💡 The algorithm completed successfully with correct previous smaller elements.

def previous_smaller_element_indexes(arr):
    stack = []  # STEP 1: initialize stack
    result = [] # STEP 1: initialize result
    for i, num in enumerate(arr):  # STEP 2: iterate over elements
        while stack and arr[stack[-1]] >= num:  # STEP 4: pop while top >= current
            stack.pop()  # STEP 4: pop operation
        if stack:  # STEP 5: if stack not empty
            result.append(arr[stack[-1]])  # STEP 5: append previous smaller
        else:
            result.append(-1)  # STEP 5: append -1 if none
        stack.append(i)  # STEP 6: push current index
    return result  # STEP 10: return final result

if __name__ == '__main__':
    arr = [4, 5, 2, 10, 8]
    print(previous_smaller_element_indexes(arr))

📊

Previous Smaller Element - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation on the stack reveals how the algorithm efficiently skips unnecessary comparisons and maintains a monotonic property to find previous smaller elements in linear time.

no_op

Stack (top→bottom)

empty

pushElement[0]: 4

Stack (top→bottom)

0

↑ pushed: 0

Contributes: -1

pushElement[1]: 5

Stack (top→bottom)

1

0

↑ pushed: 1

Contributes: 4

popElement[2]: 2

Stack (top→bottom)

0

↓ popped: [1]

popElement[2]: 2

Stack (top→bottom)

empty

↓ popped: [0]

pushElement[2]: 2

Stack (top→bottom)

2

↑ pushed: 2

Contributes: -1

pushElement[3]: 10

Stack (top→bottom)

3

2

↑ pushed: 3

Contributes: 2

popElement[4]: 8

Stack (top→bottom)

2

↓ popped: [3]

pushElement[4]: 8

Stack (top→bottom)

4

2

↑ pushed: 4

Contributes: 2

no_opElement[4]: 8

Stack (top→bottom)

4

2

Contributes: [-1,4,-1,2,2]

Key Takeaways

✓ The stack maintains indexes of elements in strictly increasing order by their values, enabling O(n) time complexity.

This insight is hard to see from code alone because the popping and pushing logic is subtle and intertwined.

✓ When processing each element, popping all elements greater or equal to it ensures the top of the stack is always the previous smaller element.

Visualizing the stack changes clarifies why multiple pops can happen before pushing the current index.

✓ If the stack is empty after popping, it means no previous smaller element exists, so the algorithm outputs -1 for that element.

This decision branch is critical and often overlooked without step-by-step visualization.

Practice

1. Given the following code for finding the first unique character in a stream, what is the output after processing the input stream ['a', 'b', 'a']?

from collections import deque

def first_unique_stream(stream):
    freq = [0] * 26
    q = deque()
    result = []
    for ch in stream:
        idx = ord(ch) - ord('a')
        freq[idx] += 1
        if freq[idx] == 1:
            q.append(ch)
        while q and freq[ord(q[0]) - ord('a')] > 1:
            q.popleft()
        result.append(q[0] if q else '#')
    return result

print(first_unique_stream(['a', 'b', 'a']))

easy

A. ['a', 'b', '#']

B. ['a', 'a', '#']

C. ['a', 'a', 'b']

D. ['a', 'b', 'b']

Solution

1. Step 1: Trace first iteration with 'a'

   freq['a'] = 1, queue = ['a'], first unique = 'a'

2. Step 2: Trace second iteration with 'b'

   freq['b'] = 1, queue = ['a', 'b'], first unique still 'a' since freq['a'] = 1

3. Step 3: Trace third iteration with 'a'

   freq['a'] = 2, queue front 'a' freq > 1, pop 'a', queue now ['b'], first unique = 'b'

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Queue updates correctly remove duplicates [OK]

Hint: Queue front always holds current first unique or empty [OK]

Common Mistakes:

• Not popping duplicates from queue front
• Appending duplicates to queue multiple times
• Returning wrong character after duplicates

2. You are given a string containing only the characters '(', ')', '{', '}', '[' and ']'. You need to determine if the string is valid, meaning every opening bracket has a corresponding closing bracket in the correct order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that matches pairs as soon as they appear from left to right

B. Dynamic programming approach that stores valid substrings and merges them

C. Brute force approach that repeatedly removes valid pairs until no pairs remain

D. Stack-based approach that pushes opening brackets and matches them with closing brackets

Solution

1. Step 1: Understand problem constraints

   The problem requires matching brackets in correct order, which is naturally suited for a LIFO structure to track the most recent unmatched opening bracket.

2. Step 2: Evaluate approaches

   Greedy fails on nested or interleaved brackets; DP is overkill and complex; brute force is inefficient. Stack-based approach efficiently tracks opening brackets and matches them with closing ones in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach matches pairs in order with linear time [OK]

Hint: Stack matches nested pairs in correct order [OK]

Common Mistakes:

• Assuming greedy matching works for nested brackets

3. Consider this buggy version of the decodeString function. Which line contains the subtle bug that causes incorrect decoding for inputs with multiple bracketed substrings?

medium

A. Line appending current_string to string_stack

B. Line popping count from count_stack

C. Line resetting k after '[' is missing

D. Line appending characters to current_string

Solution

1. Step 1: Identify where repeat count is reset

   After pushing k to count_stack on '[', k must be reset to 0 to avoid carryover to next substring.

2. Step 2: Locate missing reset

   The code comment indicates missing reset of k after pushing it, causing subsequent repeats to accumulate incorrectly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting k prevents repeat count carryover bugs [OK]

Hint: Repeat count must reset after pushing to stack [OK]

Common Mistakes:

• Forgetting to reset repeat count after '['
• Mismanaging stack push/pop order

4. What is the time complexity of the optimal maximalRectangle solution that uses row-wise histogram transformation and largestRectangleArea with a monotonic stack for a matrix of size rows x cols?

medium

A. O(rows^2 * cols^2)

B. O(rows * cols^2)

C. O(rows^2 * cols)

D. O(rows * cols)

Solution

1. Step 1: Analyze outer loop over rows and inner loop over columns

   For each row, heights array is updated in O(cols) time.

2. Step 2: Analyze largestRectangleArea call per row

   largestRectangleArea uses a monotonic stack with O(cols) amortized time per call.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each row processed in O(cols), total O(rows * cols) [OK]

Hint: Each row processed once, stack operations amortize to O(cols) [OK]

Common Mistakes:

• Confusing nested loops leading to O(rows * cols^2)
• Assuming stack operations are O(cols^2)
• Forgetting amortized analysis

5. What is the time complexity of the optimal monotonic stack solution that uses an explicit circular array copy (doubling the array) for the Next Greater Element II problem, and why?

medium

A. O(n) because each element is pushed and popped at most once despite doubling

B. O(n²) because the doubled array doubles the iterations

C. O(n log n) due to sorting implicit in stack operations

D. O(2n) which simplifies to O(n) but requires extra space

Solution

1. Step 1: Identify loop iterations

   The loop runs over doubled array of length 2n, so 2n iterations.

2. Step 2: Analyze stack operations

   Each element index is pushed once and popped once at most, so total stack operations are O(n). The doubling does not cause repeated pushes for the same index.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Doubling array length does not multiply complexity beyond linear [OK]

Hint: Each element pushed/popped once -> O(n) despite doubled array [OK]

Common Mistakes:

• Assuming doubling array doubles complexity to O(n²)
• Confusing stack operations with sorting complexity
• Ignoring that indices are pushed only once