Header Ad

HackerRank Maximum Element problem solution

In this tutorial, we are going to solve or make a solution to the Maximum Element problem. so here we have given N queries. and then we need to perform queries on the stack. first, push the element into the stack and then delete the element present at the top of the stack and then print the maximum element in the stack.

HackerRank Maximum Element problem solution


Problem solution in 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])


Problem solution in Java Programming.

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

public class Solution {
    private static void getMaxElementFromStack()
    {
        Stack<Integer> stack = new Stack<Integer>();
        Stack<Integer> onlyMaxs = new Stack<Integer>();
        
        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();
    }
}


Problem solution in 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;
}


Problem solution in 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;
}


Problem solution in 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);
});


Post a Comment

0 Comments