Mark visited with a set08.01
A seen-set records which values, nodes, or states you have already touched so you do not process them again. Insert when you first commit to a visit. contains is the guard before doing the work again.
Graphs, grids, and cycles all use this. The set is extra memory Θ(visited).
worked examples
Same skill, three traces. Read all three before you try it.
01first visit - given
a = [4, 1, 9], seen starts{}- walk
4not in, insert4- result
- seen
{4}, process4
02already marked - given
a = [4, 1, 9], seen{4,1}, at4- walk
contains
4skip
- result
- do not process
4again
03empty stream - given
a = []- walk
nothing to mark
- result
- seen stays
{}
Write
For each value, if it is not in seen, insert it and process it. If it is already in seen, skip it. Print seen after each step.
markSeen(a).a is an array of integers to walk left to right.For each value, if it is not in seen, insert it and process it. If it is already in seen, skip it. Print seen after each step.
a = [4, 1, 9], seen starts {} → seen {4}, process 4.a = [4, 1, 9], seen {4,1}, at 4 → do not process 4 again.a = [] → seen stays {}.constraintsa is a list of integers and may be empty. seen starts as {} unless the example already filled it.
- Happy Number0/2 skills ready · hash sets · easyopen
- Happy Number0/2 skills ready · hash sets · easyopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.