Problem Statement
Given an undirected graph with V vertices and M colors, determine whether it is possible to color the graph such that:
- No two adjacent vertices have the same color.
- Only M colors are available.
Return true if possible, otherwise false.
Brute Force Intuition
For every vertex:
Try all M colors
After coloring the entire graph:
Check whether adjacent vertices have different colors
This works but explores many invalid color assignments.
Complexity
- Time Complexity: O(M^V)
- Space Complexity: O(V)
Moving Towards the Optimal Approach
Instead of coloring everything first:
For each vertex:
Try every color
Check validity immediately
If valid:
Assign Color
Recurse
Else:
Try another color
Pattern Recognition
Whenever you see:
- Assign values under constraints
- Multiple choices per position
- Need all positions valid
Think:
Backtracking + Constraint Checking
Key Observation
For every node:
Can I assign Color 1 ?
Can I assign Color 2 ?
Can I assign Color 3 ?
...
If a color conflicts with a neighbour:
Reject immediately
Optimal Java Solution
class Solution {
boolean graphColoring(int v, int[][] edges, int m) {
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for (int i = 0; i < v; i++) {
adj.add(new ArrayList<>());
}
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
int[] color = new int[v];
return solveColoring(0, adj, color, m, v);
}
private boolean solveColoring(int node,
ArrayList<ArrayList<Integer>> adj,
int[] color,
int m,
int v) {
if (node == v)
return true;
for (int c = 1; c <= m; c++) {
if (isSafe(node, c, adj, color)) {
color[node] = c;
if (solveColoring(node + 1,
adj,
color,
m,
v))
return true;
color[node] = 0;
}
}
return false;
}
private boolean isSafe(int node,
int currColor,
ArrayList<ArrayList<Integer>> adj,
int[] color) {
for (int neighbour : adj.get(node)) {
if (color[neighbour] == currColor)
return false;
}
return true;
}
}
Dry Run
0 ----- 1
| |
| |
2 ----- 3
M = 3
Coloring:
0 -> Red
1 -> Blue
2 -> Blue
3 -> Red
Valid ✅
Why Backtracking Works?
For every vertex:
Try all colors
If a color eventually causes a conflict:
Undo assignment
Try next color
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(M^V) |
| Space Complexity | O(V) |
Interview One-Liner
Color vertices one by one, trying all possible colors while ensuring no adjacent vertices share the same color.
Memory Trick
Node
↓
Try Color
↓
Safe ?
↓
Yes → Recurse
No → Next Color
![[System Design] Part 4 — Amazon CONDOR & Anticipatory Shipping](https://media2.dev.to/dynamic/image/width=1000,height=420,fit=cover,gravity=auto,format=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fcr7y22086qgqejku95th.png)
