Searching & Sorting

Painters Partition

Binary search on answer tests a possible answer, then keeps the half that can still contain the optimum.

Time

O(N log range)

Space

O(1) to O(N)

Trace Steps

Interactive Array

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Step Timeline

Code + State

1int low = minimumPossible();

2int high = maximumPossible();

3while (low <= high) {

4    int mid = low + (high - low) / 2;

5    if (can(mid)) ans = mid, high = mid - 1;

6    else low = mid + 1;

7}

What To Watch

Edit the array, then replay the trace from the beginning.

Drag numbers to create your own input order.

Each step shows active indices, ranges, variables, and the matching code line.

Use next or autoplay to watch the algorithm state evolve one decision at a time.

Loading Lab...