title: Algorithm for 2D grid problem?
body: <p>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.</p>
  
  <p>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</p>
  
  <p>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.</p>
  
  <p>What I have tried:
  - Different data structures (most are nlogn)
  - Folding the grid (again nlogn)</p>
  
  <p>Thanks in advance.</p>
  
  <p>Edit: </p>
  
  <p>My mistake, the grid is (n x n) making the number of houses n^2, sorry for the confusion.</p>
  
  <p>Edit2:</p>
  
  <p>This is the question exactly, maybe I am reading it wrong?</p>
  
  <p>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.</p>