Maximum Total Area Occupied by Pistons - Practice Coding Problems

Maximum Total Area Occupied by Pistons - Problem

Array Hash Table String Simulation Counting Prefix Sum Hard

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.

Input & Output

Example 1 — Basic Case

$ Input: height = 4, positions = [1,3,2], directions = "UDU"

› Output: 8

💡 Note: At time 2: piston 1 reaches position 3 (up from 1), piston 2 reaches position 1 (down from 3), piston 3 reaches position 4 (up from 2). Total area = 3+1+4 = 8

Example 2 — All Moving Up

$ Input: height = 3, positions = [1,2], directions = "UU"

› Output: 6

💡 Note: Both pistons move up. At time 1: positions become [2,3], total = 5. At time 2: positions become [3,3] (piston 2 bounces), total = 6

Example 3 — Single Piston

$ Input: height = 5, positions = [2], directions = "D"

› Output: 5

💡 Note: Piston moves down to 0, then up to maximum height 5. Maximum area is 5 when it reaches the top

Constraints

1 ≤ height ≤ 10⁵
1 ≤ positions.length ≤ 10⁴
0 ≤ positions[i] ≤ height
directions.length == positions.length
directions[i] is either 'U' or 'D'

Visualization

Tap to expand

Understanding the Visualization

Input

Pistons at positions [1,3,2] with directions UDU in chambers of height 4

Process

Track piston movements over time to find when total area is maximized

Output

Maximum total area is 8 (achieved at time t=2)

Key Takeaway

🎯 Key Insight: Pistons follow predictable bounce patterns - find optimal time when total area peaks

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that pistons follow predictable cycles. The simulation approach tracks movement step-by-step, while the mathematical approach calculates positions directly using cycle analysis. Best approach is mathematical analysis with Time: O(n × height), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Simulation	O(T × n)	O(1)	Simulate piston movements second by second until a pattern emerges
Mathematical Analysis	O(n × height)	O(1)	Calculate maximum area by analyzing each piston's cycle independently

Simulation — Algorithm Steps

Step 1: Simulate each second by updating positions and directions
Step 2: Calculate total area at each step
Step 3: Track maximum area encountered

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Pistons at starting positions with directions

Simulate Movement

Move each piston and change direction at boundaries

Track Maximum

Record highest total area encountered

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int height, int* positions, int posSize, char* directions) {
    int* pos = malloc(posSize * sizeof(int));
    char* dirs = malloc((posSize + 1) * sizeof(char));
    
    for (int i = 0; i < posSize; i++) {
        pos[i] = positions[i];
        dirs[i] = directions[i];
    }
    dirs[posSize] = '\0';
    
    int maxArea = 0;
    for (int i = 0; i < posSize; i++) {
        maxArea += pos[i];
    }
    
    // Simple simulation with time limit
    for (int t = 0; t < 10000; t++) {
        for (int i = 0; i < posSize; i++) {
            if (dirs[i] == 'U') {
                pos[i]++;
                if (pos[i] == height) dirs[i] = 'D';
            } else {
                pos[i]--;
                if (pos[i] == 0) dirs[i] = 'U';
            }
        }
        
        int sum = 0;
        for (int i = 0; i < posSize; i++) {
            sum += pos[i];
        }
        if (sum > maxArea) maxArea = sum;
    }
    
    free(pos);
    free(dirs);
    return maxArea;
}

int main() {
    int height;
    scanf("%d", &height);
    
    char line[1000];
    scanf(" %s", line);
    
    // Parse array manually
    int positions[100];
    int posSize = 0;
    char* ptr = line + 1; // skip '['
    while (*ptr != ']') {
        if (*ptr == ',' || *ptr == '[') ptr++;
        positions[posSize++] = atoi(ptr);
        while (*ptr != ',' && *ptr != ']') ptr++;
    }
    
    char directions[101];
    scanf("%s", directions);
    
    int result = solution(height, positions, posSize, directions);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(T × n)

T seconds of simulation × n pistons to update each second

✓ Linear Growth

Space Complexity

O(1)

Only storing current positions and directions

✓ Linear Space

28.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler