Remove duplicate element from a sorted array such that no more than 2 elements of same number lies in returned end index

Question

I was solving this problem : https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii. Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

I used the below code to solve this:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct getrid
{
    bool operator()(int x)
    {
        static int count = 0;
        static int prev = -1000001;

        if(count == 0)
        {
            prev = x;
            count++;
            return false;
        }
        else
        {
            if(x == prev)
            {
                count++;
                if(count > 2)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                prev=x;
                count=1;
                return false;
            }
        } 

    }

};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() < 3)
        {
            return nums.size();
        }
        auto last_iterator=std::remove_if(nums.begin(),nums.end(),getrid());         
        if(last_iterator == nums.end())
        {
            std::cout <<"Pointing to iterator pointed by end \n";
        }
        int total_element= last_iterator-nums.begin();
        return total_element;
    }
};

While this works fine perfectly for most test cases, this seems to fail for test cases when vector is [1,1] or [1,2,2] . Basically it seems for cases when last element has 2 occurrences.

But when I run the same on gdb online this seems to work perfectly fine. The returned value is 2 for vector [1,1] and 3 for [1,2,2].

Anyone can help me with why my test case is failing in leetcode ? Code for gdbonline below

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct getrid
{
    bool operator()(int x)
    {
        static int count = 0;
        static int prev = -1000001;

        if(count == 0)
        {
            prev = x;
            count++;
            return false;
        }
        else
        {
            if(x == prev)
            {
                count++;
                if(count > 2)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                prev=x;
                count=1;
                return false;
            }
        } 

    }

};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto last_iterator=std::remove_if(nums.begin(),nums.end(),getrid());         
        if(last_iterator == nums.end())
        {
            std::cout <<"Pointing to iterator pointed by end \n";
        }
        int total_element= last_iterator-nums.begin();
        return total_element;
    }
};

int main()
{
    std::vector<int> vec = {1,2,2};
    Solution s;
    int total_val = s.removeDuplicates(vec);
    std::cout <<"total val returned is: " << total_val <<"\n";
    return 0;
}

Thanks

score 2 · Accepted Answer · answered Aug 02 '23 at 22:42

2

The functor shown in the posted code uses two static variables

bool operator()(int x)
{
    static int count = 0;
    static int prev = -1000001;
    // ...
}

Those are initialized once, but they are never resetted and beeing static they retain their values between calls.

While the second snippet calls removeDuplicates only once, the on-line judge probably calls that function multiple times, one for each test. The problem is that each new test case starts with the last values of count and prev of the previous one.

answered Aug 02 '23 at 22:42

Bob__

12,361
3
28
42

1

Also: [Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). – Bob__ Aug 02 '23 at 22:49
very valid point something that I missed, what would be the right way to do this in such cases, if we are trying to do it with algorithms used in c++17 where i need to provide a callable or lambda function to tell which element to remove. Note there are simple iteration ways by which this can be done and I have done it, but was also willing to explore inbuilt algorithms for these. – Invictus Aug 02 '23 at 22:54
@Invictus Well, you could just make them class *members*: https://godbolt.org/z/r9afn73G4 – Bob__ Aug 02 '23 at 23:15
Making them class member rather than static would not work as this can lead to variable get reinitialized with each call and hence count getting reset for each call leading to not appropriately counting occurrence of each element. One easy way is to make these 2 variables global and reset them before call to the remove_if but i wanted to avoid using that mechanism. – Invictus Aug 03 '23 at 06:33
1

@Invictus Please note that those member variables are initialized at each call of `auto last_iterator=std::remove_if(nums.begin(),nums.end(),getrid());`, because `getrid()` instantiates a new `getrid` object, not at each call of `operator()`. Could you please provide the test cases which fail when applied to the snippet in my previous comment so that I can improve it? – Bob__ Aug 03 '23 at 09:38

Remove duplicate element from a sorted array such that no more than 2 elements of same number lies in returned end index

1 Answers1