Algorithm for 2D grid problem?

Question

Hello everyone,

I will be honest, this is an assignment question but I just cant find a solution to it. Please remember I am not asking for the answer but simply some guidance.

Problem: Design an algorithm that runs in O(n) time (linear) which can locate a single suspicious house (point) on a 2D grid. It is suspicious if it consumes equal or greater to the electrical consumption of its two vertical and two horizontal neighbors. Note: just wants one suspicious house to be returned

Solution: Not even sure how to achieve such a solution. If you check n houses you also can check its four surrounding neighbors. 4n/n^2 which simplifies to 4/n. Meaning that as the grid expands it is less likely to find a suspicious house.

What I have tried: - Different data structures (most are nlogn) - Folding the grid (again nlogn)

Thanks in advance.

Edit:

My mistake, the grid is (n x n) making the number of houses n^2, sorry for the confusion.

Edit2:

This is the question exactly, maybe I am reading it wrong?

The police are looking for houses which have particularly large elec- tricity consumption. To simplify the problem, imagine that they are investigating houses which are laid out on an n×n grid. Each house on the grid has some electricity consumption, e(i, j). The police consider the house suspicious if it has electricity consumption equal to or greater than each of its vertical and horizontal neighbours. Design an algorithm that runs in O(n) time and returns the location of a suspicious house.

Answer 1

You are basically looking for a house whose electricity use is a local maximum. You can find one of those by starting at an arbitrary house and stepping to an adjacent house if its electricity use is higher (repeat until no adjacent house is higher).

This will take O(n) time on an n x n grid.

Edit: commenters are right, this could take O(n^2) time in the worst case.

Answer 2

The local optima solution presented by Keith will not actually run in linear time. The problem is that it cannot guarantee that the path length is O(n).

However, consider what would happen if you looked at all of the houses in the middle row and column. Particular consider how you could use that in that to help your local optima solution.

(Complete solution not provided because, well, its an assignment) Nevertheless, a really neat problem. Kudos to its creator.

[EDIT: A hint]

The previously offered solution fails in cases like this:

X.XXX.XXX.X
X.X.X.X.X.X
X.X.X.X.X.X
X.X.X.X.X.X
XXX.XXX.XXX

where . is a really small electrical usage and and the x's are slowly increasing electrical usage.

What happens if we query the middle row?

X.XXX.XXX.X
X.X.X.X.X.X
&&&&&&&&&&&
X.X.X.X.X.X
XXX.XXX.XXX

Where the & is the houses we looked at. We've managed to slice through the path. If we were to start our hill climbing at the best point we found, we'd be able to avoid the long path. (But we still cannot guarantee the path is short enough)

[EDIT: A second hint]

Scan the middle row as mentioned. Take the largest value. Move up or down to a larger value (if you can't then that grid cell is a local optima and you are done). Now consider a path of increasing values. There is no way that path can cross that middle row again because all values in that row must be less then then the current cell. (Because the current cell must be larget then the largest of the values in the row). This means that we have essentially reduced the problem in half.