Title

class Solution {
    boolean[] colorInNeighbour;
    boolean graphColoring(int[][] edges, int m, int n) {
        
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(int i = 0; i < n; ++i) graph.put(i, new ArrayList<>());
 
        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
 
        int[] colors = new int[n];
        colorInNeighbour = new boolean[m];
 
        Arrays.fill(colors,-1);
        Arrays.fill(colorInNeighbour,false);
        
        for(int i = 0; i < n ; ++i) {
            if(colors[i] == -1) {
                if(!dfs(graph,colors, m, i)) return false;
            }
        }
        
        return true;
    }
 
 
    boolean dfs(Map<Integer, List<Integer>> graph, int[] color, int M, int index) {
        
        if(color[index] != -1) return true;
 
        Arrays.fill(colorInNeighbour,false);
        for(int nbr : graph.get(index)) {
            if(color[nbr] != -1) {
                colorInNeighbour[color[nbr]] = true;
            }
        }
 
        for(int i = 0; i < M; ++i) {
            if(!colorInNeighbour[i]) {
                color[index] = i;
                break;
            }
        }
 
 
        if(color[index] == -1) return false;
 
        for(int nbr : graph.get(index)) {
            if(!dfs(graph,color,M,nbr)) return false;
        }
 
        return true;
    }
}

 
---
tags:
  - cc
---
 
 
## Question
 
{Rewrite the problem clearly and concisely. Use math notation if needed.}
 
## Solution
 
### Pattern
 
**{Primary pattern}**
Short explanation
Explain in 1–2 lines.
 
### How to Identify
 
Give 3–5 bullet points explaining how to recognize this pattern in interviews.
 
- Key signals
- When to use
 
### Description
 
Explain the approach step-by-step but in reader friendly way so that a person with no idea can read it and understand
 
Step-by-step explanation:
 
- Mention constraints or invariants
- Explain decision choices
- Keep it structured and logical
- Flow
 
### The Intuition
 
Give a strong mental model or analogy or Deep reasoning::
 
- Solution choice reasoning
- Why this works
- Mental model
 
### Complexity
 
| Label            | Worst          | Average          |
| :--------------- | :------------- | :--------------- |
| Time Complexity  | ${Worst Case}$ | ${Average Case}$ |
| Space Complexity | ${Worst Case}$ | ${Average Case}$ |
 
#### Time Complexity
 
Explain clearly, not just Big-O
 
#### Space Complexity
 
Include recursion stack if applicable
 
### Code
 
Provide clean, optimal code:
 
- Prefer Java (default) unless specified
- Use best practices (no brute force unless necessary)
- Add short comments where useful
 
```java
{code_here}
```
 
## Caveats
 
Situation where this approch might not work or alternatve way would be better
 
- Limitations
- When not to use
 
## Concepts to Think About
 
Provide 5–8 deeper insights:
 
- Related formulas
- Variations or extensions
- Tradeoffs
- Common mistakes
- Performance considerations
- Patterns
- Variations
- Tradeoffs
- Mistakes
 
## Logical Follow-up
 
Give me all logical follow ups for top-tier technical interviews (Google, Meta, Uber etc.).
 
Question: {Follow-up question}
Solution: {Answer with explaination}