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

Posted on Categories Articles