Open In App

Find maximum in stack in O(1) without using additional stack in Python

Last Updated : 05 Jun, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

The task is to design a stack which can get the maximum value in the stack in O(1) time without using an additional stack in Python.

Examples:

Input: Consider the following SpecialStack

16  –> TOP
29
15
19
18
When getMax() is called it should return 29, 
which is the maximum element in the current stack. 

If we do pop two times on stack, the stack becomes

15  –> TOP
19
18

When getMax() is called, it should return 19 
which is the maximum in the current stack.

Approach: Instead of pushing a single element to the stack, push a pair instead. The pair consists of the (value, localMax) where localMax is the maximum value upto that element. 

  • When we insert a new element, if the new element is greater than the local maximum below it, we set the local maximum of a new element equal to the element itself.
  • Else, we set the local maximum of the new element equal to the local maximum of the element below it.
  • The local maximum of the top of the stack will be the overall maximum.
  • Now if we want to know the maximum at any given point, we ask the top of the stack for local maximum associated with it which can be done in O(1).

Below is the implementation in Python:

Python
# Python3 implementation of the approach
class Block:

    # A block has two elements
    # as components (i.e. value and localMax)
    def __init__(self, value, localMax):
        self.value = value
        self.localMax = localMax


class Stack:
    def __init__(self, size):

        # Setting size of stack and
        # initial value of top
        self.stack = [None] * size
        self.size = size
        self.top = -1

    # Function to push an element
    # to the stack
    def push(self, value):

        # Don't allow pushing elements
        # if stack is full
        if self.top == self.size - 1:
            print("Stack is full")
        else:
            self.top += 1

            # If the inserted element is the first element
            # then it is the maximum element, since no other
            # elements is in the stack, so the localMax
            # of the first element is the element itself
            if self.top == 0:
                self.stack[self.top] = Block(value, value)

            else:

                # If the newly pushed element is less
                # than the localMax of element below it,
                # Then the over all maximum doesn't change
                # and hence, the localMax of the newly inserted
                # element is same as element below it
                if self.stack[self.top - 1].localMax > value:
                    self.stack[self.top] = Block(
                        value, self.stack[self.top - 1].localMax)

                # Newly inserted element is greater than
                # the localMax below it, hence the localMax
                # of new element is the element itself
                else:
                    self.stack
                    self.stack[self.top] = Block(value, value)

            print(value, "inserted in the stack")

    # Function to remove an element
    # from the top of the stack
    def pop(self):

        # If stack is empty
        if self.top == -1:
            print("Stack is empty")

        # Remove the element if the stack
        # is not empty
        else:
            self.top -= 1
            print("Element popped")

    # Function to find the maximum
    # element from the stack
    def getMax(self):

        # If stack is empty
        if self.top == -1:
            print("Stack is empty")
        else:

            # The overall maximum is the local maximum
            # of the top element
            print("Maximum value in the stack:",
                  self.stack[self.top].localMax)

# Driver code


# Create stack of size 5
stack = Stack(5)
stack.push(2)
stack.getMax()
stack.push(6)
stack.getMax()
stack.pop()
stack.getMax()

Output
2 inserted in the stack
Maximum value in the stack: 2
6 inserted in the stack
Maximum value in the stack: 6
Element popped
Maximum value in the stack: 2

Time Complexity: O(1)
Auxiliary Space: O(N) 



Previous Article
Next Article

Similar Reads

Find maximum in stack in O(1) without using additional stack
The task is to design a stack which can get the maximum value in the stack in O(1) time without using an additional stack. Examples: Input: push(2) findMax() push(6) findMax() pop() findMax() Output: 2 inserted in stack Maximum value in the stack: 2 6 inserted in stack Maximum value in the stack: 6 Element popped Maximum value in the stack: 2 Appro
11 min read
Efficiently find first repeated character in a string without using any additional data structure in one traversal
Implement a space efficient algorithm to check First repeated character in a string without using any additional data structure in one traversal. Use additional data structures like count array, hash, etc is not allowed. Examples : Input : abcfdeacf Output : char = a, index= 6Recommended: Please solve it on “PRACTICE ” first, before moving on to th
5 min read
Efficiently check if a string has all unique characters without using any additional data structure
Implement an space efficient algorithm to determine if a string (of characters from 'a' to 'z') has all unique characters or not. Use additional data structures like count array, hash, etc is not allowed.Expected Time Complexity : O(n) Examples : Input : str = "aaabbccdaa" Output : No Input : str = "abcd" Output : Yes Brute Force Approach: The brut
9 min read
Minimum number of additional Trees to have exactly n-leaf nodes
Given a tree with only one node. We want a tree with exactly n-leaf nodes. We have exactly k trees consisting of 1, 2, ..., and k leaf nodes. For example, we had k additional trees. The only operation we can do now is to superimpose the root of one of the additional trees onto any leave of the original tree. Determine the minimum number of addition
7 min read
Median after K additional integers
Given an array of n integers. We are allowed to add k additional integer in the array and then find the median of the resultant array. We can choose any k values to be added. Constraints: k < n n + k is always odd. Examples : Input : arr[] = { 4, 7 } k = 1 Output : 7 Explanation : One of the possible solutions is to add 8 making the array [4, 7,
5 min read
Find maximum and minimum element in binary tree without using recursion or stack or queue
Given a binary tree. The task is to find out the maximum and minimum element in a binary tree without using recursion or stack or queue i.e, space complexity should be O(1). Examples: Input : 12 / \ 13 10 / \ 14 15 / \ / \ 21 24 22 23 Output : Max element : 24 Min element : 10 Input : 12 / \ 19 82 / / \ 41 15 95 \ / / \ 2 21 7 16 Output : Max eleme
10 min read
Inorder Tree Traversal without recursion and without stack!
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. 1. Initialize current as root 2. While current
9 min read
Postorder traversal of Binary Tree without recursion and without stack
Given a binary tree, perform postorder traversal. Prerequisite - Inorder/preorder/postorder traversal of tree We have discussed the below methods for postorder traversal. 1) Recursive Postorder Traversal. 2) Postorder traversal using Stack. 2) Postorder traversal using two Stacks. Approach 1 The approach used is based on using an unordered set to k
15 min read
Sliding Window Maximum (Maximum of all subarrays of size k) using stack in O(n) time
Given an array arr[] of N integers and another integer k ? N. The task is to find the maximum element of every sub-array of size k. Examples: Input: arr[] = {9, 7, 2, 4, 6, 8, 2, 1, 5} k = 3 Output: 9 7 6 8 8 8 5 Explanation: Window 1: {9, 7, 2}, max = 9 Window 2: {7, 2, 4}, max = 7 Window 3: {2, 4, 6}, max = 6 Window 4: {4, 6, 8}, max = 8 Window 5
8 min read
Find maximum in an array without using Relational Operators
Given an array A[] of non-negative integers, find the maximum in the array without using Relational Operator. Examples: Input : A[] = {2, 3, 1, 4, 5}Output : 5Input : A[] = {23, 17, 93}Output : 93We use repeated subtraction to find out the maximum. To find maximum between two numbers, we take a variable counter initialized to zero. We keep decreasi
9 min read
Article Tags :
Practice Tags :