CODEWITHSUNDEEP
algorithmbig-o
Marcus Lind
Marcus Lind

Reputation: 11430

Fastest way to calculate how many straight lines required to intersect points?

I was doing a coding interview and even though I was able to solve it, I got low score on the performance and I thought I'd asked for improvements.

Question:

Input is array of points on a graph. E.g [(-1, -2), (1, 2), (2, 4), (2, 3)]

From point (0, 0), how many straight lines do you need to draw to intersect all points?

Solution:

I solved this in O(n) by looping through all points and storing the ratio in a set, then returning the number of items in the set. So for example, (1, 2) and (2, 4) have the same ratio, so a single line can pass through them.

How would you solve this in a faster way than O(n)?

My Code:

def countRays(points):
  positiveRatios = set()
  negativeRatios = set()
  for point in points:
    x, y = point
    if x < 0 or y < 0:
      symbol = "-"
    else:
      symbol = "+"

    ratios = positiveRatios if x >= 0 else negativeRatios
    if x == 0:
      ratios.add( (symbol, 1,) )
    else:
      ratios.add( (symbol, y/x,) )
  return len(positiveRatios) + len(negativeRatios)

Upvotes: 1

Views: 61

Answers (1)

Henry
Henry

Reputation: 43728

This cannot be solved faster than O(n). Each point can give rise to a new line so you have to look at each one at least once.

Upvotes: 2

Related Questions