Three-Color an Undirected Graph
Updated
Problem statement
You are given an undirected graph with n vertices numbered 0 through n - 1. Return true if you can color every vertex using at most three colors so that vertices joined by an edge have different colors. Otherwise, return false.
Each row edges[i] = [u, v] represents an undirected edge. A coloring is proper when the endpoints of every edge receive different colors. Vertices with no edge and disconnected components are allowed. The same three colors are available to every component. Vertices that are not connected by an edge may share a color.
Return only a boolean. You do not need to return a coloring or count the possible colorings. A graph using fewer than three colors is valid. The empty graph is valid. Edges have no direction even if their endpoints are listed in reverse order.
Function
canThreeColor(n: int, edges: int[][]) → booleanExamples
Example 1
n = 3edges = [[0,1],[1,2],[2,0]]return = trueA triangle can use one distinct color at each vertex. An odd cycle is not automatically a failure when a third color is available.
Example 2
n = 4edges = [[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]return = falseEvery pair of vertices is adjacent. Four mutually adjacent vertices cannot share only three available colors.
Example 3
n = 0edges = []return = trueThe empty graph has no conflicting edge and needs no colors.
Constraints
0 <= n <= 12.0 <= edges.length <= n * (n - 1) / 2.- Every edge has exactly two integer endpoints in
[0, n - 1], and its endpoints are different. - Each unordered pair of endpoints occurs at most once. No self-loops or parallel edges are present.
- The graph may be disconnected, and vertices need not appear in an edge.
More Snowflake Phone Screen questions
- Connect Four from the Last MovePHONE SCREEN · Seen Nov 2026
- Minimum Edits to a Perfect Binary TreePHONE SCREEN · Seen Nov 2026
- Configurable Per-Client Token BucketsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Find Valid SET Card TriplesOA · PHONE SCREEN · Seen Nov 2026
- Minimum Index Distance Between Person and CakeOA · PHONE SCREEN · Seen Nov 2026
- Minimum N-ary Tree Depth DeletionsOA · PHONE SCREEN · Seen Nov 2026
- Sum of Binary Tree Boundary NodesOA · PHONE SCREEN · Seen Nov 2026
- Greedy Person-Cake Matching DistancePHONE SCREEN · Seen Nov 2026
- Tree Height After Child PromotionPHONE SCREEN · Seen Oct 2026
- Minimum StackPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Visit Desired Attractions Without Reusing a TrailDuolingo · PHONE SCREENDuolingo interview questions
- Maximum Currency Conversion Along a Simple PathRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Longest Anchored Song ChainIntuit · OAIntuit interview questions
- Choose the Next Minesweeper ActionRunloop · PHONE SCREEN
- Attraction Route Without Reusing TrailsWhatNot · PHONE SCREENWhatNot interview questions
- Enumerate Directed Paths and CyclesByteDance · PHONE SCREENByteDance interview questions
- Minimum Distance Matching in a ForestScale AI · PHONE SCREEN · ONSITE INTERVIEWScale AI interview questions
- Word Ladder IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Words in Disjoint Grid PathsIndeed · PHONE SCREENIndeed interview questions
- SubsetsTemu · PHONE SCREENTemu interview questions