Pump Rods at Their Peak

Hard

Several rods move up and down inside a pump. Each rod can be anywhere from height 0 to height top. You are given an array levels, where levels[i] is the current height of rod i, and a string moves, where moves[i] is its direction: 'U' for up, 'D' for down. Every second each rod moves by 1 in its direction. As soon as a rod is at height 0 or top, its direction flips (a rod sitting at an end and facing outward goes back on the next second). Return the largest total height of all rods that is ever reached, the current moment included.

Example 1

top=4, levels=[1, 3], moves="UD" → 4

The total is 1 + 3 = 4 now and never changes: one rod rises while the other sinks, and they bounce off the ends at the same moments. The answer is 4.

Example 2

top=5, levels=[0, 2, 5], moves="UUD" → 10

After 3 seconds the rods stand at 3, 5 and 2, a total of 10, and no moment does better.

Example 3

top=3, levels=[3, 0, 0], moves="DDD" → 6

Constraints

1 ≤ top ≤ 10⁶
1 ≤ len(levels) = len(moves) ≤ 10⁵
0 ≤ levels[i] ≤ top
moves[i] is 'U' or 'D'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String Counting Prefix Sum Simulation

Similar problems

Matching Ends per Range Medium Balanced Cuts After One Replacement Hard Pair GCDs by Sorted Position Hard Most Searched Words Medium Domain Visit Rollup Medium

Input

top=4, levels=[1, 3], moves="UD"

Expected

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.