2280. Minimum Lines to Represent a Line Chart Medium

1/**
2 * [2280] Minimum Lines to Represent a Line Chart
3 *
4 * You are given a 2D integer array stockPrices where stockPrices[i] = [dayi, pricei] indicates the price of the stock on day dayi is pricei. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:
5 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/30/1920px-pushkin_population_historysvg.png" style="width: 500px; height: 313px;" />
6 * Return the minimum number of lines needed to represent the line chart.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/30/ex0.png" style="width: 400px; height: 400px;" />
10 * Input: stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
11 * Output: 3
12 * Explanation:
13 * The diagram above represents the input, with the X-axis representing the day and Y-axis representing the price.
14 * The following 3 lines can be drawn to represent the line chart:
15 * - Line 1 (in red) from (1,7) to (4,4) passing through (1,7), (2,6), (3,5), and (4,4).
16 * - Line 2 (in blue) from (4,4) to (5,4).
17 * - Line 3 (in green) from (5,4) to (8,1) passing through (5,4), (6,3), (7,2), and (8,1).
18 * It can be shown that it is not possible to represent the line chart using less than 3 lines.
19 *
20 * Example 2:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/30/ex1.png" style="width: 325px; height: 325px;" />
22 * Input: stockPrices = [[3,4],[1,2],[7,8],[2,3]]
23 * Output: 1
24 * Explanation:
25 * As shown in the diagram above, the line chart can be represented with a single line.
26 *
27 *  
28 * Constraints:
29 *
30 * 1 <= stockPrices.length <= 10^5
31 * stockPrices[i].length == 2
32 * 1 <= dayi, pricei <= 10^9
33 * All dayi are distinct.
34 *
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/
39// discuss: https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn minimum_lines(stock_prices: Vec<Vec<i32>>) -> i32 {
45        if stock_prices.len() < 2 {
46            return 0;
47        }
48        let mut data = stock_prices.clone();
49        data.sort();
50        let mut result = 1;
51        for i in 2..data.len() {
52            if (data[i - 2][1] - data[i - 1][1]) * (data[i - 1][0] - data[i][0])
53                != (data[i - 1][1] - data[i][1]) * (data[i - 2][0] - data[i - 1][0])
54            {
55                result += 1;
56            }
57        }
58        result
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_2280() {
70        assert_eq!(
71            Solution::minimum_lines(vec![
72                vec![1, 7],
73                vec![2, 6],
74                vec![3, 5],
75                vec![4, 4],
76                vec![5, 4],
77                vec![6, 3],
78                vec![7, 2],
79                vec![8, 1]
80            ]),
81            3
82        );
83    }
84}
85