Minimum Lines to Represent a Line Chart

Med

#2078Time: 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.

Patterns

Math Geometry Number Theory

Algorithms

Sorting

Data structures

Array

Prompt

You are given a 2D integer array stockPrices where stockPrices[i] = [day_i, price_i] indicates the price of the stock on day day_i is price_i. 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:

Return the minimum number of lines needed to represent the line chart.

Example 1:

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:

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 <= 10⁵
stockPrices[i].length == 2
1 <= day_i, price_i <= 10⁹
All day_i are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public int minimumLines(int[][] stockPrices) {5        if (stockPrices.length <= 1) {6            return 0;7        }8 9        Arrays.sort(stockPrices, (a, b) -> Integer.compare(a[0], b[0]));10 11        if (stockPrices.length == 2) {12            return 1;13        }14 15        int lines = 1;16        17        // Calculate the initial slope using floating-point division18        double currentSlope = (double)(stockPrices[1][1] - stockPrices[0][1]) / (stockPrices[1][0] - stockPrices[0][0]);19 20        for (int i = 2; i < stockPrices.length; i++) {21            double newSlope = (double)(stockPrices[i][1] - stockPrices[i-1][1]) / (stockPrices[i][0] - stockPrices[i-1][0]);22            23            // Comparing floating-point numbers for exact equality is unreliable24            if (newSlope != currentSlope) {25                lines++;26                currentSlope = newSlope;27            }28        }29 30        return lines;31    }32}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

Handle the base case: if there are one or zero points, no lines are needed.
Sort the stockPrices array by day.
Initialize a line counter to 1 (for the first segment).
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.
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.
If the cross-products are not equal, the three points are not collinear, so we increment the line counter.

1import java.util.Arrays;2 3class Solution {4    public int minimumLines(int[][] stockPrices) {5        int n = stockPrices.length;6        if (n <= 1) {7            return 0;8        }9 10        // Sort the stock prices by day11        Arrays.sort(stockPrices, (a, b) -> Integer.compare(a[0], b[0]));12 13        int lines = 1;14        for (int i = 2; i < n; i++) {15            // Get the three consecutive points16            int[] p0 = stockPrices[i - 2];17            int[] p1 = stockPrices[i - 1];18            int[] p2 = stockPrices[i];19 20            // Calculate differences for cross-multiplication21            // (y2 - y1) * (x1 - x0) == (y1 - y0) * (x2 - x1)22            // Use long to prevent overflow, as coordinates can be up to 10^923            long x0 = p0[0], y0 = p0[1];24            long x1 = p1[0], y1 = p1[1];25            long x2 = p2[0], y2 = p2[1];26 27            long val1 = (y2 - y1) * (x1 - x0);28            long val2 = (y1 - y0) * (x2 - x1);29 30            if (val1 != val2) {31                lines++;32            }33        }34 35        return lines;36    }37}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minimumLines(int[][] stockPrices) {4    Arrays.sort(stockPrices, (a, b)->a[0] - b[0]);5    int dx = 0, dy = 1;6    int ans = 0;7    for (int i = 1; i < stockPrices.length; ++i) {8      int x = stockPrices[i - 1][0], y = stockPrices[i - 1][1];9      int x1 = stockPrices[i][0], y1 = stockPrices[i][1];10      int dx1 = x1 - x, dy1 = y1 - y;11      if (dy * dx1 != dx * dy1) {12        ++ans;13      }14      dx = dx1;15      dy = dy1;16    }17    return ans;18  }19}

1class Solution {2public:3  int minimumLines(vector<vector<int>> &stockPrices) {4    sort(stockPrices.begin(), stockPrices.end());5    int dx = 0, dy = 1;6    int ans = 0;7    for (int i = 1; i < stockPrices.size(); ++i) {8      int x = stockPrices[i - 1][0], y = stockPrices[i - 1][1];9      int x1 = stockPrices[i][0], y1 = stockPrices[i][1];10      int dx1 = x1 - x, dy1 = y1 - y;11      if ((long long)dy * dx1 != (long long)dx * dy1)12        ++ans;13      dx = dx1;14      dy = dy1;15    }16    return ans;17  }18};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem