You are given an arraylist of N coordinates or "spots" (Xi, Yi).
You can imagine all these points are placed on an infinitely large 2d array, where if the coordinate pair is given in the input arraylist, it is marked as 1, else it is 0.

You need to return an ArrayList of coordinates, where the coordinate pair at each index corresponds to the closest free element (marked 0) to the coordinate pair in the input arraylist.

Eg -

Input = [[0,3], [1,2], [2,2], [2,3], [3,2]]

This input can be visualised as - 
[ 0, 0, 0, 1
  0, 0, 1, 0
  0, 0, 1, 1
  0, 0, 1, 0]
  
Possible Outputs - [[0,2], [0,2], [2,1], [1,3], [3,2]] 
				or [[0,2], [1,1], [2,1], [2,4], [4,2]]
(Note that the matrix is actually infinitely large, so all out of bound indexes are actually 0)
There can be multiple closest coordinates for a given pair, any of them are considered a valid output

I gave a DFS approach as my first answer but it was of exponential time complexity so the interviewer was not happy.
I finally coded an O(n^3) approach, still he wasn't very happy.

He asked me to think of a linear approach.

• I started out by saying that for every element in the input array, I will do 4 operations - add/subtract 1 from the x coordinate, and add/subtract 1 from the y coordinate. If this new pair is not found in the input arraylist, that means there is one free element near my original coordinate.
• I am unsure of how to deal with cases in which my coordinate is completely surrounded by more occupied coordinates. Repeating the same process for all occupied candidates will not be linear right?

Any idea on how to solve this linearly?