Going out of vector limits but can't figure out where. Vector out of scope

Question

// Find smallest missing positive number
// Solve in O(n) time and O(1) space
#include <bits/stdc++.h> 
using namespace std;

class Solution {
public:

    void swap(int* a, int* b){
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }

    // move all non positive numbers to the left side of the vector
    int negativeToLeft(vector<int>& v){ // better name is seggregate!

        int j=0, i;

        for(int i = 0; i < v.size(); i++){
            // If number is negative then swap to left side of array
            if(v[i] <= 0){
                swap(&v[i], &v[j]);
                j++;
            }

        }
        // return the index from where the positive numbers start
        return j;
    }

    int firstMissingPositive(vector<int>& nums) {

        // move non positive to left
        int index = negativeToLeft(nums);
        
        // find the size of the positive segment of the vector
        int size = nums.size() - index;
        
        // traverse the vector
        for(int i = index; i < nums.size(); i++){
            
            // mark the index of the number as negative, if the number is within size
            if(nums[i] <= size){
                nums[abs(nums[i])] = -1 * nums[abs(nums[i])];
            }
        }
        if(index==0){
            nums[0] = -1;
        }

        for(int i = index; i < nums.size(); i++){
            // if the number at the index is positive then return the the index
            if(nums[i]>0){
                return i;
            }
        }
        
        return size + 1;
    }
};

 int main()
 {
     vector<int> g1{-1, -2, -3, -4};

     Solution m;
     cout << m.firstMissingPositive(g1);
 }

Error:

Line 924: Char 9: runtime error: reference binding to null pointer of type 'int' (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_vector.h:933:9

I can't figure out where exactly an out of scope vector is being called. Any help would be much appreciated!

Use a debugger and look at which line of your code the error originates. The call stack will help. — Swordfish, Aug 02 '20 at 14:39
You're treating array elements as indices in several places, and 4 is an invalid index. Why are you assuming that the absolute values of the array's elements are valid indices? — molbdnilo, Aug 02 '20 at 14:43
Possible cause: in `firstMissingPositive`, consider what `nums[abs(nums[i])]` will evaluate to when `nums[i] == -4`. — Brian61354270, Aug 02 '20 at 14:43
`if(nums[i] <= size)` allows access to one element past the last valid index. The last valid index is `size - 1`. — Lukas-T, Aug 02 '20 at 14:44
[Why should I not #include ?](https://stackoverflow.com/q/31816095/5910058) / [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/q/1452721/5910058) — Jesper Juhl, Aug 02 '20 at 14:47

Going out of vector limits but can't figure out where. Vector out of scope

0 Answers0