LC-2280 Medium LeetCode

2280. Minimum Lines to Represent a Line Chart

Array Math Geometry Sorting Number Theory

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 26% Topics: Array, Math, Geometry, Sorting, Number Theory

Reading material

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

Reference solution (spoiler · python)

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

# sort, math, gcd
class Solution(object):
    def minimumLines(self, stockPrices):
        """
        :type stockPrices: List[List[int]]
        :rtype: int
        """
        def gcd(a, b):
            while b:
                a, b = b, a%b
            return a
    
        stockPrices.sort()
        result = 0
        prev = None
        for i in xrange(1, len(stockPrices)):
            dy, dx = stockPrices[i][1]-stockPrices[i-1][1], stockPrices[i][0]-stockPrices[i-1][0]
            g = gcd(dy, dx)
            if not prev or prev != (dy//g, dx//g):
                prev = (dy//g, dx//g)
                result += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT