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.
pop the top element from every stack (excluding the unique leftmost stack). these are the plants that die on this day.
tuesday6>5, 7>4, 3>1>1, -
now check to see if any adjacent stacks can be merged. here we see that 7>4 and 3>1>1 can be merged to form a longer chain. stacks can be merged in O(1)
tuesday6>5, 7>4>3>1>1
one day has now passed. repeat the process.
wednesday6>5, 4>3>1>1
wednesday6>5>4>3>1>1
now that just one stack remains in our list, we know we are done.
NB these stacks are linked-list-based and maintain a pointer to their base element. This allows for O(1) merge operations, and O(1) checking of the top and bottom values.
Poisonous Plants
You are viewing a single comment's thread. Return to all comments →
it can be done with a list of stacks*
let's say we start with
6 5 8 7 4 7 3 1 1 10we'll represent it as a list of stacks like this:
monday
6>5, 8>7>4, 7>3>1>1, 10each stack is a maximal non-increasing chain
now, to let one day pass:
tuesday
6>5, 7>4, 3>1>1, -7>4and3>1>1can be merged to form a longer chain. stacks can be merged in O(1)tuesday
6>5, 7>4>3>1>1wednesday
6>5, 4>3>1>1wednesday
6>5>4>3>1>1NB these stacks are linked-list-based and maintain a pointer to their base element. This allows for O(1) merge operations, and O(1) checking of the top and bottom values.