Find an element in list that appears at least 60% of the time using Divide and Conquer approach?

user_13177568 0
Viewed 146

Input is an array that has at most one element that appears at least 60% a time. The goal is to find if this array has such an element and if yes, find that element. I came up with a divide and conquer function that finds such an element.

from collections import Counter

def CommonElement(a):
    c = Counter(a) 
    return c.most_common(1) #Returns the element and it's frequency

def func(array):
    if len(array) == 1:
        return array[0]

    mid = len(array)//2

    left_element = func(array[:mid])
    right_element = func(array[mid:])

    if left_element == right_element:
        return right_element

    
    most_common_element = CommonElement(array)

    element_count = most_common_element[0][1] #Getting the frequency of the element
    percent = element_count/len(array)
    if percent >= .6:
        return most_common_element[0][0] #Returning the value of the element
    else:
        return None

array = [10,9,10,10,5,10,10,10,12,42,10,10,44,10,23,10] #Correctly Returns 10
array = [10,9,10,8,5,10,10,10,12,42,10,12,44,10,23,5] #Correctly Returns None

result = func(array)
print(result)

This function works but it's in O(n log(n)). I want to implement an algorithm that's O(n)

The recursion function for my algorithm is T(n) = 2T(n/2) + O(n). I think the goal is to eliminate the need to find frequency, which takes O(n). Any thoughts?

divide-and-conquer time-complexity list algorithm python
3 Answers

You can create a frequency counter for all elements in the list one time in O(n). Then, iterate the lookup table and see if any are at least 60% of the elements (in other words, count / len(lst) >= 0.6).

>>> from collections import Counter
>>> L = [4, 2, 3, 2, 4, 4, 4]
>>> Counter(L)
Counter({4: 4, 2: 1, 3: 1})
>>> Counter(L).most_common(1)
[(4, 4)]
>>> item, count = Counter(L).most_common(1)[0]
>>> count / len(L)
0.6666666666666666
>>> count / len(L) >= 0.6
True

Divide & conquer is a creative, but inappropriate, approach for this problem.

...or so I thought, but see this answer.

user_62433520

If you are guaranteed to have a list 60% of which is a given number, that number is guaranteed to be the median. To see this intuitively, sort the list. The number in question represents a contiguous window that is 60% of the length of the list. There is no way to place that window so that it doesn't cover the middle.

There are plenty of divide-and-conquer algorithms for finding the median. A common one is called introselect. You can find an implementation in numpy's partition and argpartition functions (it's written in C). The basic idea is to do quicksort, but only recurse into the portion that contains the index you care about. This reduces the algorithm to O(n).

By the way, you could search for any index between 40% and 60% of the length of the list. 50% seems like a reasonable middle ground.

To verify that the median appears > 60% of the time, run a single loop over the array, counting the number of times the median appears.

user_29887300

There's a pretty simple algorithm for finding the majority element of a collection, if the collection has one:

def majority(l):
    count, candidate = 0, None
    for element in l:
        if count == 0:
            count, candidate = 1, element
        elif element == candidate:
            count += 1
        else:
            count -= 1
    return candidate

This algorithm essentially pairs each element of the input against another element with a different value until all unpaired elements have the same value, then returns that value. If the input has a majority element, the algorithm must return that.

You can compute a candidate with this algorithm, then make another pass through the input and see if that candidate is a 60% supermajority. This works in O(1) space and O(n) time without mutating the input, while hash-based or introselect-based algorithms would need more space or mutate the input. It's also immune to hash collision attacks (unlike Counter and other hash-based approaches) and doesn't require elements to have an order relation (unlike introselect).

user_23571120
Related