Algorithm


Problem Name: Data Structures - Poisonous Plants

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

In this HackerRank in Data Structures - Poisonous Plants solutions

There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies.

 

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.

 

Example

p = [3,6,2,7,5] // pesticide levels

Use a 1-indexed array. On day 1 , plants 2 and 4 die leaving p' = [3,2,5] . On day 2 plant 3 in p' dies leaving p'' = [3,2]. There is no plant with a higher concentration of pesticide than the one to its left, so plants stop dying after day 2.

Function Description
Complete the function poisonousPlants in the editor below.

 

poisonousPlants has the following parameter(s):

 

  • int p[n]: the pesticide levels in each plant

 

Returns
- int: the number of days until plants no longer die from pesticide

Input Format

The first line contains an integer n the size of the array p.

The next line contains n space-separated integers p[i].

Constraints

1 <= n <= 10**5

0 <= p[i] <= 10**9

ample Input

7
6 5 8 4 7 10 9

Sample Output

2

Explanation

Initially all plants are alive.

Plants = {(6,1), (5,2), (8,3), (4,4), (7,5), (10,6), (9,7)}

Plants[k] = (i,j) => jth plant has pesticide amount = i.

After the 1st day, 4 plants remain as plants 3, 5, and 6 die.

Plants = {(6,1), (5,2), (4,4), (9,7)}

After the 2nd day, 3 plants survive as plant 7 dies.

Plants = {(6,1), (5,2), (4,4)}

Plants stop dying after the 2nd day.

 

 

 

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 {
  int val;
  int day;
} node_t;

int main(void) {
  int len = 0;
  scanf("%d\n", &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 stack\n", 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 stack\n", 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 stack\n", stack[stack_top].val, stack[stack_top].day);
    stack_top--;
  }

  printf("%d\n", max_days);

  free(A);
  free(stack);
  return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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 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;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming

start coding.
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);
	}
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - 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 == '/\r\n'){
		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">;
}
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - 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()
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Super Maximum Cost Queries solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] No Prefix Set solution in Hackerrank - Hacerrank solution C, C++, java,js, Python