Maximum Frequency Stack — Day 86(Python)

Photo by Iva Rajović on Unsplash

Today’s question is from Daily Leetcode Challenge — February Edition. It is a hard-tagged question. I had to go through the leetcode’s solution to understand the answer.

895. Maximum Frequency Stack

Implement , a class which simulates the operation of a stack-like data structure.

has two functions:

  • , which pushes an integer onto the stack.
  • , which removes and returns the most frequent element in the stack.
  • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top. Then:
pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].
pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].
pop() -> returns 5.
The stack becomes [5,7,4].
pop() -> returns 4.
The stack becomes [5,7].

Note:

  • Calls to will be such that .
  • It is guaranteed that won't be called if the stack has zero elements.
  • The total number of calls will not exceed in a single test case.
  • The total number of calls will not exceed in a single test case.
  • The total number of and calls will not exceed across all test cases.

We have to implement a Stack. A Stack follows the LIFO concept. What does LIFO mean? LIFO stands for Last In First Out i.e elements that are inserted first in the stack are removed last from the stack. In the problem statement, we need to create a stack, based on its frequency as well as its time of insertion. This means elements that have a higher frequency are removed first from the stack. If two elements have the same frequency, the element which was inserted latest is removed from the stack.

How can we keep track of both frequency and timing? We can make use of a dictionary, that will keep track of the frequency of items each time they are inserted in the stack.

How can we keep track of max frequency though? Do we have to go through each frequency in the dictionary to find the max frequency? We can make use of a variable that will keep track of max frequency whenever a new element is inserted.

To keep track of elements with the same frequency, we can have another dictionary where the key is the frequency and the value are the elements with the same frequency.

What about the case when we pop elements from our stack? Since we have stored the max frequency value in a variable, we will use this max frequency as a key in our dictionary and pop the element from the dictionary. Once there is no more element that has the same max frequency, we will decrement the value of max frequency by one.

Let us look into the code snippet.

import collections
class FreqStack:
def __init__(self):
self.frequency_dict = collections.Counter()
self.same_freq = collections.defaultdict(list)
self.max_freq = -1
def push(self, x: int) -> None:
self.frequency_dict[x] += 1
self.same_freq[self.frequency_dict[x]].append(x)
if self.frequency_dict[x] > self.max_freq:
self.max_freq = self.frequency_dict[x]
def pop(self) -> int:
output = self.same_freq[self.max_freq].pop()
self.frequency_dict[output] -= 1
if self.same_freq[self.max_freq] == []:
self.max_freq -= 1
return output

Complexity analysis.

Time Complexity

Since we are not traversing through the entire dictionary to push or pop, the time complexity is O(1).

Space Complexity

Since we are using dictionaries to store our elements and their frequency, the space complexity is O(N).

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store