Given a 2D input matrix with non negative values, consider the subgroupings as all positive values surrounded by zeroes eg:
________
|001003|
|002304|
--------
(1,2,3) and (3,4) are groupings. A matrix with all positive values is a single grouping, an empty matrix has group value 0.
The idea is to approach this as a graph walk where each point in the matrix is a node; therefore we can walk the full matrix and every time we encounter a positive value, we start searching for and queuing all contiguous values that are part of the same group and keep summing them up while marking the positions as visited.
When we cannot move anymore (queue is empty), we update, if necessary, the current max result and keep walking the matrix. Since we mark the nodes as visited, we will not process each point more than once so the total runtime is O(MxN) and total space is also in O(MxN) because at most we queue the full matrix.
Since we are adding points to a queue for later processing, we have to be very careful of the double processing possibility; this means that we have to mark each point we add as visited immediately after it is added and use a Point auxiliary structure so that we can store the data for later processing. If we skip this, we might enqueue the point for processing twice and change its value in between to mark it as visited!
As bonus, this logic scales well to higher dimensional matrices, what needs to be adjusted is the looping and queuing logic to accommodate the extra dimensions.
You can check the implementation on my Gist along with the definition of the Point class and some test cases.
No comments:
Post a Comment
With great power comes great responsibility