algoadvance

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Example:

Constraints:

Clarifying Questions

  1. Should we assume that the input coordinates are always correctly formed and within the stipulated range?
  2. Is consideration of numerical stability necessary for accuracy, or can we assume all operations will be within integer bounds?

Strategy

To determine if all the points lie on a straight line, we can use the concept of slope. For any two points (x1, y1) and (x2, y2), the slope m can be calculated as (y2 - y1) / (x2 - x1).

Considering the constraints and to avoid division (which can lead to precision issues), we can use cross multiplication to compare slopes instead:

For points (x1, y1), (x2, y2), and (x3, y3), their slopes:

The cross multiplication equivalent:

Code

def checkStraightLine(coordinates):
    (x0, y0), (x1, y1) = coordinates[0], coordinates[1]
    for i in range(2, len(coordinates)):
        x, y = coordinates[i]
        if (y1 - y0) * (x - x0) != (y - y0) * (x1 - x0):
            return False
    return True

# Example usage
coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
print(checkStraightLine(coordinates))  # Output: True

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of points in the coordinates list. This is because we need to iterate through each point once to check if they all lie on a straight line.

The space complexity is (O(1)) because we are using a constant amount of extra space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com