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.

Similarly [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 [3,1,3,2,3].

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 hashing, 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.

  • 1
    $\begingroup$ What do you mean by "better than $O(n^2)$"? Do you mean $O(n^2)$, or $o(n^2)$? If the former, I would try dynamic programming. $\endgroup$ Jun 14 '19 at 11:16
  • $\begingroup$ @YuvalFilmus I just mean it should have tighter upper bound than $O(n^2)$ i.e. $O(nlogn)$ or $O(n)$ would do. $\endgroup$ Jun 14 '19 at 12:36
  • $\begingroup$ Usually we denote your "better than $O(n^2)$" by $o(n^2)$. $\endgroup$ Jun 14 '19 at 12:52
  • $\begingroup$ You can proceed with your dynamic programming answer as I would be keen to get your explanation. $\endgroup$ Jun 14 '19 at 13:08
  • $\begingroup$ It was a suggestion for you, though. $\endgroup$ Jun 14 '19 at 13:09

Using O(n) extra space, you need to record start for each run of same numbers. Scan the array linearly. Once you removed a run, you either continue previous run, or start a new one.

for i:
  if a[i] != a[i-1]:
    if run[x] - run[x-1] >= 3:
      // avoid copying the run into output array
    if a[run[x]] != a[i]:
    run[x] = i

On the second thought, you don't need the run[] array - only start the of current run. Once a run eliminated, you can check that previous run is at least 3 elements long in O(1) operations. You still need O(n) place to store the list of eliminated ranges, though.

  • $\begingroup$ I specifically mentioned that more than the solution I want the thought process and techniques involved in solving the problem. Either you explain how you got to the solution otherwise this is not a fitting answer for me. $\endgroup$ Jun 14 '19 at 9:09
  • $\begingroup$ I checked the second example - it flies. So, try to implement it or just perfrom the check again. $\endgroup$
    – Bulat
    Jun 14 '19 at 9:16
  • 1
    $\begingroup$ Sorry but your answer is badly explained. Try improving it. $\endgroup$ Jun 14 '19 at 9:22
  • 1
    $\begingroup$ Oh, boy, if you can't got it and need a help, try to be more polite next time $\endgroup$
    – Bulat
    Jun 14 '19 at 9:26
  • 3
    $\begingroup$ Here is a counterexample to the greedy approach: aaabbbaa. You should delete bbb first. $\endgroup$ Jun 14 '19 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.