Minimum Lines to Represent a Line Chart — Problem & Solution
Minimum Lines to Represent a Line Chart solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Lines to Represent a Line Chart is a medium coding problem on arrays, math and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Sorting, Geometry
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
stockPrices[i] = [day_i, price_i] says a stock closed at price_i on day_i. The points are given in no particular order, and every day appears at most once.
A line chart is drawn by plotting the points on a plane and joining each point to the next one in order of day with a straight segment. Consecutive segments that lie on the same straight line can be drawn as one line.
Return the minimum number of lines needed to draw the chart. A single point needs 0 lines.
Example 1
Input: stockPrices = [[2,10],[4,6],[1,12],[3,8],[6,8],[5,7]]
Output: 2
Explanation: Sorted by day the prices fall by 2 per day up to day 4, then rise by 1 per day: two lines.
Example 2
Input: stockPrices = [[5,3]]
Output: 0
Example 3
Input: stockPrices = [[10,4],[20,9],[40,19]]
Output: 1
Explanation: Both segments have slope 1/2.
Constraints
1 <= stockPrices.length <= 10^5stockPrices[i].length == 21 <= day_i, price_i <= 10^9All day_i are distinct
Hints for Minimum Lines to Represent a Line Chart
Hint 1
Sort the points by day first; the chart joins neighbours in that order.
Hint 2
A new line starts exactly where the slope between consecutive points changes.
Hint 3
Comparing slopes as floating-point numbers fails for huge coordinates. Compare them exactly — reduce each slope
dy/dxbygcd(|dy|, dx), or cross-multiply in a type wide enough for10^18.
How to solve Minimum Lines to Represent a Line Chart
After sorting by day, the chart is a polyline, and the number of lines is the number of segments minus the number of joints where the slope stays the same. The only subtlety is comparing slopes exactly.
Approach
- If there is one point, return 0.
- Sort the points by day.
- For each consecutive pair compute
dx > 0anddy, and reduce both byg = gcd(|dy|, dx)so every slope has one canonical form. - Count the first segment as a line, then add one more every time a segment's reduced
(dx, dy)differs from the previous segment's.
Why it works
Two consecutive segments share their middle point, so they lie on one line exactly when their slopes are equal. Since dx is positive, the reduced fraction (dy/g, dx/g) is a unique representation of the slope, so equal pairs mean equal slopes and different pairs mean different slopes — no rounding is involved.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Slopes like
499999998/499999999and499999997/499999998differ by about4e-18; doubles call them equal. - Cross-multiplying needs 64-bit integers — the products reach
10^18(and JavaScript numbers lose precision beyond2^53, so reduce by the gcd there). - With one point the answer is 0, not 1.
Reference solution
Python
from typing import List
from math import gcd
def minimumLines(stockPrices: List[List[int]]) -> int:
p = sorted(stockPrices, key=lambda x: x[0])
n = len(p)
if n < 2:
return 0
lines = 0
prev = None
for i in range(1, n):
dx = p[i][0] - p[i - 1][0]
dy = p[i][1] - p[i - 1][1]
g = gcd(abs(dy), dx)
cur = (dx // g, dy // g)
if cur != prev:
lines += 1
prev = cur
return linesJava
static int gcdLines(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
public static int minimumLines(int[][] stockPrices) {
int n = stockPrices.length;
if (n < 2) return 0;
int[][] p = stockPrices.clone();
Arrays.sort(p, (a, b) -> Integer.compare(a[0], b[0]));
int lines = 0, pdx = 0, pdy = 0;
for (int i = 1; i < n; i++) {
int dx = p[i][0] - p[i - 1][0];
int dy = p[i][1] - p[i - 1][1];
int g = gcdLines(Math.abs(dy), dx);
dx /= g;
dy /= g;
if (i == 1 || dx != pdx || dy != pdy) lines++;
pdx = dx;
pdy = dy;
}
return lines;
}C++
static int gcdLines(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
int minimumLines(vector<vector<int>>& stockPrices) {
int n = stockPrices.size();
if (n < 2) return 0;
vector<vector<int>> p(stockPrices.begin(), stockPrices.end());
sort(p.begin(), p.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
int lines = 0, pdx = 0, pdy = 0;
for (int i = 1; i < n; i++) {
int dx = p[i][0] - p[i - 1][0];
int dy = p[i][1] - p[i - 1][1];
int g = gcdLines(dy < 0 ? -dy : dy, dx);
dx /= g;
dy /= g;
if (i == 1 || dx != pdx || dy != pdy) lines++;
pdx = dx;
pdy = dy;
}
return lines;
}JavaScript
var minimumLines = function(stockPrices) {
var p = stockPrices.slice().sort(function(a, b) { return a[0] - b[0]; });
var n = p.length;
if (n < 2) return 0;
var gcd = function(a, b) {
while (b !== 0) { var t = a % b; a = b; b = t; }
return a;
};
var lines = 0, pdx = 0, pdy = 0;
for (var i = 1; i < n; i++) {
var dx = p[i][0] - p[i - 1][0];
var dy = p[i][1] - p[i - 1][1];
var g = gcd(Math.abs(dy), dx);
dx /= g;
dy /= g;
if (i === 1 || dx !== pdx || dy !== pdy) lines++;
pdx = dx;
pdy = dy;
}
return lines;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms