Came across an OA question on LC and Can't get to cracking it


  • In short what we need are: point update queries(plant or replant crop with capacity c on ith plot) and range queries(that count c smaller than w in range l to r and also updates those indices where c < w to inf marking the damaged crops).

My idea was to implement a Merge Sort Tree to solve this problem. But there is a slight issue, when we do a sprinkle event we can do a Binary Search in Segment Tree Node Array and all ruined crops could be easily counted. But we also need to remove them, this inturn will be time consuming as we need to iterate over the ruined ones linearly and also update out Segment Tree.

The problem is that with every type 2 query we must also update the crops being damaged, which I dont think we can do better than traversing O(N).

Disclaimer: I did not solve it.

My idea was to implement a Merge Sort Tree to solve this problem

yes, probably the best approach. Make sure it is sorted in reverse-order, that way whenever you have to remove small elements, you know they will be at the end of the vector, running in O(1)

we can do a Binary Search in Segment Tree Node Array

I sadly don’t know what you mean. Let me guess and correct me if I am wrong, though.
You have a vector in some Node like this [12, 11, 5, 4, 2, 1]. And you want to remove all crops that get destroyed by water intensity 5. This would be done with a while-loop. While the last element is <= 5, remove. Each removal runs in O(1), which is fast enough. O(log n) if you consider you need to remove the element in all children.

The problem is that with every type 2 query we must also update the crops being damaged, which I dont think we can do better than traversing O(N).

You can. When removing a single crop from a Node, you would try to remove a crop from both children. If a child has no crop to remove, then you skip it. if you have a child that needs a crop removed, then you remove it and continue removing a crop in its children, until done. Runs in O(log n)*

*if you have exactly 1 crop to remove, it is easy to see that this crop can be element in at most log n Nodes. If you have 10 crops to remove, at most 10 log n Nodes may need a crop removed. And so on.