We are given a 1-d array and we have to return the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or equal to 3 times.
So for eg.
[1, 3, 3, 3, 2, 2, 2, 3, 1] should return
[1, 1] i.e. first the elimination of
2's occuring three times and after its elimination there is
3 for four times at stretch. After eliminating
3's we are left with
1's which occur less than three times, so no elimination.
[3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] should return
[3,1,3,2,3]. Here we can jumble the eliminations in different ways but no order of eliminations can lead to an array less than in size than
The time complexity should have a tighter upper bound than $O(n^2)$.
I am thinking of this problem but I haven't been able to identify a specific technique for solving it. I am thinking of
graphs and also
recursion but till now I have failure tackling the order of eliminations as the eliminations can happen in random order. More than the solution I would like to know the technique and thought process walkthrough of this problem.