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, 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.

Examples

Example 1:

1
2
3
4

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:

1
2
3
4
5

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 <= 10^6
  • 1 <= positions.length == directions.length <= 10^5
  • 0 <= positions[i] <= height
  • directions[i] is either 'U' or 'D'.

Solution

Method 1 – Simulation with Directional Updates

Intuition

To maximize the total area under the pistons, each piston should be moved in its current direction as far as possible until it hits the boundary (either 0 or height). The final area for each piston is its maximum possible position in its direction.

Approach

  1. For each piston, if its direction is ‘U’, move it up to height.
  2. If its direction is ‘D’, move it down to 0.
  3. The area under each piston is its final position.
  4. Sum all final positions to get the total area.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int maxTotalArea(int height, vector<int>& positions, string directions) {
        int n = positions.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            if (directions[i] == 'U') ans += height;
            else ans += 0;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func maxTotalArea(height int, positions []int, directions string) int {
    ans := 0
    for i := range positions {
        if directions[i] == 'U' {
            ans += height
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int maxTotalArea(int height, int[] positions, String directions) {
        int ans = 0;
        for (int i = 0; i < positions.length; ++i) {
            if (directions.charAt(i) == 'U') ans += height;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun maxTotalArea(height: Int, positions: IntArray, directions: String): Int {
        var ans = 0
        for (i in positions.indices) {
            if (directions[i] == 'U') ans += height
        }
        return ans
    }
}
1
2
3

class Solution:
    def maxTotalArea(self, height: int, positions: list[int], directions: str) -> int:
        return sum(height if d == 'U' else 0 for d in directions)
1
2
3
4
5

impl Solution {
    pub fn max_total_area(height: i32, positions: Vec<i32>, directions: String) -> i32 {
        directions.chars().map(|d| if d == 'U' { height } else { 0 }).sum()
    }
}
1
2
3
4
5
6
7
8

class Solution {
    maxTotalArea(height: number, positions: number[], directions: string): number {
        let ans = 0;
        for (let i = 0; i < positions.length; ++i)
            if (directions[i] === 'U') ans += height;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of pistons. Each piston is processed once.
  • 🧺 Space complexity: O(1), only a few variables are used.