2
$\begingroup$

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.

$\endgroup$
  • 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$ – Yuval Filmus Jun 14 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$ – Navjot Waraich Jun 14 at 12:36
  • $\begingroup$ Usually we denote your "better than $O(n^2)$" by $o(n^2)$. $\endgroup$ – Yuval Filmus Jun 14 at 12:52
  • $\begingroup$ You can proceed with your dynamic programming answer as I would be keen to get your explanation. $\endgroup$ – Navjot Waraich Jun 14 at 13:08
  • $\begingroup$ It was a suggestion for you, though. $\endgroup$ – Yuval Filmus Jun 14 at 13:09
1
$\begingroup$

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:
      x--
      // avoid copying the run into output array
    if a[run[x]] != a[i]:
      x++
    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.

$\endgroup$
  • $\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$ – Navjot Waraich Jun 14 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 at 9:16
  • 1
    $\begingroup$ Sorry but your answer is badly explained. Try improving it. $\endgroup$ – Navjot Waraich Jun 14 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 at 9:26
  • 3
    $\begingroup$ Here is a counterexample to the greedy approach: aaabbbaa. You should delete bbb first. $\endgroup$ – Yuval Filmus Jun 14 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.