Minimum lines to represent a line chart

Array Math Geometry Sorting Number Theory

26.9% acceptance

Feb 25, 2026

366

534

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. Return the minimum number of lines needed to represent the line chart.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_lines(mut stock_prices: Vec<Vec<i32>>) -> i32 {
    stock_prices.sort_unstable_by_key(|p| p[0]);
    let n = stock_prices.len();
    if n <= 1 { return 0; }
    let mut lines = 1;
    for i in 1..n-1 {
      let (x0, y0) = (stock_prices[i-1][0] as i64, stock_prices[i-1][1] as i64);
      let (x1, y1) = (stock_prices[i][0] as i64, stock_prices[i][1] as i64);
      let (x2, y2) = (stock_prices[i+1][0] as i64, stock_prices[i+1][1] as i64);
      // slope1 = (y1-y0)/(x1-x0), slope2 = (y2-y1)/(x2-x1)
      // Same iff (y1-y0)*(x2-x1) == (y2-y1)*(x1-x0)
      let dy1 = (y1 - y0) as i128;
      let dx2 = (x2 - x1) as i128;
      let dy2 = (y2 - y1) as i128;
      let dx1 = (x1 - x0) as i128;
      if dy1 * dx2 != dy2 * dx1 {
        lines += 1;
      }
    }
    lines
  }
}