We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Lines to Represent a Line Chart

Number: 2367

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array stockPrices where each element is a pair [day, price] representing the stock's price on that day, determine the minimum number of straight line segments required to represent the line chart when the points are connected in order of increasing day. A new line segment is needed every time the slope between consecutive points changes.

Key Insights

  • Sort the stockPrices based on the day since they may be unsorted.
  • Two consecutive points form a continuous line if they maintain the same slope.
  • Instead of computing slopes with division (which may lead to precision issues), use cross multiplication on differences to check for collinearity.
  • Count segments by incrementing when the current segment's slope differs from the previous segment's slope.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the stockPrices. Space Complexity: O(n) for storing the sorted list.

Solution

Sort the stockPrices by day first. Initialize the line count as 1 (since at least one segment is needed) and use the difference between the first two points to represent the starting slope. Then, iterate over the remaining points and check if each new point is collinear with the current segment by verifying (y3 - y2) * dx equals dy * (x3 - x2) using cross multiplication. If not, increment the segment count and update the slope using the last two considered points.

Code Solutions

def minimum_lines(stockPrices):
    # Sort stock prices based on day
    stockPrices.sort(key=lambda x: x[0])
    
    # If there are less than 2 points, no line can be formed
    if len(stockPrices) < 2:
        return 0
    
    # Start with first line segment using the first two points
    num_lines = 1
    x1, y1 = stockPrices[0]
    x2, y2 = stockPrices[1]
    dx = x2 - x1
    dy = y2 - y1
    
    # Iterate over the rest of the points
    for i in range(2, len(stockPrices)):
        x3, y3 = stockPrices[i]
        # Check collinearity using cross multiplication
        if (y3 - y2) * dx != dy * (x3 - x2):
            num_lines += 1  # New line segment needed
            dx = x3 - x2
            dy = y3 - y2
        # Update the last point in the current segment
        x2, y2 = x3, y3
    
    return num_lines

# Example test
print(minimum_lines([[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]))
← Back to All Questions