FunctionRacerProblemsRace

Clear the Row of Stones

HardStacks and queuesPython, JavaScript, TypeScript, Java, C++

Stones lie in a row, and weights lists their weights from left to right. One move picks two stones that lie next to each other, costs the product of their two weights, and takes the lighter of the two out of the row (either one if they weigh the same). The stones on both sides of the gap then become neighbors.

Keep moving until one stone is left. Return the least total cost.

Example 1

weights [3,1,5]
returns 18

Pair the 1 with the 3 for a cost of 3. Then 3 and 5 are neighbors and cost 15. Pairing the 1 with the 5 first would cost 5 + 15.

Example 2

weights [4]
returns 0

A single stone needs no move.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Stacks and queues problems