Minimum Lines to Represent a Line Chart

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

from math import gcd
from typing import List

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        cnt = 0
        dx = float('-inf')
        dy = float('-inf')
        stockPrices.sort()

        for i in range(1, len(stockPrices)):
            dx1 = stockPrices[i][0] - stockPrices[i - 1][0]
            dy1 = stockPrices[i][1] - stockPrices[i - 1][1]
            d = gcd(dx1, dy1)

            if dx != dx1 // d or dy != dy1 // d:
                cnt += 1

            dx = dx1 // d
            dy = dy1 // d

        return cnt