Leetcode Prob No. 494 Target Sum ,,,,,Getting Runtime Error

Question

In this code,i was getting this error... for input nums =

 Line 1034: Char 34: runtime error: addition of unsigned offset to 0x6250004d0900 overflowed to 0x6250004cf960 (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

//Incorrect code
class Solution {
public:
    
    int fun(vector<int>& nums, int target,int n ,vector<vector<int>> &dp){
        if(n  == 0){
            if(target == 0) return 1;
            return 0;
            }
        
        if(dp[n][target+1000] != -1) return dp[n][target+1000];
        return dp[n][target+1000] =  fun(nums,target - nums[n-1],n-1,dp) + fun(nums,target + nums[n-1],n-1,dp);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
       vector<vector<int>> dp(21,vector<int>(2001,-1));
       return fun(nums,target,nums.size(),dp);
    }
};

After getting runtime. error in prev approach, i tried 2nd approach just by reversing the way of traversing the vector nums from N->0 to 0->N, and the code successfully got submitted. What was the problem in the previous code???

//Correct code
class Solution {
public:
    int dp[21][2001];

    int fun(int i,int sum,int target,vector<int>&nums){
        if(i == nums.size()){
            if(sum == target) return 1;
            return 0;
        }
        if(dp[i][sum+1000] != -1) return dp[i][sum+1000];
        return dp[i][sum+1000]  = fun(i+1,sum+nums[i],target,nums) + fun(i+1,sum-nums[i],target,nums);  
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        memset(dp,-1,sizeof(dp));
        return fun(0,0,target,nums);
    }
};

With `dp[n][target+1000]`, are you ***sure*** that both `n` and `target + 1000` are in bounds of the vectors? — Some programmer dude, Mar 13 '23 at 13:50
@Reborne *What was the problem in the previous code???* -- You wrote the code, you have the test case that fails, thus you have all the ability to know what is wrong with your code by [debugging it](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). — PaulMcKenzie, Mar 13 '23 at 14:07
To be brutally honest, in my opinion the "correct" solution is to just don't use sites like leetcode. Especially if you use it for learning programming and C++, because that's not its purpose. Once you have a couple of years of college-level computer-science education and very good knowledge of the language you want to use, those sites can be used as simple brain-teasers or entertainment when you have nothing better to do. Other than that I don't think they serve any useful purpose. — Some programmer dude, Mar 13 '23 at 14:09
`int dp[21][2001];` -- I see this too often in code that attempts to answer leetcode questions, and that is declaring gigantic arrays to fit the constraints of the question. What if the highest value was 100000? Would you try to declare an array that is `21 * 100000 * sizeof(int)` in size? You will then probably get a stack overflow error due to the stack memory being exhausted. In the real-world, this would be a vector or similar class that allocates the memory dynamically. — PaulMcKenzie, Mar 13 '23 at 14:28
@Someprogrammerdude That statement stands in stark contrast to what the developer interview looks like these days. Sites like this have become mandatory. The problem is people coming at them backwards. Too many people think they'll learn exactly what they need if they start on sites like this, but as you noted, it's the other way around. If your company doesn't do this, that's fantastic. Most still do. — sweenish, Mar 13 '23 at 15:02
What I'm seeing are a lot premature optimizations. Get a working algorithm, then optimize it. You might even have to step back to a full recursive solution. This attempt at memoization looks nothing like the others that have been posted to the site already. My fully recursive solution might be in the bottom 10% performance-wise, but it's a working solution. And that's always better than a non-working one. If I feel like it, I can revisit it and re-work it to memoize, and then to straight tabulation. — sweenish, Mar 13 '23 at 15:22
@sweenish Yes that's true, unfortunately. Doing something likes this doesn't tell the prospective employer how good the candidate is at things like debugging, learning how he or she thinks about problems, how they would function as part of a team, how they handle the actual problems the employer have, how they are socially. And the solution is often just a search away, so it doesn't really tell how good the applicants are are at actually solving the problem anyway. — Some programmer dude, Mar 16 '23 at 07:19

score 0 · Accepted Answer · answered Mar 13 '23 at 13:56

According to the problem page

Target Sum - LeetCode

The value of the input target may become -1000.

With this value, after the calculation target - nums[n-1], the index target+1000 may go below zero with the new value of the argument target, and this is an out-of-range access.

You have to allocate enough elements and use proper offset to avoid this error.

Leetcode Prob No. 494 Target Sum ,,,,,Getting Runtime Error

1 Answers1