All problems
Quadtree Insert Depth
Problem
Given distinct points in an n by n grid, return the maximum depth reached by recursively splitting the square into four quadrants until each square holds at most one point.
The depth of a square holding 0 or 1 points is 0; otherwise it is 1 plus the deepest child. Squares of side 1 stop splitting even if points coincide.
Hint
A square only stops splitting early when it holds at most one point or has side 1.
Test cases
case 1
in: [[[0,0],[1,1]],2]
expected: 1
case 2
in: [[[0,0]],4]
expected: 0
case 3
in: [[],4]
expected: 0
case 4
in: [[[0,0],[1,0],[2,0],[3,0]],4]
expected: 2
case 5
in: [[[0,0],[3,3],[1,2],[2,1]],4]
expected: 1
Starter codePython
def quadtree_depth(points, n):
# Your code here
pass5 test cases · run your code against them in the editor