Skip to main content

Maximum Frequency Stack

Question​

Given a sequence of operations consisting of push and pop, write a function to find the maximum frequency element in the stack.

Example 1
Input:
[5, 7, 5, 7, 4, 5]

Output:
[5, 7, 4]

Solution​

all//Maximum Frequency Stack.py


# define a function for maximum frequency stack
def max_freq_stack(arr):

    # create an empty dictionary
    dict = {}

    # create an empty stack
    stack = []

    # loop over the array
    for i in arr:

        # if element is not present in the dictionary
        if i not in dict.keys():

            # add element to the dictionary
            dict[i] = 1

        # if element is present in the dictionary
        else:

            # increment its frequency
            dict[i] += 1

        # push the element to the stack
        stack.append(i)

    # find the maximum frequency
    maxfreq = 0
    element = 0
    for i in dict.keys():

        # compare current frequency
        # with the maximum frequency
        if dict[i] > maxfreq:
            maxfreq = dict[i]
            element = i

    # create a temporary stack
    temp_stack = []

    # loop over the stack
    while (len(stack) > 0):

        # pop the top element
        top = stack.pop()

        # check if the popped element is
        # equal to the max frequency element
        if top == element:

            # push the element to the temporary stack
            temp_stack.append(top)

            # decrement the max frequency
            maxfreq -= 1

            # if the frequencies become zero
            if maxfreq == 0:

                # break the loop
                break

        else:

            # push the element back to the stack
            stack.append(top)

    # push the elements of the temporary stack
    # to the original stack
    while (len(temp_stack) > 0):
        top = temp_stack.pop()
        stack.append(top)

    return stack