DDSA Solutions

3100. Water Bottles II

EasyView on LeetCode
MathSimulation

Problem Overview

Detect if water flows to Pacific and Atlantic.

Intuition

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

Algorithm

  1. 1Two BFS: one from Pacific border cells, one from Atlantic. Water flows UP (reverse direction).
  2. 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
C#
// 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?

Related Problems