Academy
hardJS ES5#116

Urinales libres (free urinals)

Prompt

Given a binary string representing occupied (1) and free (0) urinals, return the maximum number of additional people who can use them. Rule: at least one urinal gap between users. Return -1 if the input already violates the rule (two adjacent 1s).

Solution

function freeUrinals(urinals) {
  if (urinals.includes('11')) return -1
  let count = 0
  const arr = urinals.split('')
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === '0' && (i === 0 || arr[i - 1] === '0') && (i === arr.length - 1 || arr[i + 1] === '0')) {
      count++
      arr[i] = '1'
    }
  }
  return count
}
Mentor's take

This is a greedy placement problem (LeetCode's "Can Place Flowers" in disguise): scan left to right, place at the first legal slot, mark it occupied, continue. The greedy choice is provably optimal here — placing as early as possible never blocks more future placements than it enables, because each placement's "shadow" (itself plus one neighbor to the right) is minimal when you take the leftmost legal spot. O(n) time, O(n) space for the split array (O(1) if you track only the previous cell).

Three mechanics carry the solution:

  • Validate first. urinals.includes('11') rejects already-invalid input in one pass. Validation before computation, always — otherwise you compute a "max additions" for a state that can't exist.
  • Boundary conditions as short-circuits. i === 0 || arr[i-1] === '0' treats the wall as a free neighbor. Ends of the array are where the off-by-ones live.
  • Mutate as you place. Setting arr[i] = '1' makes each placement visible to the next iteration's neighbor check. Skipping this double-books adjacent zeros — "000" would wrongly report 3 instead of 2. Strings are immutable, hence the split('') to get a writable array.

The naive alternative — try all subsets of free positions — is exponential; the greedy insight collapses it to one scan. If asked to prove greed works, the exchange argument is the phrase to reach for.

Red flag: forgetting to mark placements as occupied, so the scan counts overlapping placements. It's the single most common failure on this problem and "000" exposes it immediately.

Say it: "Greedy left-to-right: validate for adjacent ones, place at every slot whose neighbors are free, and mark it occupied so the next check sees it — leftmost placement is provably optimal by an exchange argument."