Solution

Method 1 – Slope Comparison with Sorting

Intuition

To minimize the number of lines, we need to count how many times the slope between consecutive points changes. If the slope remains the same, the points are collinear and can be represented by a single line.

Approach

Sort the points by day (x-coordinate).
Iterate through the sorted points and compare the slope between each pair of consecutive segments.
If the slope changes, increment the line count.
Return the total number of lines needed.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minimumLines(vector<vector<int>>& stockPrices) {\n        sort(stockPrices.begin(), stockPrices.end());\n        int n = stockPrices.size();\n        if (n <= 1) return 0;\n        int ans = 1;\n        for (int i = 2; i < n; ++i) {\n            long long x1 = stockPrices[i-2][0], y1 = stockPrices[i-2][1];\n            long long x2 = stockPrices[i-1][0], y2 = stockPrices[i-1][1];\n            long long x3 = stockPrices[i][0], y3 = stockPrices[i][1];\n            if ((y2-y1)*(x3-x2) != (y3-y2)*(x2-x1)) ans++;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minimumLines</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> stockPrices</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">        sort</span><span styl

Related Tags