We need to build an ordered hash table from school coordinates to the number of houses it has a student from. A school situated at $\left(10\left(\left\lfloor\frac{x}{10}\right\rfloor+i\right), 10\left(\left\lfloor\frac{y}{10}\right\rfloor+j\right)\right)$ has a student from a particular house $(x, y)$, if$\left|10\left(\left\lfloor\frac{x}{10}\rfloor+i\right) - x\right| + \left|10\left(\lfloor\frac{y}{10}\rfloor+j\right) - y\right)\right| \leq 10$, for $i, j \in \{-1, 0, 1\}$
This check is done in O(1) time.
We can build our hash table by iterating over all n houses, and for each school coordinates nearby (Manhattan Distance ≤ 10), we increment the student count of that school.
This loop takes O(n) amortized time. During this increment, we can keep track of the maximum number of students possible.
Finally, we iterate through the hash table, printing the coordinates of the school which has the maximum number of student. Since there can be at most 5 schools near each house, we'll have at most 5×n keys.
Runtime: O(n)
Common mistakes:
- A house could exist on top of a school, so we need to check 9 positions instead of 4.
- If there are multiple popular schools, you need to print all of them.
