Same or Different Rules
MediumGraphs
Problem
A configuration validator receives rules about named variables. Each rule is [x, op, y] where op is either "same" (x and y must hold equal values) or "diff" (x and y must hold different values). Variables can take any value, and there are infinitely many values available.
Return true if all rules can be satisfied at once, and false otherwise.
Example 1
- Input:
- rules = [["temp", "same", "heat"], ["heat", "same", "warm"], ["temp", "diff", "warm"]]
- Output:
- false
temp equals heat equals warm, so temp cannot differ from warm.
Example 2
- Input:
- rules = [["a", "same", "b"], ["b", "diff", "c"]]
- Output:
- true
a = b = 1 and c = 2.
Example 3
- Input:
- rules = [["x", "diff", "x"]]
- Output:
- false
A variable cannot differ from itself.
Constraints
- 1 ≤ rules.length ≤ 10^4
- Variable names are 1–20 lowercase letters or digits.
- op is "same" or "diff".
Hint
Show the first hint
Equality is transitive; inequality is not. Which kind of rule creates groups?
Walkthrough
How to approach it
01Clarify before coding
- Is the number of distinct values limited? No, so 'diff' rules never conflict with each other: a ≠ b, b ≠ c, a ≠ c is fine.
- Can a rule mention the same variable twice? Yes; 'x diff x' is immediately impossible.
- Does rule order matter? No, all rules must hold simultaneously.
02Brute force
Try assigning values from 1..V to the V variables in every combination and test all rules.
Cost: V^V assignments: hopeless beyond a handful of variables.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.