algorithms – Check if there is a subset of coordinates where each coordinate in the subset is diagonal to each other

Problem Statement

Given a list of XY coordinates of length N ( e.g. ((1,2),(3,4)) ) check if there is a subset of coordinates of length S where each coordinate of this subset is diagonal to each other. More details below:

  • Coordinate A and Coordinate B are diagonal to each other if A‘s XY values are different to B‘s XY values. For example, (1,1) is diagonal to both (2,2) and (4,3), but not diagonal to (1,2)
  • I don’t need to find the specified subset of length S, I only need to say if it’s possible or not given the list N
  • If S=1, then every subset is valid.
  • N, S > 0
  • N >= S

For example, given the following list of length N=4 ((1,2), (2,2), (3,1), (4,5)), the following statements are true:

  • ((2,2), (3,1), (4,5)) is a valid subset of length S=3 where every coordinate is diagonal to each other.
  • ((2,2)) is a valid subset of length S=1.
  • ((1,2), (2,2)) is not a valid subset of length S=2.

The Issue

A brute-force approach would be to iterate through all possible subset combinations of length S until we find one that fulfills the criteria from the problem statement. In the worst case scenario when N=S, this would have a complexity of O(n!), which is way too inefficient I think.

Is there an an O(n^2) or better solution to this problem? This was a problem that a colleague came up with, so I’m not sure if this is a known problem with an efficient solution.