I am getting array index out of bound on leetcode

Question

I am trying to solve a problem :

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

Input: matrix =

[

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 3

Output: true

The code that I have written is :

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i,j;
        for(i = 0; i < m; i++)
        {
            if(target >= matrix[i][0] && target <= matrix[i][n-1])
            {
              break;  
            }
        }

       for(j = 0; j < n; j++)
       {
           if(matrix[i][j] == target)
           {
               return true;
           }
       }

        return false;
    }

}

I am getting this error :

   Runtime Error Message:
   Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
   at Solution.searchMatrix(Solution.java:4)
   at __DriverSolution__.__helper__(__Driver__.java:8)
   at __Driver__.main(__Driver__.java:54)
   Last executed input:
   []
   0

Since the index is zero, I have to conclude your array is empty. — rghome, Aug 03 '18 at 07:40

Zabuzard · Answer 1 · 2018-08-03T07:58:01.723

Your code does not account for the following two edge cases:

The passed array is empty. In that case the array has no index 0 and your access matrix[0].length fails. That's why you get the exception.
The passed array does not contain the element. In which case the second loop will throw an IndexOutOfBoundsException because i == m and matrix[i][j] == target is out of bounds then.

You can easily fix both of them:

public static boolean searchMatrix(int[][] matrix, int target) {
    // Matrix empty, can not find element
    if (matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

    int m = matrix.length;
    int n = matrix[0].length;

    // Search row
    int targetRow = -1;
    for (int i = 0; i < m; i++) {
        if (target >= matrix[i][0] && target <= matrix[i][n - 1]) {
          targetRow = i;
          break;
        }
    }

   // No row found
   if (targetRow == -1) {
       return false;
   }

   for (int j = 0; j < n; j++) {
       // Target found
       if (matrix[targetRow][j] == target) {
           return true;
       }
   }

   // Target not inside row
   return false;
}

Note that, since your rows are sorted too, you could further improve the search by using a binary search. You could even implicitly flatten the complete array (flatten all rows to one single row) and then deploy a binary search over all elements. This will be even faster than your approach.

score 0 · Answer 2 · answered Aug 03 '18 at 07:57

As Zabuza points out, there are several bugs in your code.

And as rghome points out, you probably initialize your matrix incorrectly.

Try this way of initializing the matrix. Then your code will work (the example below returns true as expected):

    int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}};
    System.out.println(new Solution().searchMatrix(matrix, 3));

Then go thru Zabuza's answer and fix your bugs.

I am getting array index out of bound on leetcode

2 Answers2