Problem Description

You have a system of pistons that move up and down within a fixed height range. Each piston contributes an area equal to its current position (height from bottom), and you need to find the maximum total area that can be achieved as the pistons move over time.

Given:

• height: The maximum height any piston can reach (pistons move between 0 and height)
• positions: An array where positions[i] is the current position of piston i (also the area under that piston)
• directions: A string where directions[i] is either 'U' (moving up) or 'D' (moving down) for piston i

Movement Rules:

• Each second, every piston moves 1 unit in its current direction
• When a piston reaches either boundary (position 0 or position height), it reverses direction

Goal: Find the maximum possible total area under all pistons at any point in time.

For example, if you have 3 pistons at positions [2, 5, 3] with a height limit of 10, the current total area would be 2 + 5 + 3 = 10. As the pistons move according to their directions, this total will change, and you need to find the maximum value it can reach.

The solution uses an event-based approach to track when pistons change direction. It calculates the rate of change of the total area and identifies critical time points where pistons bounce off boundaries. By processing these events in chronological order, it efficiently computes the maximum area without simulating every single time step.

The key insight is that between direction changes, the total area changes linearly. Pistons moving up contribute +1 to the rate of change per second, while pistons moving down contribute -1. When a piston hits a boundary and reverses, it changes the rate by ±2 (from +1 to -1 or vice versa).

Intuition

The key observation is that we don't need to simulate the movement second by second. Instead, we can think about this problem in terms of events and rates of change.

At any moment, the total area is changing at a constant rate. Each piston moving up adds +1 per second to the total area, and each piston moving down subtracts 1 per second. So if we have 3 pistons going up and 2 going down, the total area increases by 3 - 2 = 1 per second.

The rate only changes when a piston hits a boundary (at position 0 or height) and reverses direction. When a piston switches from going up to going down, the rate decreases by 2 (it was contributing +1, now it contributes -1). Similarly, when switching from down to up, the rate increases by 2.

We can calculate when each piston will hit its next boundary:

• A piston at position pos moving up will hit the top after height - pos seconds
• A piston at position pos moving down will hit the bottom after pos seconds

But pistons don't stop after hitting one boundary - they bounce back and forth. So we need to track all future boundary hits:

• A piston starting at pos going up hits boundaries at times: height - pos, height * 2 - pos, height * 3 - pos, ...
• A piston starting at pos going down hits boundaries at times: pos, height + pos, height * 2 + pos, ...

Since we only care about the maximum area, we can limit our search to a reasonable time window. The pattern repeats every 2 * height seconds (time for a complete up-down cycle), so we only need to check the first few bounces.

By collecting all these boundary-hit events, sorting them by time, and processing them in order, we can track how the total area changes over time. At each event, we:

1. Calculate the area at that moment using the current rate
2. Update the rate based on which piston(s) are reversing
3. Keep track of the maximum area seen

This approach runs in O(n log n) time due to sorting, where n is the number of events, which is much more efficient than simulating every second.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation uses an event-based simulation with a dictionary to track when rate changes occur.

Data Structures:

• delta: A dictionary that maps time points to rate changes. When a piston bounces at time t, we store how the rate of change will be modified at that time.
• diff: The current rate of change (how much the total area changes per second)
• res: The current total area at any given time point
• ans: The maximum area encountered

Initial Setup:

1. Calculate the initial total area by summing all positions: res = sum(positions)
2. Calculate the initial rate of change diff:
   • For each piston going up ('U'): add 1 to diff
   • For each piston going down ('D'): subtract 1 from diff

Recording Future Events: For each piston, we record when it will hit boundaries and reverse direction:

• For pistons moving UP (from position pos):

  • First boundary hit at time height - pos (reaching the top)
  • When it bounces, it changes from +1 to -1 contribution, so rate changes by -2
  • Next boundary hit at time height * 2 - pos (reaching bottom after bouncing)
  • When it bounces again, it changes from -1 to +1, so rate changes by +2

• For pistons moving DOWN (from position pos):

  • First boundary hit at time pos (reaching the bottom)
  • When it bounces, it changes from -1 to +1 contribution, so rate changes by +2
  • Next boundary hit at time height + pos (reaching top after bouncing)
  • When it bounces again, it changes from +1 to -1, so rate changes by -2

Processing Events:

1. Sort all events by time using sorted(delta.items())
2. For each event at time cur:
   • Calculate the area at this time: res += (cur - pre) * diff
     • This adds the area accumulated since the last event
   • Update the maximum: ans = max(ans, res)
   • Apply the rate change for this event: diff += d
   • Update pre = cur for the next iteration

Example Walkthrough: If we have a piston at position 3 moving up with height = 10:

• Initial contribution to area: 3
• Initial contribution to rate: +1
• At time 7 (= 10 - 3), it hits the top and reverses
• Rate change at time 7: -2 (from +1 to -1)
• At time 17 (= 10 * 2 - 3), it hits the bottom again
• Rate change at time 17: +2 (from -1 to +1)

The algorithm efficiently finds the maximum by only checking these critical time points where the rate changes, avoiding the need to simulate every single second.

Example Walkthrough

Let's walk through a small example with height = 6, positions = [1, 5], and `directions = "UD".

Initial State:

• Piston 0: at position 1, moving UP ('U')
• Piston 1: at position 5, moving DOWN ('D')
• Initial total area: 1 + 5 = 6
• Initial rate of change: +1 (for UP) - 1 (for DOWN) = 0

Recording Events:

For Piston 0 (position 1, moving UP):

• Hits top at time 5 (= 6 - 1)
  • Rate change: -2 (switches from +1 to -1)
• Hits bottom at time 11 (= 6 × 2 - 1)
  • Rate change: +2 (switches from -1 to +1)

For Piston 1 (position 5, moving DOWN):

• Hits bottom at time 5 (= 5)
  • Rate change: +2 (switches from -1 to +1)
• Hits top at time 11 (= 6 + 5)
  • Rate change: -2 (switches from +1 to -1)

Event Timeline:

Time 0: area = 6, rate = 0
Time 5: Two events occur
  - Both pistons reverse
  - Total rate change: -2 + 2 = 0
  - Area at time 5: 6 + (5 - 0) × 0 = 6
  - New rate: 0 + 0 = 0
Time 11: Two events occur
  - Both pistons reverse again
  - Total rate change: +2 - 2 = 0
  - Area at time 11: 6 + (11 - 5) × 0 = 6
  - New rate: 0 + 0 = 0

In this example, the rate stays at 0 throughout, so the area remains constant at 6. The maximum area is 6.

A More Interesting Example:

Let's try height = 5, positions = [2, 4, 1], and `directions = "UUD".

Initial State:

• Total area: 2 + 4 + 1 = 7
• Rate: +1 + 1 - 1 = +1 (two UP, one DOWN)

Recording Events:

Piston 0 (position 2, UP):

• Hits top at time 3 (= 5 - 2), rate change: -2

Piston 1 (position 4, UP):

• Hits top at time 1 (= 5 - 4), rate change: -2

Piston 2 (position 1, DOWN):

• Hits bottom at time 1 (= 1), rate change: +2

Processing Events in Order:

Time 0: area = 7, rate = +1
Time 1: Two events (Piston 1 hits top, Piston 2 hits bottom)
  - Area at time 1: 7 + (1 - 0) × 1 = 8
  - Rate change: -2 + 2 = 0
  - New rate: 1 + 0 = 1
Time 3: One event (Piston 0 hits top)
  - Area at time 3: 8 + (3 - 1) × 1 = 10
  - Rate change: -2
  - New rate: 1 - 2 = -1

After time 3, the area starts decreasing (rate = -1). The maximum area achieved is 10 at time 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the number of positions/directions.

• Creating the delta dictionary and calculating initial values takes O(n) time as we iterate through all positions once
• The sorted(delta.items()) operation dominates the time complexity, requiring O(m log m) where m is the number of unique keys in delta
• Since each position can contribute at most 2 entries to delta (one addition and one subtraction), we have m ≤ 2n, making this O(n log n)
• The final iteration through sorted delta items takes O(m) = O(n) time
• Overall: O(n) + O(n log n) + O(n) = O(n log n)

Space Complexity: O(n)

• The delta dictionary stores at most 2n key-value pairs (2 entries per position), requiring O(n) space
• The sorted operation creates a list of delta items which also takes O(n) space
• Other variables (diff, res, ans, pre) use O(1) space
• Overall: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Time Calculations

When calculating bounce times like height * 2 - position, these values can become very large if height is large. In languages with fixed integer sizes, this could cause overflow issues.

Solution: In Python, integers have arbitrary precision so this isn't an issue, but in other languages, use long/64-bit integers or check for potential overflow conditions.

2. Missing Edge Cases for Initial Positions

A common mistake is not handling pistons that start at the boundaries (position 0 or position height). The code assumes all pistons are strictly between boundaries initially.

Solution: Add validation to handle boundary cases:

for position, direction in zip(positions, directions):
    if position == 0 and direction == "D":
        # Piston at bottom trying to go down - should immediately reverse
        direction = "U"
    elif position == height and direction == "U":
        # Piston at top trying to go up - should immediately reverse
        direction = "D"

3. Incorrect Handling of Simultaneous Events

Multiple pistons might hit boundaries at the exact same time. Using a simple dictionary correctly aggregates these changes, but developers might mistakenly overwrite values instead of accumulating them.

Wrong approach:

slope_changes[time] = -2  # This overwrites any existing value

Correct approach (as shown in solution):

slope_changes[time] -= 2  # This accumulates with existing changes

4. Not Checking Maximum at Time Zero

The code checks maximum area after processing each event, but if all pistons are moving down initially, the maximum might be at time 0 before any movement occurs.

Solution: Initialize max_area with the initial total distance (which the code already does correctly).

5. Forgetting to Update Previous Time

A subtle bug occurs if you forget to update previous_time after processing each event, causing incorrect area calculations.

Solution: Always update previous_time = current_time after processing each event (as shown in the solution).

6. Misunderstanding the Physical Model

Developers might incorrectly think that pistons stop at boundaries or that the area contribution becomes 0 at position 0. The problem states pistons bounce and continue moving, and even at position 0, the area contribution is 0 (not negative).

Solution: Carefully read the problem statement and understand that pistons continuously bounce between 0 and height, never stopping.