# Minimum Lines to Represent a Line Chart
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart)
Canonical: https://scaleengineer.com/dsa/problems/minimum-lines-to-represent-a-line-chart
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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:

![](https://assets.glich.co/dsa/minimum-lines-to-represent-a-line-chart/image0.png) 

Return _the **minimum number of lines** needed to represent the line chart_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-lines-to-represent-a-line-chart/image1.png) 

**Input:** stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
**Output:** 3
**Explanation:**
The diagram above represents the input, with the X-axis representing the day and Y-axis representing the price.
The following 3 lines can be drawn to represent the line chart:
- Line 1 (in red) from (1,7) to (4,4) passing through (1,7), (2,6), (3,5), and (4,4).
- Line 2 (in blue) from (4,4) to (5,4).
- Line 3 (in green) from (5,4) to (8,1) passing through (5,4), (6,3), (7,2), and (8,1).
It can be shown that it is not possible to represent the line chart using less than 3 lines.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-lines-to-represent-a-line-chart/image2.png) 

**Input:** stockPrices = [[3,4],[1,2],[7,8],[2,3]]
**Output:** 1
**Explanation:**
As shown in the diagram above, the line chart can be represented with a single line.

**Constraints:**

* `1 <= stockPrices.length <= 105`
* `stockPrices[i].length == 2`
* `1 <= dayi, pricei <= 109`
* All `dayi` are **distinct**.

# Approaches
## Sorting with Floating-Point Slope Comparison
This approach involves sorting the stock prices by day and then iterating through the points to count the number of lines. It identifies new lines by comparing the slopes between consecutive segments. The slope calculation is done using floating-point division, which is intuitive but can be problematic.
**Time:** O(N log N), where N is the number of stock prices. The sorting step dominates the time complexity. The subsequent loop runs in O(N) time. · **Space:** O(log N) to O(N), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort` for object arrays uses Timsort, which requires O(N) space in the worst case.
**Pros:** Conceptually straightforward and easy to map from the geometric definition of a slope.
**Cons:** Using floating-point numbers (`double`) for slope calculation and comparison is prone to precision errors. Two slopes that should be identical might be represented by slightly different binary values, leading to incorrect comparisons.; Floating-point arithmetic can be slower than integer arithmetic.
### Explanation
The algorithm begins by handling the trivial cases where the number of points is less than two. For two or more points, the `stockPrices` array is first sorted chronologically based on the day. We initialize a line counter to 1, as at least one line is required to connect the first two points. We then calculate the slope of this initial line. The algorithm then iterates from the third point onwards, calculating the slope of the new segment (from the previous point to the current point) and comparing it with the slope of the preceding segment. If the slopes differ, it indicates a 'bend' in the chart, meaning a new line is required. We then increment our line counter and update the current slope for the next comparison. A key drawback of this method is its reliance on floating-point arithmetic (`double`), which can suffer from precision errors when comparing values for equality.
```java
import java.util.Arrays;

class Solution {
    public int minimumLines(int[][] stockPrices) {
        if (stockPrices.length <= 1) {
            return 0;
        }

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

        if (stockPrices.length == 2) {
            return 1;
        }

        int lines = 1;
        
        // Calculate the initial slope using floating-point division
        double currentSlope = (double)(stockPrices[1][1] - stockPrices[0][1]) / (stockPrices[1][0] - stockPrices[0][0]);

        for (int i = 2; i < stockPrices.length; i++) {
            double newSlope = (double)(stockPrices[i][1] - stockPrices[i-1][1]) / (stockPrices[i][0] - stockPrices[i-1][0]);
            
            // Comparing floating-point numbers for exact equality is unreliable
            if (newSlope != currentSlope) {
                lines++;
                currentSlope = newSlope;
            }
        }

        return lines;
    }
}
```
### Algorithm
- Handle base cases: If `n <= 1` points, return 0.
- Sort the `stockPrices` array by day in ascending order.
- If `n == 2`, return 1.
- Initialize `lines = 1` and `currentSlope` using the first two points.
- Iterate from the third point (`i = 2`) to the end.
- Calculate `newSlope` between point `i-1` and `i` using floating-point division.
- If `newSlope` is not equal to `currentSlope`, increment `lines` and update `currentSlope`.
- Return `lines`.

## Sorting with Integer Cross-Multiplication
This optimal approach also sorts the points by day first. However, to avoid the precision issues and potential performance overhead of floating-point arithmetic, it compares slopes using integer cross-multiplication. This method is both robust and efficient.
**Time:** O(N log N), where N is the number of stock prices. The performance is bottlenecked by the sorting step. The loop for checking slopes runs in O(N). · **Space:** O(log N) to O(N), which is the space required by the sorting algorithm. For instance, Java's `Arrays.sort` for objects (Timsort) can use up to O(N) space.
**Pros:** Numerically stable and exact, as it completely avoids floating-point arithmetic.; Generally faster than the floating-point approach due to using integer operations.; Robust against all valid inputs within the given constraints.
**Cons:** Requires awareness of potential integer overflow and the need to use a larger data type (like `long`) for intermediate calculations.
### Explanation
The algorithm's strength lies in how it checks for collinearity. Three points `(x0, y0)`, `(x1, y1)`, and `(x2, y2)` are collinear if the slope of the segment `(x0, y0)-(x1, y1)` is equal to the slope of `(x1, y1)-(x2, y2)`. Mathematically, this is `(y1 - y0) / (x1 - x0) == (y2 - y1) / (x2 - x1)`. To avoid division and floating-point numbers, we can rewrite this using cross-multiplication: `(y1 - y0) * (x2 - x1) == (y2 - y1) * (x1 - x0)`. This check can be performed entirely with integers. The algorithm proceeds as follows:
1. Handle the base case: if there are one or zero points, no lines are needed.
2. Sort the `stockPrices` array by day.
3. Initialize a line counter to 1 (for the first segment).
4. Iterate from the third point (`i = 2`) to the end. In each step, compare the slope of the line `(p_{i-2}, p_{i-1})` with the slope of `(p_{i-1}, p_i)` using the cross-multiplication technique.
5. Since the coordinates can be up to `10^9`, their differences can also be large. The product of two differences can exceed the capacity of a 32-bit integer, so we must use a 64-bit integer (`long` in Java) for the multiplication to prevent overflow.
6. If the cross-products are not equal, the three points are not collinear, so we increment the line counter.
```java
import java.util.Arrays;

class Solution {
    public int minimumLines(int[][] stockPrices) {
        int n = stockPrices.length;
        if (n <= 1) {
            return 0;
        }

        // Sort the stock prices by day
        Arrays.sort(stockPrices, (a, b) -> Integer.compare(a[0], b[0]));

        int lines = 1;
        for (int i = 2; i < n; i++) {
            // Get the three consecutive points
            int[] p0 = stockPrices[i - 2];
            int[] p1 = stockPrices[i - 1];
            int[] p2 = stockPrices[i];

            // Calculate differences for cross-multiplication
            // (y2 - y1) * (x1 - x0) == (y1 - y0) * (x2 - x1)
            // Use long to prevent overflow, as coordinates can be up to 10^9
            long x0 = p0[0], y0 = p0[1];
            long x1 = p1[0], y1 = p1[1];
            long x2 = p2[0], y2 = p2[1];

            long val1 = (y2 - y1) * (x1 - x0);
            long val2 = (y1 - y0) * (x2 - x1);

            if (val1 != val2) {
                lines++;
            }
        }

        return lines;
    }
}
```
### Algorithm
- Handle base cases: If `n <= 1` points, return 0.
- Sort the `stockPrices` array by day in ascending order.
- Initialize `lines = 1`.
- Iterate from the third point (`i = 2`) to the end.
- For each set of three consecutive points `p_{i-2}`, `p_{i-1}`, `p_i`, calculate the differences: `dx1 = p_{i-1}[0] - p_{i-2}[0]`, `dy1 = p_{i-1}[1] - p_{i-2}[1]`, `dx2 = p_i[0] - p_{i-1}[0]`, `dy2 = p_i[1] - p_{i-1}[1]`.
- Using `long` to prevent overflow, check if `dy2 * dx1 != dy1 * dx2`.
- If the cross-products are not equal, increment `lines`.
- Return `lines`.

# Solutions
### Java

```java
class Solution {
public
  int minimumLines(int[][] stockPrices) {
    Arrays.sort(stockPrices, (a, b)->a[0] - b[0]);
    int dx = 0, dy = 1;
    int ans = 0;
    for (int i = 1; i < stockPrices.length; ++i) {
      int x = stockPrices[i - 1][0], y = stockPrices[i - 1][1];
      int x1 = stockPrices[i][0], y1 = stockPrices[i][1];
      int dx1 = x1 - x, dy1 = y1 - y;
      if (dy * dx1 != dx * dy1) {
        ++ans;
      }
      dx = dx1;
      dy = dy1;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumLines(vector<vector<int>> &stockPrices) {
    sort(stockPrices.begin(), stockPrices.end());
    int dx = 0, dy = 1;
    int ans = 0;
    for (int i = 1; i < stockPrices.size(); ++i) {
      int x = stockPrices[i - 1][0], y = stockPrices[i - 1][1];
      int x1 = stockPrices[i][0], y1 = stockPrices[i][1];
      int dx1 = x1 - x, dy1 = y1 - y;
      if ((long long)dy * dx1 != (long long)dx * dy1)
        ++ans;
      dx = dx1;
      dy = dy1;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int: stockPrices . sort() dx, dy = 0, 1 ans = 0 for (x, y), (x1, y1) in pairwise(stockPrices): dx1, dy1 = x1 - x, y1 - y if dy * dx1 != dx * dy1: ans += 1 dx, dy = dx1, dy1 return ans

```