Median of areas given in a matrix

user_2974674 0
Viewed 140

Given a matrix (n x n) of 1 and 0, where 1 represent land and 0 represent water. How can I find the median of the area of the lands in the most efficient way?

For Example:

1 1 0 0 0

1 0 0 1 1

1 0 1 0 0

There are three islands, the area of them [1,2,4] and the median is 2

An island can be consist of continuous non-diagonal cells which contain 1: For example:

1 0 1

0 1 0

this matrix contains three islands of areas [1,1,1]

My solution is finding recursively the areas and then sort them to find the median which takes O(n^2log(n^2)), is there a more efficient way to do that?

data-structures sorting algorithm performance
2 Answers

First step, run DFS recursively on the grid and discover all the islands & calculate areas in O(n^2) time.

Second step, You can use Median of Medians algorithm to calculate the median of unsorted island's areas array in expected O(m) time where m is the number of islands.

Overall time complexity O(n^2).

If you need further help, I can provide my implementation.

user_11622330

Using a disjoint set gives you O(A(N)), where A is inverse Ackermann function to find the Islands, then using an nth_element (aka IntroSelect) to find the N/2 in O(N) to find the median.

sets = DisjointSet(matrix)
median = nth_element(sets, N/2)

For a total of O(A(N)) far less than O(N^2)

user_40132580
Related