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.
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.