Count nodes within k distance of marked nodes in grid

There is a simple, linear time solution to this problem because of the grid and distance structure. Given a fruit tree with coordinates (a, b), consider the 4 diagonal lines bounding the box of distance k around it. The diagonals going down and to the right have a constant value of x + y, while the diagonals going down and to the left have a constant value of x - y.

A point (x, y) is inside the box (and therefore, within distance k of (a, b)) if and only if:

1. a + b - k <= x + y <= a + b + k, and
2. a - b - k <= x - y <= a - b + k

So we can iterate over our fruit trees (a, b) to find four numbers:

• first_max = max(a + b - k); first_min = min(a + b + k);
• second_max = max(a - b - k); second_min = min(a - b + k);

where min and max are taken over all fruit trees. Then, iterate over empty cells (or do some math and subtract fruit tree counts, if your grid is enormous), counting how many empty spots (x,y) satisfy

1. first_max <= x + y <= first_min, and
2. second_max <= x - y <= second_min.

This Python code (written in a procedural style) illustrates this idea. Each diagonal of each bounding box cuts off exactly half of the plane, so this is equivalent to intersection of parallel half planes:

fruit_trees = [(a, b) for a in range(len(grid))
                      for b in range(len(grid[0]))
                      if grid[a][b] == 1]

northwest_half_plane = -infinity
southeast_half_plane = infinity

southwest_half_plane = -infinity
northeast_half_plane = infinity

for a, b in fruit_trees:
    northwest_half_plane = max(northwest_half_plane, a - b - k)
    southeast_half_plane = min(southeast_half_plane, a - b + k)

    southwest_half_plane = max(southwest_half_plane, a + b - k)
    northeast_half_plane = min(northeast_half_plane, a + b + k)

count = 0
for x in range(len(grid)):
    for y in range(len(grid[0])):
        if grid[x][y] == 0:
            if (northwest_half_plane <= x - y <= southeast_half_plane
            and southwest_half_plane <= x + y <= northeast_half_plane):
                count += 1

print(count)

Some notes on the code: Technically the array coordinates are a quarter-turn rotated from the Cartesian coordinates of the picture, but that is immaterial here. The code is left deliberately bereft of certain 'optimizations' which may seem obvious, for two reasons: 1. The best optimization depends on the input format of fruit trees and the grid, and 2. The solution, while being simple in concept and simple to read, is not simple to get right while writing, and it's important that the code be 'obviously correct'. Things like 'exit early and return 0 if a lower bound exceeds an upper bound' can be added later if the performance is necessary.

As Answered by @kcsquared ,Providing an implementation in JAVA

public int solutionGrid(int K, int [][]A){
    int m=A.length;
    int n=A[0].length;
    int k=K;

    //to store the house coordinates
    Set<String> houses=new HashSet<>();

    //Find the house and store the coordinates
    for(int i=0;i<m;i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j] == 1) {
                houses.add(i + "&" + j);
            }
        }
    }
    int northwest_half_plane =  Integer.MIN_VALUE;
    int southeast_half_plane =  Integer.MAX_VALUE;

    int southwest_half_plane = Integer.MIN_VALUE;
    int northeast_half_plane = Integer.MAX_VALUE;

    for(String ele:houses){
        String arr[]=ele.split("&");
        int a=Integer.valueOf(arr[0]);
        int b=Integer.valueOf(arr[1]);
        northwest_half_plane = Math.max(northwest_half_plane, a - b - k);
        southeast_half_plane = Math.min(southeast_half_plane, a - b + k);

        southwest_half_plane = Math.max(southwest_half_plane, a + b - k);
        northeast_half_plane = Math.min(northeast_half_plane, a + b + k);
    }
    int count = 0;
    for(int x=0;x<m;x++) {
        for (int y = 0; y < n; y++) {
            if (A[x][y] == 0){
                if ((northwest_half_plane <= x - y &&  x - y <= southeast_half_plane)
                && southwest_half_plane <= x + y &&  x + y <= northeast_half_plane){
                    count += 1;
                }

            }
        }
    }
    return count;
}

This wouldn't be easy to implement but could be sublinear for many cases, and at most linear. Consider representing the perimeter of each tree as four corners (they mark a square rotated 45 degrees). For each tree compute it's perimeter intersection with the current intersection. The difficulty comes with managing the corners of the intersection, which could include more than one point because of the diagonal alignments. Run inside the final intersection to count how many empty spots are within it.

Since you are using taxicab distance, BFS is unneccesary. You can compute the distance between an empty spot and a tree directly.

This algorithm is based on a suggestion by https://stackoverflow.com/users/3080723/stef

// select tree near top left corner
SET flag false
LOOP r over rows
  LOOP c over columns
     IF tree at c, r
         SET t to tree at c,r
         SET flag true
         BREAK
  IF flag
     BREAK   
LOOP s over empty spots
  Calculate distance between s and t
  IF distance <= k
     ADD s to spotlist
LOOP s over spotlist
  LOOP t over trees, starting at bottom right corner
     Calculate distance between s and t
     IF distance > k
         REMOVE s from spotlist
         BREAK
RETURN spotlist