Code RoomMaximum nesting depth
MediumPrep Room Coding #4906

Maximum nesting depth

CodingAlgorithms & data structuresMid–Senior~25 min

A document viewer renders highlight spans as nested markup, so one span may sit wholly inside another but two spans may never partially overlap. starts and ends are parallel lists: span i marks the characters from starts[i] up to but not including ends[i], and no span ends before it starts. The spans arrive in no particular order. A span whose end equals its start marks nothing and is ignored. Two spans that touch at one boundary, where one ends exactly where the next begins, do not overlap. Two spans with identical bounds count as one sitting inside the other. Return the deepest nesting the viewer would have to render, counting a top level span as depth 1, or return -1 when some pair of spans partially overlaps so no nesting is possible. Return 0 when nothing is marked.

Implement
span_nesting_depth(starts: list[int], ends: list[int]) → int
Examples
in[[0,1,2],[9,8,3]]out3
in[[0,3],[5,8]]out-1
in[[0,5],[5,10]]out1
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 25 min
InputExpectedGot
[[0,1,2],[9,8,3]]3not run yetsample
[[0,3],[5,8]]-1not run yetsample
[[0,5],[5,10]]1not run yetsample