We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Stacks
  4. Poisonous Plants
  5. Discussions

Poisonous Plants

Sort by

recency

|

291 Discussions

|

  • dehaka
     + 0 comments

    wow hard question. couldnt figure out how to do it until i learned the previous greater element algo from copilot, very straightforward modification of that algo, ask copilot for it

    O(n)

    int poisonousPlants(const vector<int>& plant) {
    int days = 0;
    vector<int> life(plant.size(), 1);
    life[0] = INT_MAX;
    stack<int> S;
    S.push(0);
    for (int i=1; i < plant.size(); i++) {
        while (life[i] > life[S.top()] or (plant[i] <= plant[S.top()] and life[S.top()] != INT_MAX)) {
            life[i] = max(life[i], life[S.top()] + 1);
            S.pop();
        }
        if (plant[i] <= plant[S.top()] and life[S.top()] == INT_MAX) life[i] = INT_MAX;
        if (life[i] != INT_MAX) days = max(days, life[i]);
        S.push(i);
    }
    return days;
}

  • dellvecchio
     + 0 comments

    My Solution in Python using Dynamic Programing

    def poisonousPlants(p):
    vet = [float('inf')]*len(p)
    ind = [-1]*len(p)
    aux = 0
    dias = 0
    for i in range(1, len(p)):
        j = i - 1
        Achou = False
        aux = 0
        while not Achou:
            if p[j] >= p[i]:
                if vet[j] == float('inf'):
                    Achou = True
                else:
                    aux = vet[j]
                    j = ind[j]
            else:
                if vet[j] > aux:
                    vet[i] = aux + 1
                    dias = max(dias, vet[i])
                    ind[i] = j
                    Achou = True
                else:
                    j = ind[j]
    return dias

  • danielali1999
     + 0 comments

    Passing all test cases but exceeding time limit (~5 sec runtime) in a few. Could someone suggest an alternative approach or improvements to my current solution (C#)?

        public static int poisonousPlants(List<int> p)
    {
        int days = 0;
        List<int> plants = p.ToList();
        bool finalDay = false;
        do
        {
            int pCount = p.Count;
            for (int i = 1; i < pCount; i++)
            {
                if (p[i - 1] < p[i]) plants.RemoveAt(i - (pCount - plants.Count));
                if (i == pCount - 1)
                {
                    if (p.SequenceEqual(plants)) finalDay = true;
                    else days++; p = plants.ToList();
                }
            }
        } while (!finalDay && p.Count > 1);
        return days;
    }

  • ms_clovis
     + 0 comments

    My golang solution.... It doesn't pass all the test cases. Can anyone spot the logic error?

    Thanks in advance

    func poisonousPlants(p []int32) int32 {
	// Write your code here
	var days int32
	isDead := make([]bool, len(p))
	var aPlantDied bool

	aPlantDied = true

	for aPlantDied {
		aPlantDied = false
		for idx := len(p) - 1; idx > 0; idx-- {
			if p[idx-1] < p[idx] && !isDead[idx-1]  {
				isDead[idx-1] = true
				aPlantDied = true
			} else {
				continue
			}
		}
		days++
	}

	return days

}
	return days

}

  • AlzuabiIbrahim
     + 0 comments

    Kotlin

    data class Node(var prev: Node?, val value: Int, var next: Node?)

fun poisonousPlants(p: Array<Int>): Int {
    // Write your code here


    var toBeDeleted = mutableListOf<Node>()
    var previousNode: Node? = null
    for (value in p.reversed()) {
        val currentNode = Node(previousNode, value, null)
        previousNode?.next = currentNode
        previousNode = currentNode
        currentNode.prev?.let {prev->
            if (prev.value > currentNode.value) toBeDeleted.add(prev)
        }
    }

    var days = 0

    while (toBeDeleted.isNotEmpty()) {
        val toBeDeletedTemp = mutableListOf<Node>()
        toBeDeleted.forEach { nodeToBeDeleted ->
            nodeToBeDeleted.prev?.next = nodeToBeDeleted.next
            nodeToBeDeleted.next?.prev = nodeToBeDeleted.prev
            if (nodeToBeDeleted.next != null && nodeToBeDeleted.prev != null && nodeToBeDeleted.next?.value!! < nodeToBeDeleted.prev!!.value)
                toBeDeletedTemp.add(nodeToBeDeleted.prev!!)      
        }
        toBeDeleted = toBeDeletedTemp
        days++
    }
    return days
}