# 31.08.2023 [1326. Minimum Number of Taps to Open to Water a Garden]

Fill all space between `0..n` using minimum intervals

31.08.2023

1326. Minimum Number of Taps to Open to Water a Garden hard
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/325

Problem TLDR

Fill all space between 0..n using minimum intervals

Intuition

We need to fill space between points, so skip all zero intervals. Next, sort intervals and scan them greedily. Consider space between lo..hi as filled. If from > lo we must open another water source. However, there are possible good candidates before, if their to > hi.

      //     0 1 2 3 4 5 6 7 8 9
      //     0 5 0 3 3 3 1 4 0 4
      // 1 5 *************
      //     ^           ^
      //     lo          hi
      // 3 3 *************
      // 4 3   *************
      //       ^         . ^
      //       from      . to
      //                 *** opened++  
      //                 ^ ^
      //                lo hi
      // 5 3     *************
      //                     ^ hi
      // 7 4       *************
      //                       ^ hi finish
      // 6 1           *****
      // 9 4           *********

Approach

Look at others solutions and steal the implementation

Complexity

• Time complexity:
  O(nlog(n)), for sorting

• Space complexity:
  O(n), to store the intervals

Code

    fun minTaps(n: Int, ranges: IntArray): Int {
      var opened = 0
      var lo = -1
      var hi = 0
      ranges.mapIndexed { i, v -> maxOf(0, i - v) to minOf(i + v, n) }
        .filter { it.first != it.second }
        .sortedBy { (from, _) -> from }
        .onEach { (from, to) ->
          if (from <= lo) hi = maxOf(hi, to)
          else if (from <= hi) {
            lo = hi
            hi = to
            opened++
          }
          if (hi == n) return opened
        }
      return -1
    }