• 0

Searching for an element in a 2-d sorted array
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (2875)

You are given a 2 dimensional array of size (\( N \times N \)). Each row and column are sorted in ascending order. How would you find an element in it?


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

The algorithm works as :


  • Start from the last element of the first row ( array[0][N-1] ).
  • If the element matches with the element we are looking for, return true.
  • If the element is greater than the element we are looking for, go to the element at previous column but same row.
  • If the element is less than the element we are looking for, go to the element at next row but same column.
  • Return false if the element is not found after reaching the element at the last row of first column( array[N-1][0] ).

Running time = \( O(N) \).

public boolean FindElementIn2DArray(int[][] array, int k, int r, int c){

        int row = 0;
        int column = 0;

        while(row  <  r  & &  column >= 0){
            if(array[row][column] == k)
                return true;
            elseif(array[row][column] > k)
                column--;
            else
                row++;
        }
        return false;
}
You need to Sign In to post your solution.