1

I have a list of items that represents X,Y on a graph (all starts at point (0,0). example:

1. [(0,0),(0,1),(0,2),(1,2),(2,2)]
2. [(0,0),(0,1),(0,2),(1,2),(2,2),(2,1),(1,1),(0,1)]

item 2 is invalid because it intersect at point (0,1).

in order to find if intersection exists, I sort (nlogn) the list and iterate to find if 2 points are the same.

def is_intersect(points ):
    # points  [(0,0)...]
    points.sort()
    for m,u in zip(points,points[1:]):
        if m==u:
            return True
    return False

My question: is there a better way to find an intersection than the above algorithm (with space complexity O(1) no extra set or hashset)?

pylos
  • 102
  • 8
  • @trincot This is not a duplicate since the OP specifically asks for an algorithm with a space complexity of *O(1)*. – blhsing Aug 16 '22 at 09:44
  • 2
    Seems duplicate of [Find duplicates in an array, without using any extra space](https://stackoverflow.com/questions/7055508/find-duplicates-in-an-array-without-using-any-extra-space) – trincot Aug 16 '22 at 09:44
  • So an 'intersecting' list is simply one that contains the same point twice or more? I think you probably mean time complexity rather than space complexity? [Space complexity of python sort is O(n) or best case O(1)](https://stackoverflow.com/questions/48759175/what-is-the-space-complexity-of-the-python-sort) – Stuart Aug 16 '22 at 09:47
  • i updated the post. no usage of extra set or hashet – pylos Aug 16 '22 at 11:31
  • [Related](https://dl.acm.org/doi/pdf/10.5555/1496770.1496815). – n. m. could be an AI Aug 16 '22 at 12:17
  • 1
    @pylos note that your own code does use extra space, because `sorted` makes a copy of the array. If you want to sort in place without using extra space, use `points.sort()` instead of `p = sorted(points)`. – Stef Aug 16 '22 at 13:22
  • @Stef good catch. revised – pylos Aug 16 '22 at 14:33
  • @pylos sadly it still uses extra space, because `points[1:]` makes a copy, too. – Stef Aug 16 '22 at 15:12
  • I updated my code so its simpler to understand for you – S H Aug 20 '22 at 21:46

1 Answers1

0

There is an algorithm in O(n) time complexity and O(1) in memory

However it is based on the fact that the array elements are numbers, so you would need to create a function that transforms the pairs into numbers.

If the numbers are small and you know they are in a range [0,10^n). You can define the following bijection: f(x,y) = x*10^n+y
From there use one of the approaches in this post and adapt it to your needs.

Example:

def duplicate(lst):
    return 12 #implementation of the algorithm in the post
def is_intersect(points):
  n = 1 #if you don't know what n is you can find it using the log_10 of all the numbers in the list and round up the maximum value 
  n = pow(10,n)
  for i in range(len(points)):
    points[i] = points[i][0]*n+points[i][1]
  ans = duplicate(points)
  if (ans is None):
    return None
  else:
    return (ans//n,ans%10)
S H
  • 415
  • 3
  • 14
  • not sure how your answer provide a solution to the subject line. Can you improve your answer by providing some code to illustrate? O(n^2) is a big no no obviously. – pylos Aug 18 '22 at 10:12
  • I deleted that part as it is irrelevent, the article in my answer has a full explanation of the algorithm and how it works with implementations in multiple languages – S H Aug 18 '22 at 13:44
  • I also added some code for you to see, but you'll have to read the post to understand and use the algorithm – S H Aug 18 '22 at 13:57