LeetCode 895 - Maximum Frequency Stack

The problem is asking us to design a custom stack-like data structure that supports two operations: pushing values onto the stack and popping the most frequent element.

leetcodehardhash-tablestackdesignordered-set

LeetCode Problem 895

Difficulty: 🔴 Hard
Topics: Hash Table, Stack, Design, Ordered Set

Solution

Problem Understanding

The problem is asking us to design a custom stack-like data structure that supports two operations: pushing values onto the stack and popping the most frequent element. A key difference from a traditional stack is that the pop operation does not necessarily remove the element at the top; instead, it removes the element with the highest frequency. If multiple elements share the same frequency, the one closest to the top of the stack should be removed.

The input consists of a series of push and pop operations. Each push adds a value to the stack, and each pop returns the most frequent element according to the rules described. The expected output for pop is an integer corresponding to the removed element.

Constraints indicate that val can be up to 10^9 and that there can be up to 2 * 10^4 operations, which suggests that any solution must handle frequent lookups and updates efficiently. The guarantee that pop will only be called when the stack is non-empty simplifies error handling.

Edge cases to consider include pushing the same element multiple times, popping when multiple elements share the same frequency, and handling large numbers of operations efficiently.

Approaches

A brute-force approach would maintain a standard stack and, for each pop, scan the stack to find the element with the highest frequency, removing it. This ensures correctness but is inefficient. Each pop would require scanning potentially the entire stack, making the time complexity O(n) per pop, where n is the current stack size. Over 2 * 10^4 operations, this approach may be too slow.

The key observation for an optimal approach is that we only need fast access to the elements with the highest frequency. Using a hash map to track frequencies and a secondary mapping from frequency to stacks of values allows us to push and pop in constant time. Each pop simply removes the most recent element from the stack corresponding to the current maximum frequency, and the maximum frequency is updated dynamically.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per pop O(n) Uses a single stack and scans it for the most frequent element on each pop
Optimal O(1) per push/pop O(n) Uses hash maps and a frequency-stack mapping to track elements efficiently

Algorithm Walkthrough

  1. Initialize a hash map freq to store the frequency of each value.
  2. Initialize a hash map group where keys are frequencies and values are stacks of elements with that frequency.
  3. Maintain a variable maxfreq to track the current maximum frequency in the stack.
  4. For push(val), increment freq[val]. Push val onto group[freq[val]]. Update maxfreq if necessary.
  5. For pop(), take the element from group[maxfreq] (the top of the stack corresponding to the current maximum frequency). Decrement its frequency in freq[val]. If group[maxfreq] becomes empty, decrement maxfreq.
  6. Return the popped element.

This works because group always contains the most recently added elements for each frequency. By popping from the top of group[maxfreq], we satisfy both the frequency and stack order constraints.

Python Solution

class FreqStack:

    def __init__(self):
        self.freq = {}  # maps val -> frequency
        self.group = {}  # maps frequency -> stack of vals
        self.maxfreq = 0

    def push(self, val: int) -> None:
        f = self.freq.get(val, 0) + 1
        self.freq[val] = f
        if f not in self.group:
            self.group[f] = []
        self.group[f].append(val)
        self.maxfreq = max(self.maxfreq, f)

    def pop(self) -> int:
        val = self.group[self.maxfreq].pop()
        self.freq[val] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1
        return val

The push method increments the frequency for the value and appends it to the stack corresponding to that frequency. The pop method retrieves the most recent element with the maximum frequency, decrements its frequency, and adjusts maxfreq if necessary. This ensures O(1) time for both operations.

Go Solution

type FreqStack struct {
    freq    map[int]int
    group   map[int][]int
    maxfreq int
}

func Constructor() FreqStack {
    return FreqStack{
        freq:  make(map[int]int),
        group: make(map[int][]int),
    }
}

func (this *FreqStack) Push(val int) {
    this.freq[val]++
    f := this.freq[val]
    this.group[f] = append(this.group[f], val)
    if f > this.maxfreq {
        this.maxfreq = f
    }
}

func (this *FreqStack) Pop() int {
    vals := this.group[this.maxfreq]
    val := vals[len(vals)-1]
    this.group[this.maxfreq] = vals[:len(vals)-1]
    this.freq[val]--
    if len(this.group[this.maxfreq]) == 0 {
        this.maxfreq--
    }
    return val
}

In Go, slices are used as stacks. We append to push and slice to pop the top element. The rest of the logic mirrors the Python implementation. The map data structures ensure constant-time frequency and group lookups.

Worked Examples

Consider the input:

push(5), push(7), push(5), push(7), push(4), push(5), pop(), pop(), pop(), pop()
Operation freq map group map maxfreq Output
push(5) {5:1} {1:[5]} 1 -
push(7) {5:1,7:1} {1:[5,7]} 1 -
push(5) {5:2,7:1} {1:[5,7], 2:[5]} 2 -
push(7) {5:2,7:2} {1:[5,7], 2:[5,7]} 2 -
push(4) {5:2,7:2,4:1} {1:[5,7,4], 2:[5,7]} 2 -
push(5) {5:3,7:2,4:1} {1:[5,7,4], 2:[5,7], 3:[5]} 3 -
pop() {5:2,7:2,4:1} {1:[5,7,4], 2:[5,7], 3:[]} 2 5
pop() {5:2,7:1,4:1} {1:[5,7,4], 2:[5]} 2 7
pop() {5:1,7:1,4:1} {1:[5,7,4], 2:[]} 1 5
pop() {5:1,7:1,4:0} {1:[5,7]} 1 4

Complexity Analysis

Measure Complexity Explanation
Time O(1) per operation Hash map and stack operations are constant time
Space O(n) We store each element in freq map and group map once

The constant-time operations are achieved by maintaining frequency-based stacks and tracking the current maximum frequency.

Test Cases

# Provided example
fs = FreqStack()
fs.push(5)
fs.push(7)
fs.push(5)
fs.push(7)
fs.push(4)
fs.push(5)
assert fs.pop() == 5  # most frequent
assert fs.pop() == 7  # tie, closest to top
assert fs.pop() == 5  # most frequent
assert fs.pop() == 4  # tie, closest to top

# Edge case: all elements unique
fs2 = FreqStack()
fs2.push(1)
fs2.push(2)
fs2.push(3)
assert fs2.pop() == 3
assert fs2.pop() == 2
assert fs2.pop() == 1

# Edge case: single element repeated
fs3 = FreqStack()
fs3.push(10)
fs3.push(10)
fs3.push(10)
assert fs3.pop() == 10
assert fs3.pop() == 10
assert fs3.pop() == 10

# Stress test: alternating push and pop
fs4 = FreqStack()
for i in range(100):
    fs4.push(i)
for i in reversed(range(100)):
    assert fs4.pop() == i
Test Why
Provided example Validates typical use with frequency ties
All unique Ensures stack order is respected when frequencies are equal
Single element repeated Ensures frequency decrement works correctly
Stress test Checks performance and correctness for multiple operations

Edge Cases

One important edge case is when multiple elements share the maximum frequency. The implementation correctly returns the one closest to the top