runtime error on leetcode 540. Single Element in a Sorted Array

Question

I am doing leetcode 540. Single Element in a Sorted Array using c++. The problem is: You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Here is a example:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

I run into runtime error again:

Runtime Error Message:
AddressSanitizer: heap-buffer-overflow on address 0x602000000034 at pc 0x0000004056da bp 0x7ffcd2cff910 sp 0x7ffcd2cff908

Here is my code and it's super easy to understand.

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        int i = 1;
        int output;
        if(nums[0] != nums[1])
            return nums[0];
        if(nums[n-1] != nums[n-2])
            return nums[n-1];
        for(i = 1; i < n-1; i++)
            {
                if(nums[i]!=nums[i-1] && nums[i]!=nums[i+1])
                {
                    output = nums[i];
                    break;
                }
            }
        return output;
    }
};

I really hope someone can help me. I met this problem several times and I have no clue what's going on.

Jarvis · Accepted Answer · 2019-12-26 06:03:11Z

2

In this part :

if(nums[0] != nums[1])
    return nums[0];
if(nums[n-1] != nums[n-2])
    return nums[n-1];

What if the size of nums is 0 or 1? I think you should add some sanity-check to your code, like checking for the input vector size to handle corner cases of 0 or 1 elements.

I added this condition and it is accepted now.

if(n == 1)
   return nums[0];

edited Dec 26, 2019 at 6:03

answered Dec 26, 2019 at 5:57

Jarvis

8,5923 gold badges33 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

CinCout Over a year ago

It is worth mentioning that all those if aren't required. The sole loop should suffice.

Slava · Accepted Answer · 2019-12-26 06:40:09Z

0

If you start iteration from 0, not from 1 it could be significantly simplified:

int singleNonDuplicate(vector<int>& nums) 
{
   for( size_t i = 0; i < nums.size(); i += 2 )
       if( i + 1 == nums.size() || nums[i] != nums[i+1] ) 
           return nums[i];
   // if we reach here then input is wrong
   throw std::runtime_error( "wrong input" );
}

and you do not need any preconditions.

Note: on the site solution required to be O(log n), so though this loop will logically work you need more complex solution using binary search, as this solution using loop is O(n).

edited Dec 26, 2019 at 6:40

answered Dec 26, 2019 at 6:32

Slava

44.5k2 gold badges54 silver badges100 bronze badges

2 Comments

Stephane Over a year ago

Thanks! This also works. what does "throw" mean here? I searched online, but I don't understand the specific function of it.

Slava Over a year ago

throw raises exception in C++. You may return error code or do something else, but cleanest way is to raise

Collectives™ on Stack Overflow

runtime error on leetcode 540. Single Element in a Sorted Array

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related