LC-3025 Medium LeetCode

3025. Find the Number of Ways to Place People I

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 41% Topics: Array, Math, Geometry, Sorting, Enumeration

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(n^2)
# Space: O(1)

# sort, array
class Solution(object):
    def numberOfPairs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        points.sort(key=lambda x: (x[0], -x[1]))
        result = 0
        for i in xrange(len(points)):
            y = float("-inf")
            for j in xrange(i+1, len(points)):
                if points[i][1] < points[j][1]:
                    continue
                if points[j][1] > y:
                    y = points[j][1]
                    result += 1
        return result


# Time:  O(n^3)
# Space: O(1)
# sort, array
class Solution2(object):
    def numberOfPairs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        points.sort(key=lambda x: (x[0], -x[1]))
        return sum(all(not points[i][1] >= points[k][1] >= points[j][1] for k in xrange(i+1, j))
                   for i in xrange(len(points))
                   for j in xrange(i+1, len(points)) if points[i][1] >= points[j][1])

Solution from kamyu104/LeetCode-Solutions · MIT