Maximum Total Area Occupied by Pistons solution and explanation
The problem
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, wherepositions[i]is the current position of pistoni, which is equal to the current area under it. - A string
directions, wheredirections[i]is the current moving direction of pistoni,'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] == 0orpositions[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'.
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
class Solution:
def maxArea(self, height: int, positions: List[int], directions: str) -> int:
delta = defaultdict(int)
diff = res = 0
for pos, dir in zip(positions, directions):
res += pos
if dir == "U":
diff += 1
delta[height - pos] -= 2
delta[height * 2 - pos] += 2
else:
diff -= 1
delta[pos] += 2
delta[height + pos] -= 2
ans = res
pre = 0
for cur, d in sorted(delta.items()):
res += (cur - pre) * diff
pre = cur
diff += d
ans = max(ans, res)
return ansclass Solution {
public long maxArea(int height, int[] positions, String directions) {
Map<Integer, Integer> delta = new TreeMap<>();
int diff = 0;
long res = 0;
for (int i = 0; i < positions.length; ++i) {
int pos = positions[i];
char dir = directions.charAt(i);
res += pos;
if (dir == 'U') {
++diff;
delta.merge(height - pos, -2, Integer::sum);
delta.merge(height * 2 - pos, 2, Integer::sum);
} else {
--diff;
delta.merge(pos, 2, Integer::sum);
delta.merge(height + pos, -2, Integer::sum);
}
}
long ans = res;
int pre = 0;
for (var e : delta.entrySet()) {
int cur = e.getKey();
int d = e.getValue();
res += (long) (cur - pre) * diff;
pre = cur;
diff += d;
ans = Math.max(ans, res);
}
return ans;
}
}class Solution {
public:
long long maxArea(int height, vector<int>& positions, string directions) {
map<int, int> delta;
int diff = 0;
long long res = 0;
for (int i = 0; i < positions.size(); ++i) {
int pos = positions[i];
char dir = directions[i];
res += pos;
if (dir == 'U') {
++diff;
delta[height - pos] -= 2;
delta[height * 2 - pos] += 2;
} else {
--diff;
delta[pos] += 2;
delta[height + pos] -= 2;
}
}
long long ans = res;
int pre = 0;
for (const auto& [cur, d] : delta) {
res += static_cast<long long>(cur - pre) * diff;
pre = cur;
diff += d;
ans = max(ans, res);
}
return ans;
}
};func maxArea(height int, positions []int, directions string) int64 {
delta := make(map[int]int)
diff := 0
var res int64 = 0
for i, pos := range positions {
dir := directions[i]
res += int64(pos)
if dir == 'U' {
diff++
delta[height-pos] -= 2
delta[height*2-pos] += 2
} else {
diff--
delta[pos] += 2
delta[height+pos] -= 2
}
}
ans := res
pre := 0
keys := make([]int, 0, len(delta))
for key := range delta {
keys = append(keys, key)
}
sort.Ints(keys)
for _, cur := range keys {
d := delta[cur]
res += int64(cur-pre) * int64(diff)
pre = cur
diff += d
ans = max(ans, res)
}
return ans
}Complexity analysis
| 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 |
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.