HackerRank Poisonous Plants solution

In this HackerRank Poisonous Plants Interview preparation kit problem You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plant with more pesticide content than the plant to its left.

Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the poisonousPlants function below.
def poisonousPlants(p):
    stack = [(p[0], 0)]
    maxN = 0
    for i in range(1, len(p)):
        if (p[i] > p[i - 1]):
            stack.append((p[i], 1))
            maxN = max((maxN, 1))
        else:
            n = 0
            while (len(stack) > 0 and stack[-1][0] >= p[i]):
                n = max((n, stack[-1][1]))
                stack.pop()
            dayToDie = 0 if len(stack) == 0 else n + 1
            maxN = max((maxN, dayToDie))

            stack.append((p[i], dayToDie))
    return maxN

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    p = list(map(int, input().rstrip().split()))

    result = poisonousPlants(p)

    fptr.write(str(result) + 'n')

    fptr.close()

Problem solution in Java Programming.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Solution {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt();
		int[] P = new int[N + 2];
		int[] prev = new int[N + 2];
		int[] next = new int[N + 2];
		next[0] = 1;
		prev[N + 1] = N;
		for (int i = 1; i <= N; ++i) {
			P[i] = Integer.parseInt(sc.next());
			prev[i] = i - 1;
			next[i] = i + 1;
		}
		ArrayList<Integer> killer = new ArrayList<>();
		for (int i = 1; i < N; ++i) {
			if (P[i] < P[i + 1]) {
				killer.add(i);
			}
		}
		int day = 0;
		while (!killer.isEmpty()) {
			++day;
			ArrayList<Integer> nk = new ArrayList<>();
			for (int i = killer.size() - 1; i >= 0; --i) {
				int k = killer.get(i);
				int killed = next[k];
				prev[next[killed]] = k;
				next[k] = next[killed];
				if (!nk.isEmpty() && nk.get(nk.size() - 1) == killed) nk.remove(nk.size() - 1);
				if (next[k] <= N && P[k] < P[next[k]]) {
					nk.add(k);
				}
			}
			Collections.reverse(nk);
			killer = nk;
		}
		System.out.println(day);
	}
}

Problem solution in C++ programming.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
in dct=0;
map<in,in> mar;
set<in> td;
void proc(in id){
  auto it=mar.find(id);
  auto it2=it;
  ++it2;
  mar.erase(it);
  if(it2!=mar.end() && it2!=mar.begin()){
    it=it2;
    --it;
    if(it2->second>it->second)
      td.insert(it2->first);
    else{
      if(td.count(it2->first))
	td.erase(it2->first);
    }
  }
}
VI otd;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  in ta;
  forn(i,n){
    cin>>ta;
    mar[i]=ta;
    if(i>0 && mar[i]>mar[i-1])
      td.insert(i);
  }
  while(!td.empty()){
    dct++;
    otd.clear();
    fors(i,td)
      otd.PB(*i);
    td.clear();
    reverse(all(otd));
    forv(i,otd){
      proc(otd[i]);
    }
  }
  cout<<dct<<endl;
  return 0;
}

Problem solution in C programming.

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

typedef struct {
  int val;
  int day;
} node_t;

int main(void) {
  int len = 0;
  scanf("%dn", &len);

  int *A = (int*)calloc(len, sizeof(int));
  for (int i = 0; i < len; i++) {
    scanf("%d", &A[i]);
  }
  node_t *stack = (node_t*)calloc(len, sizeof(node_t));
  int stack_top = -1;
  
  int min_so_far = A[0];
  int max_days = 0;
  for (int i = 1; i < len; i++) {
    // pop things off the stack with greater or equal value and keep track of max day seen
    int my_days = 0;
    while (stack_top > -1 && stack[stack_top].val >= A[i]) {
      if (my_days < stack[stack_top].day) my_days = stack[stack_top].day;
      //printf("popping (%d,%d) from stackn", stack[stack_top].val, stack[stack_top].day);
      stack_top--;
    }   
    // if this value is a left to right min, it will never die
    if (A[i] <= min_so_far) {
      min_so_far = A[i];
    } else {
      stack_top++;
      stack[stack_top].val = A[i];
      stack[stack_top].day = my_days+1;
      //printf("adding (%d,%d) to stackn", A[i], my_days+1);
      if (max_days < my_days+1) max_days = my_days+1;
    }
  }
  
  // chcek for max of anything remaining in stack
  while (stack_top > -1) {
    if (max_days < stack[stack_top].day) max_days = stack[stack_top].day;
    //printf("popping (%d,%d) from stackn", stack[stack_top].val, stack[stack_top].day);
    stack_top--;
  }

  printf("%dn", max_days);

  free(A);
  free(stack);
  return 0;
}

Problem solution in JavaScript programming.

process.stdin.resume();
process.stdin.setEncoding("ascii");
var __input_stdin = "";
var __input_stdin_array = "";
var __input_currentline = 0;
var arr = [];
var stack = [];
var maxDays = 0;

process.stdin.on("data", function (input) {

	/* if(input == '/rn'){
		processData();
		process.exit();
	} */
	
    __input_stdin += input;
});

process.stdin.on("end", function () {
   processData(__input_stdin);
});


function processData() {
    //Enter your code here
	__input_stdin_array = __input_stdin.split("n");
	//__input_currentline++;
	
	arr = __input_stdin_array[1].split(' ').map(Number);
	
	for (var i in arr) {
		var days = 0;
		while (stack && stack[stack.length - 1] &&  (arr[i] <= stack[stack.length - 1].value)) {
			days = Math.max(days, (stack.pop()).days);
		}
		
		if (stack.length == 0) days = 0;
		else days++;
		
		maxDays = Math.max(maxDays, days);
		
		stack.push({value: (arr[i] * 1) , days : days});
	}
	process.stdout.write(""+maxDays+"n");
}