Watch 10 video solutions for Maximum Total Area Occupied by Pistons, a hard level problem involving Array, Hash Table, String. This walkthrough by NeetCode has 427,768 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are several pistons in an old car engine, and we want to calculate the maximum possible area under the pistons.
You are given:
height, representing the maximum height a piston can reach.positions, where positions[i] is the current position of piston i, which is equal to the current area under it.directions, where directions[i] is the current moving direction of piston i, 'U' for up, and 'D' for down.Each second:
positions[i] is incremented by 1.positions[i] == 0 or positions[i] == height, its direction will change.Return the maximum possible area under all the pistons.
Example 1:
Input: height = 5, positions = [2,5], directions = "UD"
Output: 7
Explanation:
The current position of the pistons has the maximum possible area under it.
Example 2:
Input: height = 6, positions = [0,0,6,3], directions = "UUDU"
Output: 15
Explanation:
After 3 seconds, the pistons will be in positions [3, 3, 3, 6], which has the maximum possible area under it.
Constraints:
1 <= height <= 1061 <= positions.length == directions.length <= 1050 <= positions[i] <= heightdirections[i] is either 'U' or 'D'.Problem Overview: You are given a sequence describing piston movements over time. Each piston moves up or down based on characters in a string, and the goal is to compute the maximum total area occupied by the pistons across the timeline. The challenge is efficiently tracking height changes and aggregating the total occupied area without recomputing states for every step.
Approach 1: Direct Simulation (Brute Force) (Time: O(n^2), Space: O(1))
The most straightforward idea is to simulate piston heights step by step and recompute the total occupied area after each operation. For every time index, iterate through all previous states to determine the effective heights and sum the occupied space. This works because piston movement is deterministic, but it quickly becomes inefficient as the timeline grows. Nested iteration over the movement string leads to quadratic complexity, making it impractical for large inputs.
Approach 2: Prefix Sum Height Tracking (Time: O(n), Space: O(n))
A better strategy models each piston movement as a numerical change. Convert upward movement to +1 and downward movement to -1, then build a prefix sum array to represent piston height at every time step. The prefix sum lets you compute the height difference between any two positions in constant time. This converts the raw string simulation into a numeric sequence that can be processed efficiently.
Approach 3: Counting Heights with Hash Table (Optimal) (Time: O(n), Space: O(n))
Once heights are represented as prefix sums, the key insight is that the total area depends on how long certain height levels persist. Use a hash table to count occurrences of prefix heights and track spans where pistons maintain or exceed a particular level. Each step updates the running height, and previously seen heights reveal intervals that contribute to the total occupied area. Combining prefix sum accumulation with counting avoids repeated recomputation and keeps processing linear.
Recommended for interviews: Start by explaining the brute force simulation to show you understand how piston movement affects area over time. Then shift to the prefix sum representation, which converts movement into cumulative heights. The optimal hash-table counting method is what interviewers expect for large constraints because it reduces the problem to a single linear scan with constant-time updates.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n^2) | O(1) | Useful for understanding piston movement and verifying logic on small inputs |
| Prefix Sum Height Tracking | O(n) | O(n) | Transforms movement string into cumulative height values for efficient queries |
| Hash Table + Prefix Sum Counting | O(n) | O(n) | Optimal approach for large constraints with constant-time updates |