CODEWITHSUNDEEP
algorithm
ms8
ms8

Reputation: 417

Sort rectangles according to area in O(N)

Let R1,...Rn be n axis-aligned rectangles in the plane for which the corners are points in the n×n-grid. Thus, for each rectangle Ri the four corners are points where both coordinates are integers in {1,...n}.

Now I want to sort these rectangles R1,...Rn by there increasing area in O(n) time.

I have an algorithm to sort them in O(n*log n). But how can it be done in O(n) ?

Using O(n*log n) we can do this :

Calculate all the areas, and then sort using any standard sorting algorithm like Quick sort

I guess some per-processing will be required, so that we can sort in O(n) , because we are given some pre-conditions which can help. I just want algorithm, no code required.

Upvotes: 1

Views: 1406

Answers (1)

Edward Doolittle
Edward Doolittle

Reputation: 4100

Since the keys (areas) of the rectangles are integers, the task can be completed in O(n) time using a counting sort. You know the minimum key is 0 and maximum key for the problem is n^2, so in the algorithm k=n^2+1. The algorithm completes in three passes: computing histogram, computing starting and ending indexes for each key, then copying the data to the output array, preserving order of inputs with equal keys so that the sort is stable. Each pass is O(n) so altogether the algorithm is O(n).

Example: Suppose n is 3. k is one more than the largest key that appears in the data, so that all keys fit in the range [0..k-1] inclusive, i.e., k is 10. You make a histogram h by setting up an array of 0s with index from 0 to k-1, and you fill the histogram by walking through your set of rectangles and just count them up. Say there are 2 with area 1, 5 with area 2, and 2 with area 4. h = [0, 2, 5, 0, 2, 0, 0, 0, 0, 0]. Then the starting indexes are immediately computed from the histogram as 0, 0, 2, 7, 7, 9, 9, 9, 9, 9. Any rectangle with area 0 goes into output array starting at 0. Any rectangle with area 1 goes into output array starting at 0 (and increment that number when you put a rectangle of area 1 into output). Any rectangle with area 2 goes into output array starting at 2. Any rectangle with area 3 goes into output array starting at 7. Any rectangle with area 4 goes into output array starting at 7.

Upvotes: 1

Related Questions