Minimum Lines to Represent a Line Chart
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, then connecting adjacent points.
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
3The line chart can be represented by 3 lines: one through days 1 to 4, one from day 4 to day 5, and one through days 5 to 8; it is not possible to use fewer than 3 lines.
Example 2
Input
stockPrices = [[3,4],[1,2],[7,8],[2,3]]Output
1The points all lie on the same line after ordering by day, so the line chart can be represented with a single line.
Constraints
- 1 <= stockPrices.length <= 10^5
- stockPrices[i].length == 2
- 1 <= dayi, pricei <= 10^9
- All dayi are distinct.