Algorithm


Problem Name: Data Structures - Maximum Element

Problem Link: https://www.hackerrank.com/challenges/maximum-element/problem?isFullScreen=true

In this HackerRank in Data Structures - Maximum Element solutions

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.

 

Function Description

 

Complete the getMax function in the editor below.

 

getMax has the following parameters:
- string operations[n]: operations as strings

 

Returns
- int[]: the answers to each type 3 query

Input Format

The first line of input contains an integer, n. The next n lines each contain an above mentioned query.

Constraints

1 <= n <= 10**5

1 <= x <= 10**9

1 <= type <= 3

All queries are valid.

Sample Input

STDIN   Function
-----   --------
10      operations[] size n = 10
1 97    operations = ['1 97', '2', '1 20', ....]
2
1 20
2
1 26
1 20
2
3
1 91
3

Sample Output

26
91

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct node *Node;
typedef struct stackRep *Stack;
   
typedef struct node {
   int data;
   int prevMax;
   Node next;
} node;

typedef struct stackRep {
   int maxElt;
   Node head;
} stack;


Stack newStack(void);
void destroyStack(Stack s);
Node newNode(Stack s, int i);
void push(Stack s, Node n);
Node pop(Stack s);


int main(int argc, char *argv[]) {

   int i;
   int lines;
   
   i = 0;
   fscanf(stdin, "%d", &lines);

   Stack s;
   s = newStack();
   
   while (i  <  lines) {
      int req;
      fscanf(stdin, "%d", &req);
      // printf("read: %d\n", req);
      
      if (req == 1) {
         // push

         int data;
         fscanf(stdin, "%d", &data);
         // printf("pushing %d..\n", data);

         Node n;
         n = newNode(s, data);
         push(s, n);
         
         if (data > s->maxElt) {
            s->maxElt = data;
         }
         
      } else if (req == 2) {
         // pop
         // printf("popping\n");
         Node n;
         n = pop(s);

         if (n->data == s->maxElt) {
            s->maxElt = n->prevMax;
         }

         free(n);
         
      } else {
         // return max
         printf("%d\n", s->maxElt);
      }
      
      i += 1;
   }
       

   destroyStack(s);
   
   return EXIT_SUCCESS;
}

void destroyStack(Stack s) {
   if (s != NULL) {
      Node curr;
      Node prev;
      
      curr = s->head;
      prev = s->head;
      
      while (curr->next != NULL) {
         prev = curr;
         curr = curr->next;
         free(prev);
      }

      free(curr);
   }
   
   free(s);
}

Stack newStack(void) {
   Stack s;
   s = malloc(sizeof(struct stackRep) * 1);
   s->maxElt = 0;
   s->head = NULL;
   return s;
}

Node newNode(Stack s, int i) {
   Node n;
   n = malloc(sizeof(struct node) * 1);
   n->data = i;
   n->prevMax = s->maxElt;
   n->next = NULL;
   return n;
}

void push(Stack s, Node n) {
   if (s->head == NULL) {
      s->head = n;
   } else {
      n->next = s->head;
      s->head = n;
   }
   // printf("push \t%p\n", n);
}

Node pop(Stack s) {

   Node curr;
   curr = NULL;
   
   if (s->head != NULL) {   
      curr = s->head;
      s->head = curr->next;
   }
   
   return curr;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <iostream>

using namespace std;

struct stack {
  struct s_node {
    int value;
    int max_value;
    s_node *prev;
  };

  s_node *top = nullptr;

  void push(int value) {
    top = new s_node { value, top ? max(top->max_value, value) : value, top };
  }

  void pop() {
    if (top)
      top = top->prev;
  }

  int max_value() {
    if (!top)
      throw exception();
    return top->max_value;
  }
};

int main() {
  /* Enter your code here. Read input from STDIN. Print output to STDOUT */
  stack s;
  int n; cin >> n;
  while (n--) {
    int o; cin >> o;
    switch (o) {
      case 1: {
        int v; cin >> v;
        s.push(v);
      }
      break;
      case 2:
      s.pop();
      break;
      case 3:
      cout << s.max_value() << '\n';
      break;
    }
  }
  return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;

public class Solution {
    private static void getMaxElementFromStack()
    {
        Stack < Integer> stack = new Stack();
        Stack onlyMaxs = new Stack();
        
        Scanner sc = new Scanner(System.in);
        
        int N = Integer.parseInt(sc.nextLine());
        int temp = 0;
        
        
        
        while(sc.hasNext())
        {
            String type[] = sc.nextLine().split(" ");
            switch(type[0])
            {
                case "1":
                temp = Integer.parseInt(type[1]);
                stack.push(temp);
                 if(onlyMaxs.isEmpty() || onlyMaxs.peek() <= temp)
                     onlyMaxs.push(temp);
                break;
                case "2":
                temp = stack.pop();
                if(temp == onlyMaxs.peek())
                    onlyMaxs.pop();
                break;
                case "3":
                System.out.println(onlyMaxs.peek()>;
            }
            N--;
        }
        
        while(N-- > 0)
            System.out.println(onlyMaxs.peek());
        
    }
    public static void main(String[] args) {
        getMaxElementFromStack();
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


function processData(input) {
    var inputs = input.split('\n');
    
    var stack = new MaxStack();
    for (var i = 1; i  <  inputs.length; i++) {
        var operation = inputs[i].charAt(0);
        if (operation === '1') {
            var data = inputs[i].split(' ');
            stack.push(parseInt(data[1], 10));
        } else if (operation === '2') {
            stack.pop();
        } else if (operation === '3') {
            console.log(stack.max());
        }
    }
} 

function MaxStack() {
    var self = this,
        data = [],
        maxes = [];
    
    this.push = function(item) {
        data.push(item);
        if (self.max() === null || self.max()  < = item) {
            maxes.push(item);
        }
    };
    
    this.pop = function() {
        if (data.length === 0) {
            return null;
        }
        
        var poppedItem = data.pop();
        if (poppedItem === self.max()) {
            maxes.pop();
        }
        return poppedItem;
    };
    
    this.max = function() {
        if (maxes.length === 0) {
            return null;
        }
        return maxes[maxes.length - 1];
    };
};

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


n = int(input())
stack = []
most = []

for i in range(n):
    data = input().split(' ')
    x = int(data[0])
    v = 0
    if len(data) > 1: v = int(data[1])
    if x == 1:
        stack.append(v)
        if not most or most[-1] <= v: most.append(v)
    elif x == 2:
        v = stack.pop()
        if most[-1] == v: most.pop()
    else:
        print(most[-1])
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] QHEAP1 solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Jesse and Cookies solution in Hackerrank - Hacerrank solution C, C++, java,js, Python