Problem with c++ leetcode compiler while compile a code { local compiler and online compiler gives different result for the same code }

Question

This is the problem i am trying to solve, along with the solution testing the test case in which i am having trouble in.

Leetcode problem: 128. Longest Consecutive Sequence

#include <iostream>
#include <vector>
#include <unordered_map>

class Solution {
public:
    int longestConsecutive(std::vector<int>& nums)
    {
        std::unordered_map<int, int> seq;
        for (auto i : nums)
        {
            ++seq[i];
        }
        int max{ 0 };
        for (auto i : seq)
        {
            int ans{ 0 };
            int x{ i.first };
            if (seq[x] > 0)
            {
                ans = 1;
                int p{ x };
                int q{ x };
                while (seq[p - 1] > 0)
                {
                    --p;
                    ++ans;
                }
                while (seq[q + 1] > 0)
                {
                    ++q;
                    ++ans;
                }
            }
            if (max < ans)
                max = ans;
        }
        return max;
    }
};

int main()
{
    Solution s;
    std::vector<int> nums{ 4,0,-4,-2,2,5,2,0,-8,-8,-8,-8,-1,7,4,5,5,-4,6,6,-3 };
    std::cout << s.longestConsecutive(nums);
    return 0;
}

When i tested this test case in my offline compiler(microsoft c++ compiler in visualt studio), it is showing the test case ans as 5(which is absolutely correct).

However, upon submitting the same solution in leetcode it is showing the test case ans as 4(which is wrong). I tried testing this case in online gdb compiler also and there also this test case ans is showing as 4.

My solution has passed 55/72 cases so i am sure there is not any issue with my algorithm or my answer output format. I believe it to be an issue with leetcode or online

Answer 1

Consider your code (shortened for brevity)

    for (auto i : seq)
    {
        int x{ i.first }; 
        if (seq[x] > 0) // okay, will be in the sequence
        {
            int p{ x };
            int q{ x };
            while (seq[p - 1] > 0) // p-1 might not be in the map, so insert
            {}
            while (seq[q + 1] > 0) // q+1 might not be in the map, so insert
            {}
        }
    }

Both these while loops can cause insertions, which can invalidate the iterators used by for (auto i : seq). Thus, you have Undefined Behaviour, and getting anywhere near the correct result is more by accident.

Answer 2

With your issue pointed out (invaliding iterators due to inserts), here's a working solution. It beats 80.33% on runtime and 60.17% on memory:

class Solution {
 public:
  int longestConsecutive(vector<int>& nums) {
    std::unordered_set<int> uniqueVals;

    // Fill set
    for (auto& i : nums) {
      uniqueVals.insert(i);
    }

    int maxSequence = 0;
    // Iterate the set instead of the vector to avoid re-checking
    // repeated values in the vector.
    for (auto& i : uniqueVals) {
      // Is number the start of a sequence?
      if (uniqueVals.find(i - 1) != uniqueVals.end()) {
        continue;  // It was not, we move on immediately
      }

      // Getting here means our value is the start of a sequence
      int sequenceLength = 1;
      for (int val = i + 1; uniqueVals.find(val) != uniqueVals.end();
           ++val, ++sequenceLength) {
      }
      if (sequenceLength > maxSequence) {
        maxSequence = sequenceLength;
      }
    }

    return maxSequence;
  }
};

This answer was accepted by leetcode, so it passes all tests.

The big idea is identifying the start of a sequence. I use std::unordered_set because I don't care how many times a value has occurred, and I get O(1) insertion. I only care if a value is in the set or not.

More importantly, I don't modify the set with insertions as I'm iterating it (read-only), which keeps my loop well-defined.