The problem in question is Two Sum.
This is the error message:
=================================================================
==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001a0 at pc 0x000000346130 bp 0x7ffcd0ff6df0 sp 0x7ffcd0ff6de8
READ of size 4 at 0x6020000001a0 thread T0
#2 0x7f5dcdb820b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x6020000001a0 is located 0 bytes to the right of 16-byte region [0x602000000190,0x6020000001a0)
allocated by thread T0 here:
#6 0x7f5dcdb820b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8010: fa fa fd fd fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8020: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
=>0x0c047fff8030: fa fa 00 00[fa]fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==31==ABORTING
This is my solution:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
int i = 0, j = 1, holder;
holder = j;
while(1)
{
if(nums[i] + nums[j] == target)
{
return {i, j};
}
j++;
if(j == nums.size())
{
j = holder + 1;
i = holder - 1;
holder = j;
}
}
return {};
}
};
I tested it in Visual Studio before i even tried solving it on Leet Code and it worked fine.
>Solution :
Always check if the index is within bounds BEFORE accessing it in an uncontrolled manner as you have accessed in your code.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i = 0, j = 1, holder = j;
while (1) {
if (j == nums.size()) {
j = holder + 1;
i = holder; // assigning holder - 1 caused the right solution to get skipped
holder = j;
}
// though j had a bound check, holder had no bound check
// so nums[j] got out of range
if (nums[i] + nums[j] == target) return {i, j};
j++;
}
return {};
}
};
Now even after resolving the address sanitizer error, your solution still exceeds the time limit. Therefore, it would be wise to consider an alternative approach such as using a hashmap or set based solution or a more efficient algorithm.