Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Problem Challenge 3: Frequency Stack
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Design a class that simulates a Stack data structure, implementing the following two operations:

  1. push(int num): Pushes the number ‘num’ on the stack.
  2. pop(): Returns the most frequent number in the stack. If there is a tie, return the number which was pushed later.

Example:

After following push operations: push(1), push(2), push(3), push(2), push(1), push(2), push(5)

1. pop() should return 2, as it is the most frequent number
2. Next pop() should return 1
3. Next pop() should return 2

Constraints:

  • 0 <= val <= 10<sup>9</sup>
  • At most 2 * 10<sup>4</sup> calls will be made to push and pop.
  • It is guaranteed that there will be at least one element in the stack before calling pop.

Solution

This problem follows the Top ‘K’ Elements pattern, and shares similarities with Top ‘K’ Frequent Numbers.

We can use a Max Heap to store the numbers. Instead of comparing the numbers we will compare their frequencies so that the root of the heap is always the most frequently occurring number. There are two issues that need to be resolved though:

  1. How can we keep track of the frequencies of numbers in the heap? When we are pushing a new number to the Max Heap, we don’t know how many times the number has already appeared in the Max Heap. To resolve this, we will maintain a HashMap to store the current frequency of each number. Thus whenever we push a new number in the heap, we will increment its frequency in the HashMap and when we pop, we will decrement its frequency.
  2. If two numbers have the same frequency, we will need to return the number which was pushed later while popping. To resolve this, we need to attach a sequence number to every number to know which number came first.

In short, we will keep three things with every number that we push to the heap:

1. number // value of the number
2. frequency // frequency of the number when it was pushed to the heap
3. sequenceNumber // a sequence number, to know what number came first

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

The time complexity of push() and pop() is O(logN) where ‘N’ is the current number of elements in the heap.

Space Complexity

We will need O(N) space for the heap and the map, so the overall space complexity of the algorithm is O(N).

Alternate Solution: Using Hashmaps and Stacks

This solution uses two maps to simulate a frequency stack. The first map, frequencyMap, keeps track of how many times each number appears. When a number is pushed, its frequency is incremented in this map. The second map, frequencyStacks, stores stacks of numbers for each frequency. Each key is a frequency, and the corresponding value is a stack of numbers that have been pushed with that frequency. This organization makes it easy to retrieve the most frequent numbers.

For the pop operation, the algorithm retrieves the stack associated with the current highest frequency. Since each stack maintains insertion order, the most recently pushed number (handling ties) is returned. After popping, the frequency of that number is decremented in frequencyMap, and if the corresponding stack becomes empty, the highest frequency is updated. This design ensures efficient and constant average time complexity for both push and pop operations.

Step-by-Step Algorithm

  • Push Operation:

    • Increment the frequency of the number:
      • Retrieve the current frequency from frequencyMap (defaulting to 0) and add 1.
      • Update frequencyMap with the new frequency.
    • Update the highest frequency:
      • If the new frequency is greater than highestFrequency, update highestFrequency.
    • Add the number to the corresponding frequency stack:
      • Retrieve or create a new stack in frequencyStacks for the new frequency.
      • Push the number onto this stack.
    • This process tracks the frequency and insertion order for efficient retrieval during pop operations.

  • Pop Operation:

    • Retrieve the most frequent element:
      • Access the stack in frequencyStacks corresponding to highestFrequency.
      • Pop the top element from this stack.
      • This ensures that the most frequent, and in case of a tie the most recent, element is returned efficiently.
    • Update the frequency of the popped element:
      • Decrement its frequency in frequencyMap.
    • Adjust the highest frequency if needed:
      • If the current highest frequency stack is empty after popping, decrement highestFrequency.
    • Return the popped element.

Algorithm Walkthrough

Consider the following sequence of operations:

  1. Push(1):

    • Frequency of 1 becomes 1.
    • Update frequency map: {1: 1}.
    • Highest frequency becomes 1.
    • Push 1 into the stack for frequency 1 ? frequencyStacks: {1: [1]}.

  2. Push(2):

    • Frequency of 2 becomes 1.
    • Update frequency map: {1: 1, 2: 1}.
    • Highest frequency remains 1.
    • Push 2 into the stack for frequency 1 ? frequencyStacks: {1: [1, 2]}.

  3. Push(3):

    • Frequency of 3 becomes 1.
    • Update frequency map: {1: 1, 2: 1, 3: 1}.
    • Highest frequency remains 1.
    • Push 3 into the stack for frequency 1 ? frequencyStacks: {1: [1, 2, 3]}.

  4. Push(2):

    • Frequency of 2 increases to 2.
    • Update frequency map: {1: 1, 2: 2, 3: 1}.
    • Highest frequency updates to 2.
    • Push 2 into the stack for frequency 2 ? frequencyStacks: {1: [1, 2, 3], 2: [2]}.

  5. Push(1):

    • Frequency of 1 increases to 2.
    • Update frequency map: {1: 2, 2: 2, 3: 1}.
    • Highest frequency remains 2.
    • Push 1 into the stack for frequency 2 ? frequencyStacks: {1: [1, 2, 3], 2: [2, 1]}.

  6. Push(2):

    • Frequency of 2 increases to 3.
    • Update frequency map: {1: 2, 2: 3, 3: 1}.
    • Highest frequency updates to 3.
    • Push 2 into the stack for frequency 3 ? frequencyStacks: {1: [1, 2, 3], 2: [2, 1], 3: [2]}.

  7. Push(5):

    • Frequency of 5 becomes 1.
    • Update frequency map: {1: 2, 2: 3, 3: 1, 5: 1}.
    • Highest frequency remains 3.
    • Push 5 into the stack for frequency 1 ? frequencyStacks: {1: [1, 2, 3, 5], 2: [2, 1], 3: [2]}.

  8. Pop Operation (First pop):

    • The highest frequency is 3.
    • Access the stack for frequency 3 ? [2].
    • Pop the top element: 2.
    • Update frequency map for 2: frequency decreases from 3 to 2.
    • Check if the stack for frequency 3 is empty:
      • It is empty, so decrement highest frequency to 2.
    • Return: 2.

  9. Pop Operation (Second pop):

    • The highest frequency is now 2.
    • Access the stack for frequency 2 ? [2, 1].
    • Pop the top element: 1.
    • Update frequency map for 1: frequency decreases from 2 to 1.
    • Check if the stack for frequency 2 is empty:
      • It is not empty (remaining: [2]).
    • Return: 1.

  10. Pop Operation (Third pop):

    • The highest frequency remains 2.
    • Access the stack for frequency 2 ? [2].
    • Pop the top element: 2.
    • Update frequency map for 2: frequency decreases from 2 to 1.
    • Check if the stack for frequency 2 is empty:
      • It is empty, so decrement highest frequency to 1.
    • Return: 2.

The sequence of pop operations outputs 2, 1, and 2 respectively.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  1. push(int num)

    • Retrieving the frequency of num from frequencyMap → O(1)
    • Updating the frequency of num in frequencyMap → O(1)
    • Checking and updating highestFrequency → O(1)
    • Inserting num into frequencyStacks → O(1)
    • Overall Time Complexity: O(1)

  2. pop()

    • Accessing the stack with the highest frequency → O(1)
    • Removing the top element from the stack → O(1)
    • Updating frequencyMap for the removed element → O(1)
    • Checking if the stack is empty and updating highestFrequency → O(1)
    • Overall Time Complexity:O(1)

Thus, both push() and pop() operations run in constant time O(1).

  1. Worst Case Scenario Explanation
  • In the worst case, if the hash function results in many collisions, operations on the hash map (frequencyMap) could degrade from O(1) to O(n) due to linked list traversal or other collision resolution mechanisms.
  • Most programming languages implement hash maps using:
    • Separate chaining (linked list or balanced tree in buckets).
    • Open addressing (probing techniques).
  • When collisions occur frequently, retrieving or updating values in the hash map may require scanning multiple elements, leading to an O(n) complexity in the worst case.
  • However, in practical scenarios, well-implemented hash functions distribute keys evenly, keeping the average case O(1).

Space Complexity

  • frequencyMap: Stores the frequency of each unique element in the stack. In the worst case, all n elements are distinct, so the space complexity is O(n).
  • frequencyStacks: Contains multiple stacks where elements are grouped by frequency. The total number of elements across all stacks is at most n, so the space complexity is O(n).
  • highestFrequency: A single integer variable, O(1).

Thus, the overall space complexity is O(n), where n is the number of elements stored in the stack.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible