0

Can someone help me to solve this error?
I met a problem when I did an exercise on LeetCode.
The question is finding a number in a [n*m] 2D array.

In an n * m two-dimensional array, each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom. Please complete a function, input such a two-dimensional array and an integer to determine whether the array contains the integer.

0 <= n <= 1000
0 <= m <= 1000

For example

/**********input********/
matrix:[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
target:5
/**********output********/
true

And my solution is:

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;

        vector<vector<int>>::iterator row;
        vector<int>::iterator column;
        for(row=matrix.begin();row!=matrix.end();row++){
            if(target<*(*row).begin()) return false;
            for(column=(*row).begin();column!=(*row).end();column++){
                if(target==*column)return true;
                else if(target<*column)break;
            }
        }
        return false;
    }
};

I got a runtime error when the input is [[ ]]: reference binding to null pointer of type 'int' (stl_iterator.h).
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_iterator.h:797:16

Thanks in advance for your help!

Improve this question
6
  • 2
    Providing a minimal reproducible example that we can copy-and-paste into our favorite text editor, and then compile and reproduce the problem would be very helpful. As is, the bug may be here or may be elsewhere, and we'll only be able to guess-by-inspection as to what is wrong. I suspect an out-of-bounds mistake. Commented Aug 24, 2020 at 17:07
  • Which line of your code is responsible for executing the line mentioned in the error? That's particularly helpful info. Commented Aug 24, 2020 at 17:10
  • Not reproducible : wandbox.org/permlink/tncV62FFeytUvqyP Commented Aug 24, 2020 at 17:12
  • How do you populate matrix? Commented Aug 24, 2020 at 17:14
  • According to the conditions for m and n it's possible to get input with 0 columns, right? In this case if(target<*(*row).begin()) could dereference an past-the-end-iterator. If you know the input for which the code fails please show it. Commented Aug 24, 2020 at 17:16

4 Answers 4

Reset to default
2

Your solution looks a bit complicated. You only need to loop over the outer vector and all the inner vectors and return true if you find a match.

    bool findNumberIn2DArray(const vector<vector<int>>& matrix, int target) {
        for(const auto& inner : matrix) {
            for(int value : inner) {
                if(value == target) return true;
            }
        }
        return false;
    }

You could also use std::find_if and std::find to find the element. You supply a lambda to std::find_if and inside the lambda you execute std::find on the inner vector.

Example:

#include <algorithm>

    bool findNumberIn2DArray(const vector<vector<int>>& matrix, int target) {
        auto it = std::find_if(matrix.begin(), matrix.end(), [&target](const auto& v) {
            auto it = std::find(v.begin(), v.end(), target);
            return it != v.end();
        });
        return it != matrix.end();
    }
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Yes, you are right. But I want to skip unnecessary calculations in this code. I will try to improve the efficiency of my code. Anyway, thanks for pointing out.
@Ted I think you've got it differently. OP's algorithm is not just checking if any of the element in the matrix is equal to the target, but it also involves checking if the target is greater than each element until some element equal to target is found.
@Hopkins Then remove the line if(target<*(*row).begin()) return false; It'll only slow down the program. You should also have stated in the question that the rows are required to be sorted. I didn't take that for granted.
@brc-dd I only see "The question is finding a number in a [n*m] 2D array" but you are right. For OP:s algorithm to work, each row must be sorted.
Oh, yes. You are right. It's my first time to post a problem and the description is not accurate. Sorry!
1

The error occurs when a matrix with 0 columns is entered. Then in the line

if(target<*(*row).begin()) return false;

*row is empty, thus, (*row).begin() returns the past-the-end-iterator and dereferencing it causes undefined behaviour (a crash in your case).

You need to catch this case. Because every row has the same number of columns I suggest to expand the check at the very beginning of the function to

if(matrix.empty() || matrix.front().empty()) return false;

This will return false if the matrix has either 0 rows, or 0 columns.

Improve this answer

7 Comments

but why if(matrix.empty()) return false; doesn't work? If this code works normally, the function will return false at once and will not continue. That is, even the input is empty, the function can work normally.@churill
@Hopkins If matrix.empty() == true there are no numbers in it so returning false is 100% correct. You must check that it's not empty before accessing the first of the inner vectors (matrix.front()) otherwise you'll have undefined behavior again.
@TedLyngmo Yes, I understand what you mean. But sorry, could I ask the reason why the input [[ ]] will cause this error. Is it a bug on LeetCode?
@Hopkins Do you mean that it cause errors even with churil's bugfix?
@TedLyngmo Yep, you are so kind. Your answer and patience will encourage me to improve my coding skill. I appreciate your help.
|
1

I think that you just need a check on bounds. Check if this helps. You can simplify (and beautify) your code to greater extent by using range-based for loops.

#include <iostream>
#include <vector>
using namespace std;

bool findNumberIn2DArray(vector<vector<int>> &matrix, int target) {
    // this loop will only execute if matrix is not empty, no need to do a
    // separate check for matrix.empty()
    for (auto &&row : matrix) {
        // check if the row is empty or not; if it's not then check if target is
        // less than the first element // modified after going thru OP's answer
        if (row.empty() or target < row[0])
            return false;
        // done something here...
        for (auto &&element : row)
            if (target == element)
                return true;
            else if (target < element)
                break;
    }
    return false;
}

int main() {
    vector<vector<int>> m = {{1, 4, 7, 11, 15},
                             {2, 5, 8, 12, 19},
                             {3, 6, 9, 16, 22},
                             {10, 13, 14, 17, 24},
                             {18, 21, 23, 26, 30}};
    cout << findNumberIn2DArray(m, 5);
}
Improve this answer

Comments

0

Maybe try this solution below:

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int> >& matrix, int target) {
        if(matrix.empty()) return false;
            //需要考虑数组为空的情况。

        vector<vector<int> >::iterator row;
        vector<int>::iterator column;
        for (row=matrix.begin(); row!=matrix.end(); row++){
            for (column=(*row).begin(); column!=(*row).end(); column++){
                if (target==*column) return true;
            }
        }

    return false;
    }
};
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.