Find elements surrounding an element in an array

Question

I have a multidimensional array, I want to get the elements surrounding a particular element in that array.

For example if I have the following:

[[1,2,3,4,5,6]
 [8,9,7,5,2,6]
 [1,6,8,7,5,8]
 [2,7,9,5,4,3]
 [9,6,7,5,2,1]
 [4,7,5,2,1,3]]

How do I find all the 8 elements around any of the above elements? And how do I take care of elements at the edges?

One way I figured out is, to write a 9 line code for this , which is obvious, but is there a better solution?

Answer 1

You can use 'direction array' in form

[[-1,-1], [-1,0],[1,0]..and so on]

And method which takes point coordinate and iterates through direction array -> add direction numbers to coordinates, check indexes are not out of bounds and collect results. Something like this:

private static int[][] directions = new int[][]{{-1,-1}, {-1,0}, {-1,1},  {0,1}, {1,1},  {1,0},  {1,-1},  {0, -1}};

static List<Integer> getSurroundings(int[][] matrix, int x, int y){
    List<Integer> res = new ArrayList<Integer>();
    for (int[] direction : directions) {
        int cx = x + direction[0];
        int cy = y + direction[1];
        if(cy >=0 && cy < matrix.length)
            if(cx >= 0 && cx < matrix[cy].length)
                res.add(matrix[cy][cx]);
    }
    return res;
}

Answer 2

For (i, j) ->

              (i - 1, j - 1)
              (i - 1, j)
              (i - 1, j + 1)

              (i, j - 1)
              (i, j + 1)

              (i + 1, j - 1)
              (i + 1, j)
              (i + 1, j + 1)

Now, at the edges, you can check for num % row == 0, then its at row edge... and , num % col == 0 then its column edge..

Here's is how you can proceed: -

Given an index (i, j).. You can find elements in a rows adjacent to j for i - 1, then i, and then i + 1. (NOTE : - for index i you just have to access j - 1, and j + 1)

Subsequently you also can check for the row edge and column edge..

Here, you can look at the code below, how it can happen: -

    // Array size
    int row = 6;
    int col = 6;
    // Indices of concern
    int i = 4;
    int j = 5;

    // To the left of current Column
    int index = i - 1;
    for (int k = -1; k < 2; k++) {
        if (index % row > 0 && ((j + k)  % col) > 0) {
            System.out.println(arr[index][j + k]);
        }
    }


    // In the current Column
    index = i;

    // Increment is 2 as we don't want (i, j)
    for (int k = -1; k < 2; k = k + 2) {            
        if (index % row > 0 && ((j + k)  % col) > 0) {
            System.out.println(arr[index][j + k]);
        }
    }

    // To the right of current Column
    index = i + 1;
    for (int k = -1; k < 2; k++) {
        if (index % row > 0 && ((j + k)  % col) > 0) {
            System.out.println(arr[index][j + k]);
        }

    }

UPDATE : - The above code can further be simplified.. But I leave that task to you.. HINT: - You can reduce one for loop from there..

Answer 3

for (i = 0; i < array.length; i++) {
            for (j = 0; j < array[i].length; j++) {
                for (x = Math.max(0, i - 1); x <= Math.min(i + 1, array.length); x++) {
                    for (y = Math.max(0, j - 1); y <= Math.min(j + 1,
                            array[i].length); y++) {
                        if (x >= 0 && y >= 0 && x < array.length
                                && y < array[i].length) {
                            if(x!=i || y!=j){
                            System.out.print(array[x][y] + " ");
                            }
                        }
                    }
                }
                System.out.println("\n");
            }
        }

Thanks to all the people who have answered, but i figured it out with the help of this post which i found just now, and above is the solution. thanks again :)

Answer 4

Base case is just to obtain neighbour elements by indexing shifting. For (i,j) it will be (i + 1, j), (i - 1, j), etc.

On the edges I use two approaches:

1. Modulo % operator to avoid IndexOutOfBounds exception, but it sometimes confuse with wrong elements indexation.
2. Wrap your matrix with one layer of default elements. It adds some extraspace for holding matrices, but makes your code more readable without catching exception, lot ifs and so on. This trick often used when representation maze as matrix.

Example: your default element is 0.

0 0 0 0 0 0
0 1 2 3 4 0
0 2 6 7 3 0
0 1 3 5 7 0
0 2 4 6 2 0
0 0 0 0 0 0

Note: do not forget iterate through actual array size, not extended.

Answer 5

This is my solution for your problem written in Ruby. Instead of calculating if element is at edge you could access elements "over" the edge and handle "nil" values or exceptions that happen there. Then remove "nil" values from final list. This solution is not as good as calculating if some "point" is over the edge or not.

big_map = [[1,2,3,4,5,6],
           [8,9,7,5,2,6],
           [1,6,8,7,5,8],
           [2,7,9,5,4,3],
           [9,6,7,5,2,1],
           [4,7,5,2,1,3]]

# monkey patch classes to return nil.
[NilClass, Array].each do |klass|
    klass.class_eval do
        def [](index)
            return nil if index < 0 or index > self.size rescue nil
            self.fetch(index) rescue nil
        end
    end
end

class Array

    # calculate near values and remove nils with #compact method.   
    def near(i,j)
        [ self[i - 1][j - 1], self[i - 1][j - 0], self[i - 1][j + 1],
          self[i - 0][j - 1],                     self[i - 0][j + 1],
          self[i + 1][j - 1], self[i + 1][j - 0], self[i + 1][j + 1],
        ].compact
    end
end

puts big_map.near(1,1).inspect
# => [1, 2, 3, 8, 7, 1, 6, 8]

puts big_map.near(0,0).inspect
# => [2, 8, 9]

puts big_map.near(5,5).inspect
# => [2, 1, 1]

Answer 6

I was working on he same problem and came up with a small optimized solution to find the surrounding numbers of any point in a 2D matrix, hope this helps, please comment if I can shorten the logic somehow Code:-

import java.util.ArrayList;

public class test {
    public static void main(String[] arg){

        int[][] arr = {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
        //int[][] arr = {{width,2,3},{4,5,6},{7,8,9}};
        ArrayList<Integer> al = new ArrayList<Integer>();
        int x = 2, y = 2;
        int width = 2; //change the value of width, according to the requirement 
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                if( (i == (x-width) && ( (y+width) >= j && j >= (y-width))) || (i == (x+width) && ( (y+width) >= j && j >= (y-width))) || (j == (y-width) && ( (x+width) >= i && i >= (x-width))) || (j == (y+width) && ( (x+width) >= i && i >= (x-width)))  ){
                    //if( x >= 0 && i < (i+width) && y >= 0 && j < (j+width))
                        {
                        al.add(arr[i][j]);
                        }
                }
            }
        }
        System.out.println(al);
    }

}

Answer 7

You didnt mention if you want cyclical neighbours for edges or ignores cyclical neighbours. Assuming you want cyclical neighbours here is the code,

List<Integer> getNeighbours(int[][] mat, int x, int y){
  List<Integer> ret = new ArrayList<Integer>();
  int rows = mat.length;
  int cols = mat[0].length;
  for(int i=-1,i<=1;i++)
    for(int j=-1;j<=1;j++)
      if(i||j) ret = ret.add(mat[(x+i)%rows][(y+j)%cols]);
  return ret;
}

Answer 8

(x-1, y-1) -> upper left
(x-1, y) -> left
(x-1, y+1) -> lower left

---

(x, y+1) -> up
(x, y) -> current position
(x, y-1) -> down

---

(x+1, y+1) -> upper right
(x+1, y) -> right
(x+1, y-1) -> lower right

You can use this as guide. Now all you need to do is add them in a try catch.

 for( int x=0; x<arr.length; x++ ){
  for(int y=0; y<arr[x].length; y++){
  if( arr[x][y] == 8 ){
    try{
      System.out.println("Upper Left is: " + arr[x-1][y-1]);
    }catch(ArrayIndexOutOfBoundsException e){
     //do something
    }


    try{
      System.out.println("Left is: " + arr[x-1][y]);
    }catch(ArrayIndexOutOfBoundsException e){
     //do something
    }

    //.....and others
   }
  }