Minimum Lines to Represent a Line Chart LeetCode solution in Python

1
from fractions import Fraction
2
from itertools import pairwise
3
from math import inf
4
from operator import itemgetter
5

6
Point = tuple[int, int]
7

8

9
class Solution:
10
    def minimumLines(self, prices: list[Point]) -> int:
11
        if len(prices) == 1:
12
            return 0
13
        else:
14
            prices.sort(key=itemgetter(0))
15

16
            return self.using_slope(prices)
17
            # return self.using_cross_product(prices)
18

19
    @staticmethod
20
    def using_slope(prices: list[Point]) -> int:
21
        output, slope = 1, Solution.dy_by_dx
22

23
        ab = next(pairs := pairwise(prices))
24

25
        for bc in pairs:
26
            if slope(ab) != slope(bc):
27
                output += 1
28

29
            ab = bc
30

31
        return output
32

33
    @staticmethod
34
    def dy_by_dx(ab: tuple[Point, Point]) -> float | Fraction:
35
        (x1, y1), (x2, y2) = ab
36

37
        dx, dy = x2 - x1, y2 - y1
38

39
        if dx == 0:
40
            # 1. dx is 0, it means we have a vertical line going from (x1, y1). So whether dy is positive or
41
            #    negative, it does not matter
42
            # 2. infinity can not be represented by fraction module so returning it directly from math module
43
            return inf
44
        else:
45
            # To avoid floating point error, we use fraction module.
46

47
            # (Simple divisions can give same results for example (apparently one of the test cases),
48
            # 499999998/499999999 and 499999999/500000000 gives same result, and that is where Fraction
49
            # class shines)
50
            return Fraction(dy, dx)
51

52
    @staticmethod
53
    def using_cross_product(prices: list[Point]) -> int:
54
        output, on_line = 1, Solution.lie_on_same_line
55

56
        a = next(itr := iter(prices))
57

58
        for b, c in pairwise(itr):
59
            if not on_line(a, b, c):
60
                output += 1
61

62
            a = b
63

64
        return output
65

66
    @staticmethod
67
    def lie_on_same_line(a: Point, b: Point, c: Point) -> bool:
68
        (x1, y1), (x2, y2), (x3, y3) = a, b, c
69

70
        return (y2 - y1) * (x3 - x2) == (x2 - x1) * (y3 - y2)