Problem Description

You operate a Ferris wheel (Centennial Wheel) with 4 gondolas, where each gondola can hold up to 4 people. The wheel rotates counterclockwise, and each rotation costs you runningCost dollars.

You're given an array customers where customers[i] represents the number of new customers arriving just before the i-th rotation (0-indexed). This means the wheel must rotate i times before these customers arrive.

Key rules:

• You cannot make customers wait if there's room in a gondola
• Each customer pays boardingCost dollars when boarding the gondola at the ground level
• Customers exit when their gondola returns to the ground (after a full rotation)
• At most 4 customers can board per rotation (even if more are waiting)
• Excess customers wait for the next rotation
• You can stop the wheel at any time, even before serving all customers
• Once you stop charging customers, all remaining rotations to safely unload passengers are free

Your goal is to find the minimum number of rotations that maximizes your profit. Profit is calculated as: (total boarding fees collected) - (total running costs for paid rotations)

Return the optimal number of rotations, or -1 if no positive profit is possible.

Example scenario: If 5 customers arrive before rotation 0, only 4 can board immediately, and 1 must wait for the next rotation. You earn 4 * boardingCost but pay runningCost for that rotation.

Intuition

The key insight is that we need to simulate the actual operation of the Ferris wheel rotation by rotation, because the profit changes dynamically with each rotation and we want to find the optimal stopping point.

Think about it this way: at each rotation, we have some customers waiting (from previous arrivals or overflow), and potentially new customers arriving. We can board at most 4 people per rotation. Each rotation adds boardingCost * (number of people boarding) to our revenue but costs us runningCost to operate.

The profit at any point is cumulative - it's the total revenue minus total costs up to that rotation. Since we can stop at any time, we want to track the maximum profit we've seen so far and remember at which rotation it occurred.

Why can't we use a formula or mathematical approach? Because the arrival pattern is irregular - customers arrive in batches at specific rotations, and we have the constraint of maximum 4 people per gondola. This creates a queue of waiting customers that varies over time.

The simulation continues as long as either:

1. We still have customers in the input array who haven't arrived yet, OR
2. We have customers waiting to board

For each rotation, we:

• Add newly arriving customers to our waiting queue
• Board up to 4 customers (up = min(wait, 4))
• Calculate the profit change: up * boardingCost - runningCost
• Track if this gives us a better total profit than before

The reason we track the "minimum number of rotations" for maximum profit is that if the same maximum profit occurs at different rotations, we want the earliest one (fewer rotations = stop earlier).

Solution Approach

The solution uses a simulation approach to track the Ferris wheel operation rotation by rotation.

Variables used:

• ans = -1: Stores the optimal number of rotations (initialized to -1 for the case when no positive profit is possible)
• mx = 0: Tracks the maximum profit seen so far
• t = 0: Current cumulative profit
• wait = 0: Number of customers currently waiting to board
• i = 0: Current rotation number (counter)

Algorithm steps:

1. Continue simulation while needed: The loop runs as long as wait > 0 (customers still waiting) OR i < len(customers) (more customers will arrive).

2. Handle new arrivals:

   wait += customers[i] if i < len(customers) else 0

   If we haven't processed all customer arrivals yet, add the new arrivals to the waiting queue.

3. Board customers:

   up = wait if wait < 4 else 4
   wait -= up

   Board up to 4 customers from the waiting queue. If less than 4 are waiting, board them all.

4. Update profit:

   t += up * boardingCost - runningCost

   Add revenue from boarded customers and subtract the cost of this rotation.

5. Track maximum profit:

   i += 1
   if t > mx:
       mx = t
       ans = i

   Increment rotation counter. If current profit exceeds the maximum seen so far, update both the maximum profit and the optimal number of rotations.

6. Return result: After simulation completes, return ans. If profit never became positive, ans remains -1.

The beauty of this approach is its simplicity - it directly models the problem statement without trying to find a closed-form formula. By checking the profit at each rotation, we automatically find the optimal stopping point that maximizes profit.

Example Walkthrough

Let's walk through a small example where customers = [8, 3], boardingCost = 5, and runningCost = 6.

Initial state:

• ans = -1 (no profitable rotation found yet)
• mx = 0 (maximum profit so far)
• t = 0 (current cumulative profit)
• wait = 0 (customers waiting)
• i = 0 (rotation counter)

Rotation 0 (i=0):

• New arrivals: wait = 0 + 8 = 8 (8 customers arrive)
• Board customers: up = min(8, 4) = 4 (only 4 can board)
• Update waiting: wait = 8 - 4 = 4 (4 customers still waiting)
• Calculate profit: t = 0 + (4 × 5) - 6 = 20 - 6 = 14
• Increment rotation: i = 1
• Check if best: 14 > 0, so mx = 14, ans = 1

Rotation 1 (i=1):

• New arrivals: wait = 4 + 3 = 7 (3 more customers arrive, plus 4 waiting)
• Board customers: up = min(7, 4) = 4
• Update waiting: wait = 7 - 4 = 3
• Calculate profit: t = 14 + (4 × 5) - 6 = 14 + 20 - 6 = 28
• Increment rotation: i = 2
• Check if best: 28 > 14, so mx = 28, ans = 2

Rotation 2 (i=2):

• New arrivals: wait = 3 + 0 = 3 (no new customers, i >= len(customers))
• Board customers: up = min(3, 4) = 3
• Update waiting: wait = 3 - 3 = 0
• Calculate profit: t = 28 + (3 × 5) - 6 = 28 + 15 - 6 = 37
• Increment rotation: i = 3
• Check if best: 37 > 28, so mx = 37, ans = 3

End of simulation:

• No more waiting customers (wait = 0) and all arrivals processed (i >= len(customers))
• Return ans = 3

The optimal strategy is to run the Ferris wheel for 3 rotations, yielding a maximum profit of $37. Note how we had to continue past the point where all customers arrived (after rotation 1) because we still had waiting customers who could generate more profit.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m), where n is the length of the customers array and m is the number of additional rotations needed to board all waiting customers after processing the array. In the worst case where each customer arrives one at a time and the wheel can only take 4 at once, m could be proportional to the total number of customers, making the overall complexity O(total_customers). However, since we process the customers array element by element and then continue until all waiting customers are boarded, the time complexity can be simplified to O(n) when considering n as representing the effective number of operations needed.

The space complexity is O(1) as the algorithm only uses a constant amount of extra space regardless of the input size. The variables ans, mx, t, wait, i, and up are all scalar values that don't grow with the input size.

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

Common Pitfalls

Pitfall 1: Stopping Too Early When Profit Becomes Negative

The Mistake: A common error is to stop the simulation as soon as the profit becomes negative or starts decreasing, thinking that's the optimal stopping point.

# INCORRECT approach - stops too early
while waiting_customers > 0 or rotation < len(customers):
    # ... boarding logic ...
    current_profit += customers_boarding * boardingCost - runningCost
    rotation += 1
  
    if current_profit <= 0:  # Wrong! Stops at first negative
        break
  
    if current_profit > max_profit:
        max_profit = current_profit
        min_rotations = rotation

Why It's Wrong: The profit can temporarily dip negative but recover later when more customers arrive. For example:

• customers = [10, 10, 1, 0, 0], boardingCost = 4, runningCost = 20
• Early rotations might show negative profit, but accumulating customers leads to positive profit later

The Fix: Continue simulation through all possible rotations, tracking the maximum profit throughout:

# CORRECT approach - checks all possibilities
while waiting_customers > 0 or rotation < len(customers):
    # ... boarding logic ...
    current_profit += customers_boarding * boardingCost - runningCost
    rotation += 1
  
    # Always check if this is a new maximum, don't break early
    if current_profit > max_profit:
        max_profit = current_profit
        min_rotations = rotation

Pitfall 2: Incorrectly Handling Empty Rotations

The Mistake: Not properly accounting for rotations where no customers board (either because none are waiting or none have arrived yet).

# INCORRECT - skips empty rotations
if waiting_customers > 0:  # Wrong! Still costs money to rotate
    customers_boarding = min(waiting_customers, 4)
    current_profit += customers_boarding * boardingCost - runningCost
    rotation += 1

Why It's Wrong: Even if no customers board, you still pay runningCost for that rotation if you continue operating. This affects the total profit calculation.

The Fix: Always account for the running cost when the wheel rotates, regardless of whether customers board:

# CORRECT - accounts for all rotations
customers_boarding = min(waiting_customers, 4)  # Could be 0
current_profit += customers_boarding * boardingCost - runningCost  # Always subtract runningCost
rotation += 1

Pitfall 3: Off-by-One Error in Rotation Counting

The Mistake: Confusing when to increment the rotation counter - before or after updating the maximum profit.

# INCORRECT - updates rotation before checking profit
while waiting_customers > 0 or rotation < len(customers):
    rotation += 1  # Wrong position!
    # ... boarding logic ...
    current_profit += customers_boarding * boardingCost - runningCost
  
    if current_profit > max_profit:
        max_profit = current_profit
        min_rotations = rotation  # This is now off by one

Why It's Wrong: This makes the rotation count represent the "next" rotation rather than the "just completed" rotation, leading to incorrect answers.

The Fix: Increment rotation after calculating profit but before checking for maximum:

# CORRECT - proper ordering
while waiting_customers > 0 or rotation < len(customers):
    # ... boarding logic ...
    current_profit += customers_boarding * boardingCost - runningCost
  
    rotation += 1  # Increment after profit calculation
  
    if current_profit > max_profit:
        max_profit = current_profit
        min_rotations = rotation  # Now correctly represents completed rotations