3100. Water Bottles II

EasyView on LeetCode

Math Simulation

Intuition

Detect if water flows to Pacific and Atlantic. Multi-source BFS from ocean borders inward.

Algorithm

1Two BFS: one from Pacific border cells, one from Atlantic. Water flows UP (reverse direction).
2Return cells reachable by both BFS.

Common Pitfalls

•Reverse problem: find cells that can reach ocean. BFS from ocean going to higher cells.

3100.cs

// Approach: Simulate; each round trade numExchange empties for 1 full; numExchange increments each trade.
// Time: O(sqrt(n)) Space: O(1)

class Solution
{
    public int MaxBottlesDrunk(int numBottles, int numExchange)
    {
        int ans = numBottles;

        while (numBottles >= numExchange)
        {
            numBottles = (numBottles - numExchange + 1);
            ++numExchange;
            ++ans;
        }

        return ans;
    }
}

Was this solution helpful?