Weather Relay Band Check
Check whether graph nodes can be split into two edge-free groups
A weather station operates n wireless relays, numbered from 0 to n - 1. Each relay must use either the low band or the high band.
The list interference contains pairs [u, v]. Each pair means that relays u and v must use different bands. Interference is symmetric, and there are no restrictions between relays whose pair is not listed.
Return true if it is possible to assign a band to every relay while satisfying all listed restrictions. Otherwise, return false.
Relays without any interference restrictions may use either band.
Examples
Example 1
Input: n = 4, interference = [[0,1],[1,2],[2,3],[0,3]] Output: true
Relays 0 and 2 can use the low band, while relays 1 and 3 use the high band. Every listed pair then uses different bands.
Example 2
Input: n = 3, interference = [[0,1],[1,2],[0,2]] Output: false
Each of the three relays interferes with the other two. After assigning different bands to any two, neither band is available for the third.
Example 3
Input: n = 5, interference = [[0,1],[2,3]] Output: true
The two separate interfering pairs can each receive opposite bands independently. Relay 4 has no restrictions.
Constraints
- 1 <= n <= 3000
- 0 <= interference.length <= 3200
- Each element of interference is a pair [u, v] with 0 <= u < v < n.
- No pair occurs more than once.
Use an iterative traversal to avoid recursion-depth limits. An optimal solution takes O(n + interference.length) time and space.
Hints
Show hint 1Hint 1
Once a relay's band is chosen, the bands of its interfering neighbors are forced.
Show hint 2Hint 2
Explore every connected component. A contradiction occurs when an interference pair has both endpoints assigned the same band.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return a valid band assignment when one exists?
- How would you return a cycle that explains why no valid assignment exists?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem