Count nodes within k distance of marked nodes in grid

Question

I am attempting to solve a coding challenge however my solution is not very performant, I'm looking for advice or suggestions on how I can improve my algorithm.

The puzzle is as follows:

You are given a grid of cells that represents an orchard, each cell can be either an empty spot (0) or a fruit tree (1). A farmer wishes to know how many empty spots there are within the orchard that are within k distance from all fruit trees.

Distance is counted using taxicab geometry, for example:

k = 1

[1, 0]
[0, 0]

the answer is 2 as only the bottom right spot is >k distance from all trees.

My solution goes something like this:

1. loop over grid and store all tree positions
2. BFS from the first tree position and store all empty spots until we reach a neighbour that is beyond k distance
3. BFS from the next tree position and store the intersection of empty spots
4. Repeat step 3 until we have iterated over all tree positions
5. Return the number of empty spots remaining after all intersections

I have found that for large grids with large values of k, my algorithm becomes very slow as I end up checking every spot in the grid multiple times. After doing some research, I found some solutions for similar problems that suggest taking the two most extreme target nodes and then only comparing distance to them:

• https://www.codingninjas.com/codestudio/problem-details/count-nodes-within-k-distance_992849
• https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/

However this does not work for my challenge given certain inputs like below:

k = 4

[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
[1, 0, 0, 0]
[0, 0, 0, 0]

Using the extreme nodes approach, the bottom right empty spot is counted even though it is 5 distance away from the middle tree.

Could anyone point me towards a more efficient approach? I am still very new to these types of problems so I am finding it hard to see the next step I should take.

Answer 1

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.

Answer 2

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.

Answer 3

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;
}

Answer 4

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