CODEWITHSUNDEEP
algorithm
cirik
cirik

Reputation: 179

How to find minimum or maximum element in a matrix region?

For NxM matrix with integer values, what is the most efficient way to find minimum element for region (x1,y1) (x2,y2) where 0 <= x1<=x2 < M and 0 <= y1 <= y2 < N

We can assume that we will query different regions numerous times.

I am wondering if we can extend range minumum query methods to this question. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

Pretty straightforward solution could be use the most efficient solution of RMQ (Segment Tree) then apply it row or column wise.

Worst case complexity would be min(N,M)*log(max(N,M))

But still I believe we can do better than that.

Upvotes: 1

Views: 2536

Answers (3)

Evgeny Kluev
Evgeny Kluev

Reputation: 24647

It depends on what do you mean by "the most efficient way". It is possible to minimize query time itself, or preprocessing time, or memory requirements.

If only query time should be minimized, "the most efficient way" is to pre-compute all possible regions. Then each query is handled by returning some pre-computed value. Query time is O(1). Both memory and preprocessing time are huge: O((NM)2).

More practical is to use Sparse Table algorithm from the page referred in OP. This algorithm prepares a table of all power-of-two length intervals and uses a pair of these intervals to handle any range-minimum-query. Query time is O(1). Memory and preprocessing time are O(N log N). And this algorithm can be easily extended to two-dimensional case.

Sparse Table algorithm in 2D

Just prepare a table of all power-of-two length and power-of-two height rectangles and use four of these rectangles to handle any range-minimum-query. The result is just a minimum of four minimum values for each of these rectangles. Query time is O(1). Memory and preprocessing time are O(NM*log(N)*log(M)).

This paper: "Two-Dimensional Range Minimum Queries" by Amihood Amir, Johannes Fischer, and Moshe Lewenstein suggests how to decrease memory requirements and preprocessing time for this algorithm to almost O(MN).

This paper: "Data Structures for Range Minimum Queries in Multidimensional Arrays" by Hao Yuan and Mikhail J. Atallah gives different algorithm with O(1) query time and O(NM) memory and preprocessing time.

Upvotes: 2

Celada
Celada

Reputation: 22251

Given no other information about the contents of the matrix or about the way it's stored, it's impossible to make any suggestion besides just scanning every entry in the given region. That's O((x2-x1) * (y2-y1)). Your question is too vague to state anything else.

You could perhaps do better (probabilistically, in the average case) if you knew something else about the matrix, for example if you know that the elements are probably sorted in some way.

Upvotes: 2

Patrick87
Patrick87

Reputation: 28292

Pseudocode:

function getMax(M, x1, x2, y1, y2)
    max = M[x1,y1]
    for x = x1 to x2 do
        for y = y1 to y2 do
            if M[x,y] > max then max = M[x, y]
    return max

This is O(n) in the input size, which can only reasonable be interpreted as the size of the matrix region (x2 - x1) * (y2 - y1). If you want the minimum, change max to min and > to <. You cannot do better than O(n), i.e., checking each of the possible elements. Assume you had an algorithm that was faster than O(n). Then it doesn't check all elements. To get a failing case for the algorithm, take one of the elements it doesn't check, and replace it with (max + 1), and re-run the algorithm.

Upvotes: 0

Related Questions