Why AddressSanitizer:DEADLYSIGNAL?

user_13239122 0
Viewed 52
class Solution {
int maxRow, maxCol;
int x[4] = {1, -1, 0, 0};
int y[4] = {0, 0, 1, -1};

bool isValid(int row, int col){
    return (row >= 0 && row < maxRow && col >= 0 && col < maxCol);
}

int longestPath(int row, int col, vector<vector<int>>& matrix, vector<vector<int>>& dp){
    if(dp[row][col] != -1){
        return dp[row][col];
    }
    int longestCurrPath = 1; 
    for(int dir = 0; dir < 4; ++dir){
        int newRow = row + x[dir];
        int newCol = col + y[dir];
        if(isValid(newRow, newCol) && matrix[col][row] > matrix[newRow][newCol]){
            longestCurrPath = max(longestCurrPath, longestPath(newRow, newCol, matrix, dp) + 1);
        }
    }
    return dp[row][col] = longestCurrPath;
}

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        maxRow = matrix.size();
        maxCol = matrix[0].size();
        int LIP = 1;
        vector<vector<int>> dp(maxRow + 1, vector<int>(maxCol + 1, -1));
        for(int row = 0; row < maxRow; ++row){
            for(int col = 0; col < maxCol; ++col){
                if(dp[row][col] == -1)
                    LIP = max(LIP, longestPath(row, col, matrix, dp));
            }
        }
        return LIP;
    }
};

AddressSanitizer:DEADLYSIGNAL

==31==ERROR: AddressSanitizer: stack-overflow on address 0x7ffe60cafff8 (pc 0x0000003466d2 bp 0x7ffe60cb0070 sp 0x7ffe60cb0000 T0) ==31==ABORTING

c++14 c++11 c++
1 Answers

Answer: Stackoverflow.

Your recursive logic is buggy. And you perpetually end up in a situation like this:

first second

See comments in the code below

int longestPath(int row, int col, vector<vector<int>>& matrix, vector<vector<int>>& dp){
    if(dp[row][col] != -1){

       // Termination depends on `dp`
       return dp[row][col];
    }

    int longestCurrPath = 1; 
    for(int dir = 0; dir < 4; ++dir){
       int newRow = row + x[dir];
       int newCol = col + y[dir];
       if(isValid(newRow, newCol) && matrix[col][row] > matrix[newRow][newCol]) {

           // Making recursive calls without ever influencing `dp`
           longestCurrPath = max(longestCurrPath, longestPath(newRow, newCol, matrix, dp) + 1);
       }
    }

    // This is the only time you change `dp`
    return dp[row][col] = longestCurrPath;
}
user_16213910
Related