Heap-buffer overflow when implementing two-pointer approch

Question

I'm solving this brain teaser

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. 
             Therefore, index1 = 1, index2 = 2. 
             We return [1, 2].

and my solution is giving this error:

=================================================================
==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000620 at pc 0x000000345e97 bp 0x7ffcd6847990 sp 0x7ffcd6847988
READ of size 4 at 0x602000000620 thread T0
    #2 0x7f2c3b9790b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000620 is located 0 bytes to the right of 16-byte region [0x602000000610,0x602000000620)

I did some research and saw that this is usually caused by calling an index that's too far (i.e. outside the range of the data structure you're using) but since I'm using vectors I don't get why I have this error. It happened on the following test case: [5,25,75] 100.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // can have an i that points forward and a j that loops through everything until sum
        // is greater
        // checking recursively
        // if sum greater stop checking (as list is increasing)
        // can reset i each time??
        // add 1 at the end
        
        vector<int> indices;
        int i = 0;
        int j = 0;
        
        // for loop on top?
        for (int i; i < numbers.size(); i++)
            int j = 0;
            while (numbers[i] + numbers[j] <= target) {
                if (numbers[i] + numbers[j] == target && i != j) {
                    // some if determining if i or j is greater
                    // to determine the order in which to push back
                    indices.push_back(i+1);
                    indices.push_back(j+1);
                    return indices;
                } else {
                    j++;
                }
            }
        return indices;
    }
};

The other tests are passing but this one is failing. I am trying to use a two-pointer approach here.

Answer 1

There are several issues with this code, some simple syntactic mistakes, some algorithmic problems.

First, as others have mentioned, i is uninitialized in your outer for loop. Luckily, that never comes into play because you have no braces around the loop body. Your code is equivilent to

for (int i; i < numbers.size(); i++) {
    int j = 0;
}
while (numbers[i] + numbers[j] <= target) {
    // ...
}

This is presumably not what you intended, so you need to both initialize i and add {} around the loop body:

for (int i = 0; i < numbers.size(); i++) {
    int j = 0;
    while (numbers[i] + numbers[j] <= target) {
        // ...
    }
}

Of course, you also don't need the redundant definitions of i and j outside the loops. Those variables get hidden by the ones defined within the loops, and are never used.

---

Of course, this still doesn't address your out-of-range error. For that, you need to re-think your algorithm. Lets walk through it to find the issue. I'll just focus on the inner while loop.

Assuming, from your test case that numbers = {5, 25, 75} and target = 100.

First iteration:

• i = 0 and j = 0
• numbers[i] + numbers[j] -> numbers[0] + numbers[0] -> -> 5 + 5 -> 10. That's less than 100, so the loop is entered
• if (10 == 100) is false, so the else branch is selected
• j++, so now i = 0 and j = 1

Second iteration:

• numbers[i] + numbers[j] -> numbers[0] + numbers[1] -> 5 + 25 -> 30. That's less than 100, so the loop continues
• if (30 == 100) is false, so the else branch is selected
• j++, so now i = 0 and j = 2

Third iteration:

• numbers[i] + numbers[j] -> numbers[0] + numbers[2] -> 5 + 75 -> 80. That's less than 100, so the loop continues
• if (80 == 100) is false, so the else branch is selected
• j++, so now i = 0 and j = 3

Third iteration:

• numbers[i] + numbers[j] -> numbers[0] + numbers[3] -> boom

j is now out of range of the valid indices of numbers, so when you attempt to access numbers[j] the behavior of your program becomes undefined. In this case, it crashed; the best possible outcome.

Answer 2

as the above comments pointed it out,

for (int i; i < numbers.size(); i++)

here 'int i' hides the previous local declaration of 'int i = 0;' (C4456), which is not desirable.

and the problem is that although i is bound to the range [0, n-1], j is not, which can cause access violation when j exceeds the range.

Answer 3

You can use below code which will pass your all test cases.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
 //first we will declare an additional vector which will return desired solution
        vector<int> mult;
//by using two pointer approach
        for(int i = 0; i<=nums.size(); i++){
            for(int j = i+1; j<nums.size();j++){
//checking for condition
                if(nums[i]+nums[j]==target){
                       mult.push_back(i);
                       mult.push_back(j);
                    j++;
                    return mult;
            }

        
        }
        
    
    }
         return mult;
    }
};