LeetCode Problem 1599

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

LeetCode 1599 - Maximum Profit of Operating a Centennial Wheel

Problem Understanding

This problem asks us to simulate the operation of a Centennial Wheel and determine the minimum number of rotations required to achieve the maximum possible profit.

The wheel has four gondolas, and each gondola can hold at most four people during a single rotation. Customers arrive over time according to the customers array. Specifically, customers[i] represents the number of customers who arrive immediately before the i-th rotation.

At every rotation:

• Up to four waiting customers can board.
• Every boarded customer generates boardingCost dollars of revenue.
• Rotating the wheel costs runningCost dollars.

The goal is to determine the rotation count at which total profit becomes as large as possible. If the wheel never produces positive profit, we return -1.

The important detail is that customers who cannot board immediately must wait for future rotations. Also, once we stop operating the wheel, any remaining rotations needed to unload passengers are considered free and do not affect profit.

The input constraints are important:

• customers.length can be as large as 10^5
• Each customers[i] is at most 50

This tells us that the solution must be efficient, ideally linear time. A quadratic or heavily nested simulation would be too slow.

Several edge cases are important:

• Profit may never become positive.
• There may still be waiting customers after processing the entire input array.
• Some rotations may board fewer than four people.
• Running the wheel when nobody boards may reduce profit.
• The optimal stopping point may occur before all customers are served.

A correct implementation must carefully track waiting customers, total profit, and the rotation count where profit is maximized.

Approaches

Brute Force Approach

A brute-force approach would attempt to simulate every possible stopping point independently.

For every possible number of rotations:

1. Simulate wheel operation from the beginning.
2. Track waiting customers.
3. Compute cumulative revenue and cost.
4. Record the profit for that stopping point.
5. Return the smallest rotation count that achieves maximum profit.

This approach is correct because it explicitly evaluates every possible operating duration. However, it repeatedly recomputes the same simulation state from scratch.

If there are n rotations, and each candidate stopping point requires another full simulation, the total complexity becomes quadratic.

With n up to 10^5, an O(n^2) solution is far too slow.

Optimal Simulation Approach

The key insight is that we do not need to restart the simulation for every possible stopping point.

Profit evolves incrementally:

• Each rotation changes the profit by:

boarded * boardingCost - runningCost

So we can process rotations one at a time while continuously maintaining:

• waiting customers
• current profit
• maximum profit seen so far
• rotation count where maximum profit occurred

Even after all arrivals are processed, we may still have waiting customers, so the simulation must continue until the queue becomes empty.

This produces a simple linear-time simulation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes the simulation for every stopping point
Optimal	O(n)	O(1)	Single-pass simulation with incremental profit tracking

Algorithm Walkthrough

Step 1: Initialize tracking variables

We maintain several variables throughout the simulation:

• waiting_customers tracks how many customers are still waiting to board.
• current_profit stores cumulative profit so far.
• max_profit stores the best profit seen.
• best_rotation stores the rotation count where maximum profit occurred.
• rotation_count tracks total rotations performed.

Initially:

• no customers are waiting
• profit is zero
• maximum profit is zero
• best rotation is -1

We use -1 because if profit never becomes positive, the answer must be -1.

Step 2: Process incoming customers

For each rotation index:

1. Add newly arriving customers to the waiting queue.
2. Board up to four customers.
3. Subtract running cost.
4. Add boarding revenue.
5. Update the maximum profit if necessary.

The boarding count is:

min(4, waiting_customers)

because each rotation can carry at most four people.

Step 3: Continue rotating after all arrivals

After processing the input array, customers may still be waiting.

We continue rotating while:

waiting_customers > 0

Each extra rotation boards up to four remaining customers and updates profit exactly the same way.

Step 4: Track the best profit

After every rotation:

• if current_profit > max_profit

• update max_profit

• store current rotation count as answer

The problem asks for the minimum number of rotations that achieves maximum profit, so we only update when profit becomes strictly larger.

Step 5: Return the result

If maximum profit never became positive, return -1.

Otherwise, return the stored rotation count.

Why it works

The algorithm works because profit changes only through local rotation events. Every possible operating duration corresponds to some prefix of the simulation. By evaluating profit immediately after every rotation, we examine every possible stopping point exactly once.

Since we always record the first rotation count achieving a new maximum profit, the stored answer is guaranteed to be the minimum number of rotations producing that maximum.

Python Solution

from typing import List

class Solution:
    def minOperationsMaxProfit(
        self,
        customers: List[int],
        boardingCost: int,
        runningCost: int
    ) -> int:
        
        waiting_customers = 0
        current_profit = 0
        max_profit = 0
        
        best_rotation = -1
        rotation_count = 0
        
        index = 0
        n = len(customers)
        
        while index < n or waiting_customers > 0:
            
            if index < n:
                waiting_customers += customers[index]
            
            boarded = min(4, waiting_customers)
            waiting_customers -= boarded
            
            rotation_count += 1
            
            current_profit += boarded * boardingCost
            current_profit -= runningCost
            
            if current_profit > max_profit:
                max_profit = current_profit
                best_rotation = rotation_count
            
            index += 1
        
        return best_rotation

The implementation follows the simulation process directly.

The variable waiting_customers stores the current queue size. At each iteration, new arrivals are added if there are still elements remaining in the input array.

We then determine how many people can board during the current rotation. Since the gondola capacity is four, we use:

boarded = min(4, waiting_customers)

After boarding:

• the queue decreases
• the rotation count increases
• revenue and running cost are applied

The current profit is compared against the best profit seen so far. If the current value is larger, we update both max_profit and best_rotation.

The loop condition is especially important:

while index < n or waiting_customers > 0:

This ensures we continue operating the wheel even after all arrivals have been processed, as long as customers are still waiting.

Finally, if profit never became positive, best_rotation remains -1, which matches the problem requirements.

Go Solution

func minOperationsMaxProfit(customers []int, boardingCost int, runningCost int) int {
    waitingCustomers := 0
    currentProfit := 0
    maxProfit := 0

    bestRotation := -1
    rotationCount := 0

    index := 0
    n := len(customers)

    for index < n || waitingCustomers > 0 {

        if index < n {
            waitingCustomers += customers[index]
        }

        boarded := waitingCustomers
        if boarded > 4 {
            boarded = 4
        }

        waitingCustomers -= boarded

        rotationCount++

        currentProfit += boarded * boardingCost
        currentProfit -= runningCost

        if currentProfit > maxProfit {
            maxProfit = currentProfit
            bestRotation = rotationCount
        }

        index++
    }

    return bestRotation
}

The Go implementation mirrors the Python logic closely.

Since Go does not provide a built-in min function for integers, we compute the boarded count manually using a conditional check.

All values remain safely within Go's standard integer range because the constraints are relatively small. No special overflow handling is required.

The loop condition is identical to the Python version and ensures remaining queued customers are fully processed.

Worked Examples

Example 1

Input:

customers = [8,3]
boardingCost = 5
runningCost = 6

Rotation	New Arrivals	Waiting Before Boarding	Boarded	Waiting After	Profit Change	Total Profit	Best Rotation
1	8	8	4	4	20 - 6 = 14	14	1
2	3	7	4	3	20 - 6 = 14	28	2
3	0	3	3	0	15 - 6 = 9	37	3

Maximum profit is 37, achieved after 3 rotations.

Answer:

3

Example 2

Input:

customers = [10,9,6]
boardingCost = 6
runningCost = 4

Rotation	New Arrivals	Waiting Before Boarding	Boarded	Waiting After	Profit Change	Total Profit
1	10	10	4	6	24 - 4 = 20	20
2	9	15	4	11	24 - 4 = 20	40
3	6	17	4	13	24 - 4 = 20	60
4	0	13	4	9	24 - 4 = 20	80
5	0	9	4	5	24 - 4 = 20	100
6	0	5	4	1	24 - 4 = 20	120
7	0	1	1	0	6 - 4 = 2	122

Maximum profit occurs after 7 rotations.

Answer:

7

Example 3

Input:

customers = [3,4,0,5,1]
boardingCost = 1
runningCost = 92

Rotation	Boarded	Revenue	Cost	Total Profit
1	3	3	92	-89
2	4	7	184	-177
3	0	7	276	-269
4	4	11	368	-357
5	2	13	460	-447

Profit never becomes positive.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each customer rotation is processed once
Space	O(1)	Only a few integer variables are maintained

The simulation performs one iteration per wheel rotation. Every rotation either processes a customer arrival or removes waiting customers from the queue. Since each customer can only wait and board once, the total work grows linearly with the input size.

No auxiliary data structures proportional to input size are used, so space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def minOperationsMaxProfit(
        self,
        customers: List[int],
        boardingCost: int,
        runningCost: int
    ) -> int:
        
        waiting_customers = 0
        current_profit = 0
        max_profit = 0
        
        best_rotation = -1
        rotation_count = 0
        
        index = 0
        n = len(customers)
        
        while index < n or waiting_customers > 0:
            
            if index < n:
                waiting_customers += customers[index]
            
            boarded = min(4, waiting_customers)
            waiting_customers -= boarded
            
            rotation_count += 1
            
            current_profit += boarded * boardingCost
            current_profit -= runningCost
            
            if current_profit > max_profit:
                max_profit = current_profit
                best_rotation = rotation_count
            
            index += 1
        
        return best_rotation

solution = Solution()

assert solution.minOperationsMaxProfit([8,3], 5, 6) == 3
# Basic example with leftover queue after arrivals end

assert solution.minOperationsMaxProfit([10,9,6], 6, 4) == 7
# Long profitable run with many waiting customers

assert solution.minOperationsMaxProfit([3,4,0,5,1], 1, 92) == -1
# Profit never becomes positive

assert solution.minOperationsMaxProfit([4], 10, 1) == 1
# Exactly full gondola in one rotation

assert solution.minOperationsMaxProfit([0,0,0], 10, 1) == -1
# No customers ever board

assert solution.minOperationsMaxProfit([1,1,1,1], 100, 1) == 4
# Small arrivals across many rotations

assert solution.minOperationsMaxProfit([50], 10, 1) == 13
# Large waiting queue requiring many extra rotations

assert solution.minOperationsMaxProfit([4,4,4,4], 2, 8) == -1
# Revenue equals cost per full rotation, never positive

assert solution.minOperationsMaxProfit([4,4,4,4], 3, 8) == 4
# Positive profit only with consistently full gondolas

assert solution.minOperationsMaxProfit([2,2,2], 5, 6) == 3
# Partial gondolas can still produce profit

Test Case Summary

Test	Why
[8,3], 5, 6	Standard example with remaining queue
[10,9,6], 6, 4	Large queue and extended processing
[3,4,0,5,1], 1, 92	Profit never becomes positive
[4], 10, 1	Single perfect rotation
[0,0,0], 10, 1	No passengers at all
[1,1,1,1], 100, 1	Small repeated arrivals
[50], 10, 1	Many extra rotations after arrivals
[4,4,4,4], 2, 8	Revenue exactly balanced by cost
[4,4,4,4], 3, 8	Always profitable full rotations
[2,2,2], 5, 6	Profitable partial loads

Edge Cases

Profit Never Becomes Positive

One tricky case occurs when the operating cost is too high relative to boarding revenue. Even if customers continue boarding, the wheel may continuously lose money.

For example:

customers = [3,4,0,5,1]
boardingCost = 1
runningCost = 92

A buggy implementation might incorrectly return the final rotation count instead of -1.

This implementation avoids that issue by initializing:

best_rotation = -1

and only updating it when profit becomes strictly positive.

Remaining Customers After Input Ends

Another important case occurs when customers are still waiting after all arrivals have been processed.

For example:

customers = [50]

Even though the array contains only one entry, the wheel must continue rotating until all waiting customers are served.

The loop condition:

while index < n or waiting_customers > 0

ensures these remaining customers are processed correctly.

Rotations With Partial Gondolas

A subtle bug can happen when fewer than four customers are available.

For example:

customers = [1,1,1]

An incorrect implementation might assume every profitable rotation boards exactly four people.

Instead, this solution correctly computes:

boarded = min(4, waiting_customers)

which handles partially filled gondolas naturally and ensures accurate profit calculations.