LC-2251 Hard LeetCode

2251. Number of Flowers in Full Bloom

Array Hash Table Binary Search Sorting Prefix Sum Ordered Set

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 57% Topics: Array, Hash Table, Binary Search, Sorting, Prefix Sum, Ordered Set

Reading material

Arrays & Hashing 12 min Binary Search 12 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn + mlogn)
# Space: O(n)

import bisect


# line sweep, binary search
class Solution(object):
    def fullBloomFlowers(self, flowers, persons):
        """
        :type flowers: List[List[int]]
        :type persons: List[int]
        :rtype: List[int]
        """
        cnt = collections.Counter()
        for s, e in flowers:
            cnt[s] += 1
            cnt[e+1] -= 1
        events = sorted(cnt.iterkeys())
        prefix = [0]
        for x in events:
            prefix.append(prefix[-1]+cnt[x])
        return [prefix[bisect.bisect_right(events, t)] for t in persons]


# Time:  O(nlogn + mlogn)
# Space: O(n)
import bisect


# binary search
class Solution(object):
    def fullBloomFlowers(self, flowers, persons):
        """
        :type flowers: List[List[int]]
        :type persons: List[int]
        :rtype: List[int]
        """
        starts, ends = [], []
        for s, e in flowers:
            starts.append(s)
            ends.append(e+1)
        starts.sort()
        ends.sort()
        return [bisect.bisect_right(starts, t)-bisect.bisect_right(ends, t) for t in persons]

Solution from kamyu104/LeetCode-Solutions · MIT