3279. Maximum Total Area Occupied by Pistons 🔒

HardArrayHash TableStringCountingPrefix SumSimulation

Problem Description

In this problem, we are dealing with an engine comprised of multiple pistons, and our goal is to determine the maximum possible area beneath these pistons. The pistons are capable of moving up and down within a defined range.

You are given:

An integer height, indicating the maximum height a piston can reach.
An integer array positions, where each element positions[i] represents the current position of piston i, which is equal to the current area beneath it.
A string directions, where each character directions[i] indicates the current moving direction of piston i, either 'U' for up or 'D' for down.

Each second, every piston moves by 1 unit in its given direction. If a piston reaches one of the boundaries (either position 0 or height), its moving direction will switch.

The task is to return the maximum possible area that can be achieved beneath all pistons.

Intuition

The key to solving this problem is to track the movement of the pistons and determine how their changing positions impact the total area beneath them. Initially, we calculate the sum of the current positions of the pistons to determine the starting area.

For each piston, depending on its direction, we adjust an incremental value (diff) that reflects how the movement of pistons will alter the total area. When pistons shift directions upon reaching the boundaries, we use a dictionary to track events that occur at specific time intervals (delta). This involves adjusting the effect on diff at specific positions in time, effectively simulating the pistons' movement over time.

The solution iterates through these changes and updates the running total area (res). We keep track of the maximum area observed (ans) as the pistons continue moving up and down.

This approach efficiently calculates the maximum potential area by leveraging the predictive modeling of each piston's movement pattern over time.

Learn more about Prefix Sum patterns.

Solution Approach

To solve the problem of calculating the maximum possible area under the pistons, we utilize a combination of calculations and simulations.

Here's a breakdown of the approach:

Initialize Variables:
- Use a defaultdict named delta to keep track of changes in direction at certain time intervals.
- Initialize diff to track the net change in area over time.
- Calculate the initial res, which is the total area under the pistons at the starting configuration by summing up all positions.
Loop through Pistons:
- For each piston, based on its direction (U for up or D for down), update the diff and prepare the delta mapping:
  - If the direction is U, increase diff, prepare an event to decrease it when reaching the top boundary (height), and to revert at double-height.
  - If the direction is D, decrease diff, prepare an event to increase it when reaching zero, and to revert at the reach of height.
Simulate Movements:
- Iterate over the sorted delta dictionary to simulate the changes:
  - Update res (the current area under the pistons) by adding (cur - pre) * diff, where cur is the current event's position, and pre is the previous event's position.
  - Adjust diff based on the current event.
  - Determine if the current res is greater than the recorded ans (maximum area so far), and update ans accordingly.
Return Result:
- After processing all the events, return ans, which contains the maximum possible area achieved.

This approach effectively leverages the predictive modeling of piston movement to efficiently calculate the maximum possible area beneath them.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach for the given problem.

Consider the following inputs:

height = 5
positions = [2, 3]
directions = "UD"

The pistons start at positions [2, 3], with the first piston moving up ('U') and the second piston moving down ('D').

Step-by-Step Simulation:

Initial Setup:
- The initial area (res) is the sum of the starting positions: 2 + 3 = 5.
- We initialize diff as 0 and a defaultdict delta to manage direction changes.
Loop Through Pistons:
- Piston 0 (Moving Up):
  - Current position: 2, starts moving up.
  - Increment diff by 1 because moving up increases area.
  - In delta, set an event to decrease diff at time 3 (when it hits the top boundary, position 5).
- Piston 1 (Moving Down):
  - Current position: 3, starts moving down.
  - Decrement diff by 1 because moving down decreases area.
  - In delta, set an event to increase diff at time 4 (when it hits the bottom boundary, position 0).
Simulate Movements:
- Start by iterating over the sorted keys of delta (events at time 3 and 4).
- Time 3 Event:
  - diff changes from 1 to 0 (Piston 0 hits the top).
  - Before adjusting diff, compute the area addition: (3 - 0) * 1 = 3, update res to 8.
  - ans is updated to 8 as it's greater than initial res.
- Time 4 Event:
  - Adjust diff for Piston 1 hitting the bottom boundary: from 0 to 1.
  - Compute area addition from 3 to 4 with diff as 0: 0. Area remains 8.
  - ans remains 8 as it's the maximum so far.
Return Result:
- After processing all events, the maximum possible area (ans) is 8.

This walkthrough demonstrates how the solution tracks pistons' movements with events to compute the maximum area efficiently over time.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4class Solution:
5    def maxArea(self, height: int, positions: List[int], directions: str) -> int:
6        # Dictionary to keep track of differences of positions
7        delta = defaultdict(int)
8        # Initial difference and result
9        diff = res = 0
10      
11        # Iterate through each position and its corresponding direction
12        for pos, dir in zip(positions, directions):
13            # Add the position to the current result
14            res += pos
15            if dir == "U":
16                # Moving up increases the difference
17                diff += 1
18                # Adjust the difference for the position moving up
19                delta[height - pos] -= 2
20                delta[height * 2 - pos] += 2
21            else:
22                # Moving down decreases the difference
23                diff -= 1
24                # Adjust the difference for the position moving down
25                delta[pos] += 2
26                delta[height + pos] -= 2
27      
28        # Initialize the answer with the current result
29        ans = res
30        # Previous checkpoint initialized to zero
31        pre = 0
32      
33        # Process each checkpoint in sorted order
34        for cur, d in sorted(delta.items()):
35            # Update the result based on the difference and distance moved
36            res += (cur - pre) * diff
37            # Update the previous checkpoint
38            pre = cur
39            # Update the difference at the current checkpoint
40            diff += d
41            # Update the answer with the current maximum result
42            ans = max(ans, res)
43      
44        # Return the maximum calculated area
45        return ans
46

1import java.util.Map;
2import java.util.TreeMap;
3
4class Solution {
5    public long maxArea(int height, int[] positions, String directions) {
6        // Use a TreeMap to maintain the changes in delta at different positions
7        Map<Integer, Integer> delta = new TreeMap<>();
8        int diff = 0; // Initialize the difference tracker
9        long res = 0; // Initialize the result
10
11        // Traverse each position and its corresponding direction
12        for (int i = 0; i < positions.length; ++i) {
13            int pos = positions[i];
14            char dir = directions.charAt(i);
15            res += pos;
16
17            // Modify delta based on the direction
18            if (dir == 'U') {  // Direction is 'Up'
19                ++diff;
20                // Subtract 2 when at height - pos, add 2 at height * 2 - pos
21                delta.merge(height - pos, -2, Integer::sum);
22                delta.merge(height * 2 - pos, 2, Integer::sum);
23            } else {  // Direction is 'Down'
24                --diff;
25                // Add 2 when at pos, subtract 2 at height + pos
26                delta.merge(pos, 2, Integer::sum);
27                delta.merge(height + pos, -2, Integer::sum);
28            }
29        }
30
31        long ans = res; // Start by considering the initial result as the answer
32        int pre = 0; // Track the previous position in the delta map
33
34        // Iterate over sorted entries of delta
35        for (Map.Entry<Integer, Integer> entry : delta.entrySet()) {
36            int cur = entry.getKey();
37            int d = entry.getValue();
38
39            // Calculate the new result by expanding the difference between cur and pre
40            res += (long) (cur - pre) * diff;
41            pre = cur; // Update previous position to current
42
43            // Update the cumulative difference
44            diff += d;
45
46            // Update the answer with the maximum value found
47            ans = Math.max(ans, res);
48        }
49
50        // Return the maximum area found
51        return ans;
52    }
53}
54

1class Solution {
2public:
3    long long maxArea(int height, vector<int>& positions, string directions) {
4        // 'delta' map stores changes in the diff at specific positions
5        map<int, int> delta;
6        int diff = 0;  // 'diff' counts the net effect of directions
7        long long res = 0;  // 'res' tracks the running total of positions
8      
9        // Loop over each element in positions and directions
10        for (int i = 0; i < positions.size(); ++i) {
11            int position = positions[i];
12            char direction = directions[i];
13            res += position;  // Add the current position to the total
14          
15            // If direction is 'U', update 'delta' and increase 'diff'
16            if (direction == 'U') {
17                ++diff;  // Increment the effect of 'U' direction by 1
18                delta[height - position] -= 2;  // Mark changes at entering and exiting points
19                delta[height * 2 - position] += 2;  // Update for twice the height
20            } 
21            // If direction is 'D', update 'delta' and decrease 'diff'
22            else {
23                --diff;  // Decrement the effect of 'D' direction by 1
24                delta[position] += 2;  // Mark changes at entering and exiting points
25                delta[height + position] -= 2;  // Update for height above current
26            }
27        }
28
29        long long maxResult = res;  // 'maxResult' stores the maximum area found
30        int previousPoint = 0;  // 'previousPoint' tracks the last processed position
31      
32        // Iterate over the 'delta' map to compute the maximum area
33        for (const auto& [currentPoint, deltaEffect] : delta) {
34            // Calculate the total area between 'previousPoint' and 'currentPoint'
35            res += static_cast<long long>(currentPoint - previousPoint) * diff;
36            previousPoint = currentPoint;  // Update 'previousPoint' to 'currentPoint'
37            diff += deltaEffect;  // Adjust 'diff' by the value at 'currentPoint'
38            maxResult = max(maxResult, res);  // Update 'maxResult' if a new maximum is found
39        }
40
41        return maxResult;  // Return the maximum area
42    }
43};
44

1// Function to calculate the maximum area given the height of bars, their positions, and movement directions.
2function maxArea(height: number, positions: number[], directions: string): number {
3    // Initialize an array to capture responses
4    let maxArea = 0;
5
6    // Iterate over bar positions
7    for (let i = 0; i < positions.length; i++) {
8        for (let j = i + 1; j < positions.length; j++) {
9            // Determine the vertical distance and horizontal distance between the two bars
10            const width = positions[j] - positions[i];
11            const minHeight = Math.min(height, height);
12
13            // Calculate the area for this pair of bars
14            const area = width * minHeight;
15
16            // Update maxArea if the calculated area is larger
17            maxArea = Math.max(maxArea, area);
18        }
19    }
20
21    // Return the maximum achieved area
22    return maxArea;
23}
24

Time and Space Complexity

Time Complexity: The time complexity of the code is primarily determined by the loop iterating through the positions and directions arrays and the sorting operation on the delta dictionary. The loop has a time complexity of O(n), where n is the length of the positions. The sorting operation has a time complexity of O(m log m), where m is the number of unique keys in the delta dictionary. Therefore, the overall time complexity is O(n + m log m).
Space Complexity: The space complexity is determined by the space used for the delta dictionary, which can contain up to n keys in the worst-case scenario. Thus, the overall space complexity is O(m), where m is the number of distinct keys in the delta dictionary.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First Search

Breadth-First Search

Binary Search

Priority Queue

I don’t know