Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Why getting runtime-error even after declaring size of vector?

I am solving leetcode problem : https://leetcode.com/problems/number-of-islands/

It gives me this error:

Char 34: runtime error: addition of unsigned offset to 0x6080000000a0 overflowed to 0x60800000008c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

My code:

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

class Solution {
public:
    void bfs(vector<int>&visited,vector<vector<char>>& grid,int r,int c,int n,int m)
    {
        queue<pair<int,int>>q;
        q.push({r,c});
        int dx[4]={1,-1,0,0};
        int dy[4]={0,0,1,-1};
        
        visited[r*m+c]=1;
        while(!q.empty())
        {   
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            for(int i=0;i<4;i++)
            {
                int newX=x+dx[i];
                int newY=y+dy[i];
                if(newX<n && newY<m && visited[newX*m+newY]==-1 && grid[newX][newY]=='1')
                {
                    q.push({newX,newY});
                    visited[newX*m+newY]=1;
                }
                    
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        
        vector<int>visited(n*m+1,-1);
        
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(visited[i*m+j]==-1 && grid[i][j]=='1')
                {
                    bfs(visited,grid,i,j,n,m);
                   cnt++;
                }
            }
        }
        return cnt;
    }
};

I have used the BFS algorithm here.
I have declared sizes of all vectors to prevent out of bounds error, still its occuring.

>Solution :

In this line:

if(newX<n && newY<m && visited[newX*m+newY]==-1 && grid[newX][newY]=='1')

You never check if newX or newY are less than 0. If so, accessing grid[newX][newY] gives a runtime error.

Just add two conditions, as shown below:

if(newX<n && newY<m && newX >= 0 && newY >= 0 && visited[newX*m+newY]==-1 && grid[newX][newY]=='1')
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading