Skip to content

2280. Minimum Lines to Represent a Line Chart 👎

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int minimumLines(vector<vector<int>>& stockPrices) {
    int ans = 0;

    ranges::sort(stockPrices);

    for (int i = 2; i < stockPrices.size(); ++i) {
      const pair<int, int> a = getSlope(stockPrices[i - 2], stockPrices[i - 1]);
      const pair<int, int> b = getSlope(stockPrices[i - 1], stockPrices[i]);
      if (a != b)
        ++ans;
    }

    return ans + (stockPrices.size() > 1);
  }

 private:
  pair<int, int> getSlope(const vector<int>& p, const vector<int>& q) {
    const int dx = p[0] - q[0];
    const int dy = p[1] - q[1];
    if (dx == 0)
      return {0, p[0]};
    if (dy == 0)
      return {p[1], 0};
    const int d = __gcd(dx, dy);
    return {dx / d, dy / d};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int minimumLines(int[][] stockPrices) {
    int ans = 0;

    Arrays.sort(stockPrices, (a, b) -> Integer.compare(a[0], b[0]));

    for (int i = 2; i < stockPrices.length; ++i) {
      Pair<Integer, Integer> a = getSlope(stockPrices[i - 2], stockPrices[i - 1]);
      Pair<Integer, Integer> b = getSlope(stockPrices[i - 1], stockPrices[i]);
      if (a.getKey() != b.getKey() || a.getValue() != b.getValue())
        ++ans;
    }

    return ans + (stockPrices.length > 1 ? 1 : 0);
  }

  private Pair<Integer, Integer> getSlope(int[] p, int[] q) {
    final int dx = p[0] - q[0];
    final int dy = p[1] - q[1];
    if (dx == 0)
      return new Pair<>(0, p[0]);
    if (dy == 0)
      return new Pair<>(p[1], 0);
    final int d = gcd(dx, dy);
    return new Pair<>(dx / d, dy / d);
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def minimumLines(self, stockPrices: list[list[int]]) -> int:
    ans = 0

    stockPrices.sort()

    def getSlope(p: list[int], q: list[int]) -> tuple[int, int]:
      dx = p[0] - q[0]
      dy = p[1] - q[1]
      if dx == 0:
        return (0, p[0])
      if dy == 0:
        return (p[1], 0)
      d = gcd(dx, dy)
      return (dx // d, dy // d)

    for i in range(2, len(stockPrices)):
      a = getSlope(stockPrices[i - 2], stockPrices[i - 1])
      b = getSlope(stockPrices[i - 1], stockPrices[i])
      if a != b:
        ans += 1

    return ans + (len(stockPrices) > 1)