---
title : Filter Elements
tags : Functional Programming, Computer Science, Hacker Rank
---
###### tags: `Functional Programming`, `Computer Science`, `Hacker Rank`

Filter Elements
===

Problem Analytica
---

Given a list of N integers A = [a1, a2, ..., aN], you have to find those integers which are repeated at least K times. In case no such element exists you have to print -1.

If there are multiple elements in A which are repeated at least K times, then print these elements ordered by their first occurrence in the list.

### Example
Let's say A = [4, 5, 2, 5, 4, 3, 1, 3, 4] and K = 2. Then the output is

4 5 3

because these numbers have appeared at least 2 times.
Among these numbers,
4 has appeared first at position 1,
5 has appeared next at position 2,
and 3 has appeared thereafter at position 6.
That's why, we print in the order 4, 5 and finally 3.

Point of Attack
---
### Intuition
The solution is quite straight forward.
We can create a ordered dictionary,

[4->3, 5->2, 2->1, 3->2, 1->1]

then append the number and update the occurance through the scanning.
Finally, we can filter the elements which met the occurance the problem needs as our answer.

### Can we do better?
I have an eager to solve this without pack and filter, can we solve this in one linear search without storing any info?

If no, how can we proof it?
#### Proof
Suppose a list $A = {a_1,a_2, a_3, ... }$ ,
if we split the list to do a linear search start at each index,
i.e. [
search ${ a_1, a_2, a_3, ... }$ ,
search ${ a_2, a_3, a_4, ... }$ ,
search ${ a_3, a_3, a_5, ... }$ ,
],
We should know that, any later element will lost the earlier duplicate, thus the later occurance are incorrect and only occourance obtain from earlier search is trustworth.

Therefore, we can only know the element has met the occurance after a full scan, as intermediate dropping a element will produce a incorrect result.

In this sense, each element can only filter out after full scan. Which means, linear search can not perform filtering and scanning without storing info, as it cannot return intermediate result during the scanning.

Algorithm
---

Hierarcy Decompsition
---

Further Readings
---
###### tags: `Functional Programming`, `Computer Science`, `Hacker Rank`