Skip to main content
Talentd

Maximum Total Area Occupied by Pistons - Solution & Explanation

HardPremiumFree on FleetCodeArrayHash TableStringSimulation5 min read
Practice this problem

Problem Statement

There are several pistons in an old car engine, and we want to calculate the maximum possible area under the pistons.

You are given:

  • An integer height, representing the maximum height a piston can reach.
  • An integer array positions, where positions[i] is the current position of piston i, which is equal to the current area under it.
  • A string directions, where directions[i] is the current moving direction of piston i, 'U' for up, and 'D' for down.

Each second:

  • Every piston moves in its current direction 1 unit. e.g., if the direction is up, positions[i] is incremented by 1.
  • If a piston has reached one of the ends, i.e., 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 <= 106
  • 1 <= positions.length == directions.length <= 105
  • 0 <= positions[i] <= height
  • directions[i] is either 'U' or 'D'.

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct SimulationO(n^2)O(1)Useful for understanding piston movement and verifying logic on small inputs
Prefix Sum Height TrackingO(n)O(n)Transforms movement string into cumulative height values for efficient queries
Hash Table + Prefix Sum CountingO(n)O(n)Optimal approach for large constraints with constant-time updates

Video Solution

How to EASILY solve LeetCode problems • NeetCode • 427,768 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Total Area Occupied by Pistons easy or hard?
Maximum Total Area Occupied by Pistons is classified as a Hard problem. The difficulty comes from recognizing that direct simulation is too slow and that prefix sums combined with counting techniques can compress the computation into a linear-time scan.
Maximum Total Area Occupied by Pistons Python/Java solution
Most implementations simulate piston movement by converting characters to numeric increments and maintaining a running prefix height. Python solutions typically use dictionaries for counting heights, while Java implementations use HashMap. Both versions achieve O(n) time complexity and O(n) space complexity.
How to solve Maximum Total Area Occupied by Pistons in O(n)?
Convert piston movements into numeric changes and compute a prefix sum representing the piston height at every step. While iterating through the string, maintain a hash map that tracks occurrences of each height level. This allows you to quickly determine spans that contribute to the maximum total occupied area, completing the computation in a single pass.
What is the best approach for Maximum Total Area Occupied by Pistons?
The most efficient approach combines prefix sum height tracking with a hash table for counting height occurrences. Each piston movement is converted into a +1 or -1 change, and prefix sums track the cumulative height at each step. A hash map stores previously seen height levels, allowing the algorithm to compute the maximum total area in O(n) time with O(n) space.
Is Maximum Total Area Occupied by Pistons asked at Google/Amazon/Meta?
Problems involving prefix sums, simulation, and hash-table counting are common in interviews at companies like Google, Amazon, and Meta. Variants of movement simulation and cumulative height tracking frequently appear in hard-level algorithm rounds, especially when combined with prefix-sum optimization.
What data structure is used in Maximum Total Area Occupied by Pistons?
The main data structures are arrays for prefix sums and a hash table for counting or tracking previously seen height states. These structures enable constant-time updates and quick lookups while iterating through the movement sequence.
What is the time complexity of Maximum Total Area Occupied by Pistons?
The optimal solution runs in O(n) time where n is the length of the movement string. Each character is processed once to update the prefix height and perform constant-time hash map operations. Space complexity is O(n) due to storing prefix sums or frequency counts of height states.

Ready to solve this problem?

Practice Maximum Total Area Occupied by Pistons with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays