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.