CODEWITHSUNDEEP
algorithm
Arek Krawczyk
Arek Krawczyk

Reputation: 441

Algorithm - find four elements in a grid that make a rectangle and their minimum is maximal

I have a n x n grid. All the grids have numbers in them. I need to find 4 points in a grid such that they make a rectangle and the smallest element among them is as big as it can be. The minimum is taken from the ends of the rectange, meaning the corner elements.

Example

1 1 1
2 1 2
3 1 4

The answer is obiously (2,1),(2,3),(3,1) and (3,3), because then the set is 2,2,3,4 and min of it is 2, and obviously we can't do better.

The only possible solution I can think of is somethow brute-forcy. For each element (n^2 of them), we check every element that could be opposite of it in a rectangle. In the example below when we check the red element, the possible element are the yellow ones.

enter image description here

Such solutions is obviously O(n^4), which is not desirable.

Anyone know a better way?

Upvotes: 2

Views: 252

Answers (1)

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

O(n3) algorithm

for row1 = 1 .. n:
    for row2 = row1 + 1 .. n:
        h = empty min heap
        for column = 1 .. n:
            x = min(grid[row1, column], grid[row2, column])
            push x to h
            if h.size > 2:
                pop h
        best = max(best, h.min)

O(n2 log n) algorithm

Unlike previous approach, this one needs O(n2) temporary space.

This algorithm is based on binary search, which works better when dealing with integer numbers in limited range. So simple preprocessing is needed to compress range of values in the grid. Sort grid cells by their value and substitute these values by indexes in sorted array. Alternatively (if there are duplicates among original values) we could assign consecutive natural numbers to each unique number in the grid (in sorted order), in this case time complexity decreases to O(n2 log U), where U is the number of unique numbers.

range = [1 .. U] (where U is maximal cell value)
binary search, stop when range is empty:
    m = range.middle
    A = empty 2D array of size n*n
    for row = 1 .. n:
        L = empty linked list
        for each column:
            if grid[row, column] >= m:
                append column to L
        for column1 = L.begin .. L.end:
            for column2 = column1.next .. L.end:
                if A[column1, column2] is empty:
                    A[column1, column2] = row
                else:
                    result = (A[column1, column2], row, column1, column2)
                    range = [m .. range.max]
                    continue binary search (found)
    range = [range.min .. m]
    continue binary search (not found)

Upvotes: 1

Related Questions