Find adjacent elements in a 2D matrix

Question

I have a 2 dimensional matrix of order m *n

00 01 02 03 ....0n
10 11 12 13 ....1n
20 21 22 23 ....2n
..
m0 m1 m2  m3 ...mn

From this, given an element , i need to write a method that returns its adjacent elements. Adjacent elements are either horizontally, vertically, or diagonally adjacent.

For example, adjacent element of 01 is 00,02,10,11,12 adjacent element of 00 is 01 ,10,11 adjacent element of 11 is 00,01,02,10,12,20,21,22

Can some one help me with an optimistic algorithm to solve this?

Answer 1

public static IEnumerable<T> AdjacentElements<T>(T[,] arr, int row, int column)
{
    int rows = arr.GetLength(0);
    int columns = arr.GetLength(1);

    for (int j = row - 1; j <= row + 1; j++)
        for (int i = column - 1; i <= column + 1; i++)
            if (i >= 0 && j >= 0 && i < columns && j < rows && !(j == row && i == column))
                yield return arr[j, i];
}

...

var arr = new[,] { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };

var results = AdjacentElements(arr, 1, 3);

foreach(var result in results) 
    Console.WriteLine(result)

This yields the answer: 3 4 7 11 12 (the elements adjacent to the 8).

Answer 2

It seems elements in 2d array(be a[n][m]) are increasing horizontally and vertically . So for the given question we need to find the index of the element first. So if we can find the element in quicker way then we can optimize the solution . The question is how do we find it in efficient way. One approach is take the middle element of the matrix and check given element with it

if given element is lesser than middle element then our solution lies in matrix a[0][0] to a[n/2][m/2] because all elements to right and below are greater than middle (since given element is less than middle element) so we have reduced our search space from a[n][m] to a[n/2][m/2] which is one fourth of original size.

if given element is greater than middle element then our solution doesnt lies in matrices a[0][0] to a[n/2][m/2] because all elements to left and above are lesser than middle (since given element is greater than middle element) so our search space is total array minus a[0][0] to a[n/2][m/2] which is three-fourth of original size. Total array minus a[0][0] to a[n/2][m/2] means ,there will be three recursive call with array index

    --------->a[0][m/2](start index) to a[n/2][m](end index)  
    --------->a[n/2][0](start index) to a[n][m/2](end index)
    --------->a[n/2][m/2](start index) to a[n][m](end index)

Now recursively call the same function based on our search space.

Time complexity of our function will as follows . NOTE: In time function n represents total number of element but not no of rows as mentioned .n=(no_of_rows)*(no_of_columns)

                _________________T(n/4)  if given element is less than middle of the array.
               / 
              /
T(n)==========------------------- 1 if n=1 (if element found)
              \
               \_________________3T(n/4) if given element is greater than middle element of array

so out time function will

T(n)=3T(n/4) or T(n)=T(n/4)

In worst case T(n)=3T(n/4)
               T(n)=3{3T(n/4)}
               T(n)=3power(i)T(n/(4)poweri)     equation------> (1) 

But T(1)=1 (guessing given elemet is found in array)

so  n/(4power(i))=1
====> n=2power(2*i)
====> n=2power(2*i)

Talking log to base 2 on both sides (log[n])/2=i ====> i=log(sqrt(n))

substituting equation 1 we get T(n)=3power(log[sqrt(n)])

So after finding the element using the index we can find it neighbours . Lets say element found at a[i][j] then print

 {
a[i-1][j-1],
a[i-1][j],
a[i-1][j+1],
a[i][j-1],
a[i][j+1],
a[i+1][j-1],
a[i+1][j],
a[i+1][j+1]
}

provided

 0<i<n and 0<j<n .