One-Stroke Drawing
EasyAdvanced Graphs
Problem
A puzzle book shows figures made of n dots and some lines. Each lines[i] = [u, v] is a line between dots u and v (a line may start and end at the same dot, and two dots may be joined by several lines).
Return true if the figure can be traced in one stroke: a single continuous walk that uses every line exactly once, without lifting the pen. Dots may be visited several times. A figure with no lines counts as traceable.
Example 1
- Input:
- n = 4, lines = [[0,1],[1,2],[2,0],[2,3]]
- Output:
- true
Dots 2 and 3 have odd degree. Start at 3: 3 → 2 → 0 → 1 → 2.
Example 2
- Input:
- n = 4, lines = [[0,1],[0,2],[0,3]]
- Output:
- false
Four dots have odd degree; a single stroke allows at most two.
Example 3
- Input:
- n = 5, lines = [[0,1],[1,0],[3,4],[4,3]]
- Output:
- false
Every degree is even, but the lines form two separate pieces.
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ lines.length ≤ 2·10^4
- 0 ≤ u, v < n
Hint
Show the first hint
Every time the pen passes through a dot it uses two lines: one in, one out.
Walkthrough
How to approach it
01Clarify before coding
- Can dots without lines be ignored? Yes: isolated dots do not need to be visited.
- Must the stroke end where it started? No, an open path is fine.
- How does a self-loop count? It adds 2 to its dot's degree.
02Brute force
Backtrack over every possible ordering of lines from every starting dot.
Cost: Up to E! orderings: exponential, impossible for thousands of lines.
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.