c++buffer-overflow

Runtime error: addition of unsigned offset in leetcode


I was solving a question on Leetcode(322. Coin Change) and I wrote my solution which is working on VScode. the code is:

int coinChange(vector<int>& coins, int amount) {
   int n = coins.size();
   vector<vector<int>> dp(n+1,vector<int>(amount+1,999));

   for(int i=0;i<n+1;i++)
      dp[i][0] = 0;
   for(int i=0;i<amount+1;i++){ 
      dp[0][i] = 999;
   }

   for(int i=1;i<n+1;i++){
      for(int j=1;j<amount+1;j++){
            if(coins[i-1]<=amount)
               dp[i][j] = min( dp[i][j-coins[i-1]]+1, dp[i-1][j] );
            else
               dp[i][j] = dp[i-1][j];
      }
   }

   if(dp[n][amount]>=999) return -1;
   return dp[n][amount];
}

upon running for testcase coins = [1,2,5], amount = 11, it I'm getting the following error

Line 1117: Char 34: runtime error: addition of unsigned offset to 0x504000000110 overflowed to 0x50400000010c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13/bits/stl_vector.h:1126:34

Solution

  • In the line:

    dp[i][j] = min( dp[i][j-coins[i-1]]+1, dp[i-1][j] );

    When indexing into dp, j-coins[i-1] can be less than 0 because coins[i-1] can be grater than j.

    This could cause the runtime error you are seeing. I would suggest running the code under a debugger and stepping through the loop to see what the values of the indexes are at different points in time.