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>& stockPrices) { int ans = 0; sort(begin(stockPrices), end(stockPrices)); for (int i = 2; i < stockPrices.size(); ++i) { const pair a = getSlope(stockPrices[i - 2], stockPrices[i - 1]); const pair b = getSlope(stockPrices[i - 1], stockPrices[i]); if (a != b) ++ans; } return ans + (stockPrices.size() > 1); } private: pair getSlope(const vector& p, const vector& 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) -> a[0] - b[0]); for (int i = 2; i < stockPrices.length; ++i) { Pair a = getSlope(stockPrices[i - 2], stockPrices[i - 1]); Pair 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 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)