LC-1943 Medium LeetCode

1943. Describe the Painting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 51% Topics: Array, Hash Table, Sorting, Prefix Sum

Reading material

Arrays & Hashing 12 min Sorting 13 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

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

import collections


class Solution(object):
    def splitPainting(self, segments):
        """
        :type segments: List[List[int]]
        :rtype: List[List[int]]
        """
        counts = collections.defaultdict(int)
        for s, e, c in segments:
            counts[s] += c
            counts[e] -= c
        points = sorted(x for x in counts.iteritems())

        result = []
        overlap = prev = 0
        for curr, cnt in points:
            if overlap:
                result.append([prev, curr, overlap])
            overlap += cnt
            prev = curr
        return result

Solution from kamyu104/LeetCode-Solutions · MIT