HackerRank: Poisonous Plants ( Stacks, DS )

HackerRank: Poisonous Plants ( Stack, DS )
(Find me on HackerRank @ Handle: BishalG )

Problem Summary:
In this problem, we are given some value , say pesticide levels of each plants. A plant will dies if all plants to its left side have smaller such value than that of its own. We have to calculate the number of days after which no plants will die!!

Solution Idea:
For every position find out: "How many times it will be hitted from right side", say hits(i) maximum among all hits(i) is the desired answer!!
To find this, keep track of values in stack and try to eliminate all values in current stack which are greater than p(i) from each points !!
At certain point, if we find element which is to be counted as kth hit counter but that element itself require more than k hits to be stable then, we count that element as hit source of maximum value.
In this way, we will not repetitive actions and one element is added and popped from stack at most one time which leads to the O(n) time complexity, where n is total number of plant. We are using stack and hits which holds n elements total. So, space complexity is also O(n).

Source code:
int poisonousPlants(vector<int> p) {
stack<int>stk;
int n = p.size();
p.push_back(INT_MIN);
vector<int>hits(n, 0);
stk.push(n);
int ans = 0;
for (int i = n - 1; i >= 0; --i) {
int cnt = 0;
while (!stk.empty() && p[ stk.top()] > p[i]) {
cnt = max(cnt + 1, hits[ stk.top() ]);
stk.pop();
}
ans = max(ans, cnt);
hits[i] = cnt;
stk.push(i);
}
return ans;
}

Comments

Popular posts from this blog

HackerEarth: City and Campers 2 (DSU-UnionFind)

Problem : Codeforces Round #406 (Div. 1) B [ Legacy ]( Dijakstra, Segment tree)

Two Pointers Technique & Binary Search For Beginners