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:
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 <= 105stockPrices[i].length == 21 <= dayi, pricei <= 109dayi are distinct.Problem Overview: You receive stock prices as [day, price] points. After sorting by day, the chart connects points with straight segments. The goal is to compute the minimum number of straight lines needed so consecutive points that share the same slope belong to the same segment.
Approach 1: Using Slopes and Collinearity (O(n log n) time, O(1) space)
First sort the points by day using a standard sorting step. Then iterate through the array and compute the slope between consecutive points. If three consecutive points are collinear, they belong to the same line segment, so you continue without increasing the line count. Instead of floating-point division, compare slopes using cross multiplication: (y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1). This avoids precision issues and relies purely on integer arithmetic from math and geometry. Every time the slope changes, increment the line counter.
Approach 2: Incremental Line Count with Direct Comparison (O(n log n) time, O(1) space)
This approach focuses on counting line segments as you traverse the sorted array. After sorting by day, start with one line segment between the first two points. For each new point, compare the slope of the last segment with the slope formed by the current pair. If the slopes differ, a new line segment must start, so increment the count. The comparison again uses cross multiplication instead of division. The logic is simple: iterate once, compute slope relationships, and maintain a running count of segments.
Recommended for interviews: The incremental slope comparison approach is typically expected. It shows you understand how to detect collinearity without floating-point errors and how sorting enables a single linear pass. Interviewers usually look for the O(n log n) solution (due to sorting) with constant extra space and integer slope comparison.
To determine the minimum number of lines needed, we can utilize the concept of slopes between two points.
The slope between two points (x1, y1) and (x2, y2) is (y2-y1)/(x2-x1).
By calculating slopes between consecutive points and checking for changes in the slope, we can count the number of distinct lines required.
This C solution sorts the given points based on the day, then calculates consecutive slopes to check if they are collinear. Using integer arithmetic to avoid precision issues with floating-point division, this implementation compares the slopes of each triplet of points to ascertain changes.
Time Complexity: O(n log n), dominated by the sorting step.
Space Complexity: O(1), as sorting is in-place.
In this approach, we directly compare consecutive points to form lines when a change in direction is detected. By storing the direction differences using primitive comparisons, we adjust and increment a line counter whenever a shift occurs in the plotting direction of consecutive stock points.
This C solution takes the approach of starting with the maximum possible lines (n-1) and reduces them as coinciding slope patterns are identified between consecutive stock prices. Uses simple subtraction and multiplication for calculations.
Time Complexity: O(n log n), dictated by the sorting requirement.
Space Complexity: O(1), as no additional space is utilized outside of input modification.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Slopes and Collinearity | Time Complexity: O(n log n), dominated by the sorting step. |
| Approach 2: Incremental Line Count with Direct Comparison | Time Complexity: O(n log n), dictated by the sorting requirement. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Slopes and Collinearity | O(n log n) | O(1) | General case when points are unsorted and you need accurate slope comparison without floating-point errors |
| Incremental Line Count with Direct Comparison | O(n log n) | O(1) | Preferred interview solution after sorting; simple linear pass and easy slope checks |
Minimum Lines to Represent a Line Chart | Leetcode 2280 | Arrays | Contest 294 🔥🔥 • Coding Decoded • 1,303 views views
Watch 9 more video solutions →Practice Minimum Lines to Represent a Line Chart with our built-in code editor and test cases.
Practice on FleetCode