LeetCode Entry

2251. Number of Flowers in Full Bloom

11.10.2023 hard 2023 kotlin

Array of counts of segments in intersection

2251. Number of Flowers in Full Bloom hard blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/366

Problem TLDR

Array of counts of segments in intersection

Intuition

We need to quickly count how many segments are for any particular time. If we sort segments by from position, we can use line sweep, and we also need to track times when count decreases. To find out how many people in a time range we can sort them and use Binary Search.

Approach

• to track count changes let’s store time deltas in timeToDelta HashMap
• careful with storing decreases, they are starting in to + 1
• instead of sorting the segments we can use a TreeMap
• we need to preserve peoples order, so use separate sorted indices collection

For better Binary Search code:

• use inclusive lo and hi
• check the last condition lo == hi
• always save a good result peopleIndBefore = max(.., mid)
• always move the borders lo = mid + 1, hi = mid - 1
• if mid is less than target drop everything on the left side: lo = mid + 1

Complexity

• Time complexity: \(O(nlog(n))\)

• Space complexity: \(O(n)\)

Code

    fun fullBloomFlowers(flowers: Array<IntArray>, people: IntArray): IntArray {
      val peopleInds = people.indices.sortedBy { people[it] }
      val timeToDelta = TreeMap<Int, Int>()
      for ((from, to) in flowers) {
        timeToDelta[from] = 1 + (timeToDelta[from] ?: 0)
        timeToDelta[to + 1] = -1 + (timeToDelta[to + 1] ?: 0)
      }
      val res = IntArray(people.size)
      var count = 0
      var lastPeopleInd = -1
      timeToDelta.onEach { (time, delta) ->
        var lo = max(0, lastPeopleInd - 1)
        var hi = peopleInds.lastIndex
        var peopleIndBefore = -1
        while (lo <= hi) {
          val mid = lo + (hi - lo) / 2
          if (people[peopleInds[mid]] < time) {
            peopleIndBefore = max(peopleIndBefore, mid)
            lo = mid + 1
          } else hi = mid - 1
        }
        for (i in max(0, lastPeopleInd)..peopleIndBefore) res[peopleInds[i]] = count
        count += delta
        lastPeopleInd = peopleIndBefore + 1
      }
      return res
    }