patternMinor
Check if there is a subset of coordinates where each coordinate in the subset is diagonal to each other
Viewed 0 times
thecoordinateseachdiagonalwherecoordinateotherchecksubsetthere
Problem
Problem Statement
Given a list of XY coordinates of length N ( e.g.
For example, given the following list of length N=4
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.
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.
Solution
One way to solve this optimally is to model it as a maximum cardinality matching problem in a bipartite graph whose two parts consist of the occupied rows $r_i$ and the occupied columns $c_i$, where the edge $r_ic_j$ is present whenever $(c_j, r_i)$ appears in the input. A matching in this graph having $k$ edges maps a subset of $k$ rows to $k$ distinct columns, which is the same as choosing $k$ pairwise diagonal coordinate pairs from the input. Iff the largest possible matching has at least $S$ edges, the answer is YES.
Each input coordinate pair increases the number of occupied rows and columns by at most 1 each, so there are at most $n$ occupied rows and at most $n$ occupied columns. There are just $n$ edges (thanks Inuyasha Yagami for noticing this), so solving the problem using the $O(|E|\sqrt{|V|}))$-time Hopcroft-Karp algorithm will take $O(n^{1.5})$ time.
Each input coordinate pair increases the number of occupied rows and columns by at most 1 each, so there are at most $n$ occupied rows and at most $n$ occupied columns. There are just $n$ edges (thanks Inuyasha Yagami for noticing this), so solving the problem using the $O(|E|\sqrt{|V|}))$-time Hopcroft-Karp algorithm will take $O(n^{1.5})$ time.
Context
StackExchange Computer Science Q#143711, answer score: 3
Revisions (0)
No revisions yet.