3
\$\begingroup\$

I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in \$ O(n \log n)\$. The majority element is defined as the element with number of repetitions more than half the length of the input list.

The stated solution for that problem was to find the majority element in the two sub-lists which will be the majority element of the entire list.

I don't know how this is supposed to work if the input list is \$ [1,1,1,5,5] \$ where the two sub-lists would be \$ [1,1,1] \$ and \$ [1,5,5] \$ yielding two different majority elements, so I came up with another solution.

The recurrence relation for the Divide and Conquer part is $$ T(n) = 2 T\left(\dfrac{n}{2}\right)+O(n) $$ which is \$ O(n \log n) \$ and an extra \$ O(n) \$ for iterating on the resulting list of tuples after the divide and conquer terminates.


What do you guys think about the performance and efficiency of this algorithm, I know I could have sorted at first in \$ O(n \log n)\$ and then do this same iteration in \$ O(n) \$, but I wanted to come up with new way of solving it.

What do you also think about the supposedly correct answer for the problem of finding the majority element in each sub-list, is it possible, and how can you code it if yes ?!

def element_repetitions(lst):
    """
    This function is used to determine the number of repetitions of each element in the input list
    :param lst: A list of positive integers.
    :return: A sorted list of tuples, each tuple representing an element in the
    input lst and the number of repetitions of this element.
    """
    n = len(lst)
    if n == 1:
        return [(lst[0], 1)]
    first_half = element_repetitions(lst[:n // 2])
    second_half = element_repetitions(lst[n // 2:])
    return merge_the_tuples(first_half, second_half)


def merge_the_tuples(lst1, lst2):
    """
    This function sorts and merges the two input list of tuples.
    It iterates on both of the input lists with a technique similar to that used in
    the merging function of the merge sort, but if both of the elements are equal, only one instance
    of the element is added as the first element of the tuple, and the sum of their repetitions is added as the
    second element of the tuple.

    :param lst1: A sorted list of tuples, each tuple has a unique element, and the number of repetitions of
    this element.
    :param lst2: The other sorted list of tuples.
    :return: A merged list of tuples.
    """
    list_of_tuples = []
    i, j = 0, 0
    while i < len(lst1) and j < len(lst2):
        if lst1[i][0] < lst2[j][0]:
            list_of_tuples.append(lst1[i])
            i += 1
        elif lst1[i][0] > lst2[j][0]:
            list_of_tuples.append(lst2[j])
            j += 1
        elif lst1[i][0] == lst2[j][0]:
            list_of_tuples.append((lst1[i][0], lst1[i][1] + lst2[j][1]))
            i += 1
            j += 1
    return list_of_tuples + lst1[i:] + lst2[j:]


def majority_element(lst):
    """
    Iterates over the resulting list of tuples from element_repetitions(), returning the element with repetitions
    more than half the length of the input list.
    :param lst: A list of integers > 0
    :return: The majority element if present, else 0
    """
    element_repetition_list = element_repetitions(lst)
    for element_repetition in element_repetition_list:
        if element_repetition[1] >= len(lst) // 2 + 1:
            return element_repetition[0]
    return 0

print(majority_element([1, 1, 1, 5, 5])) outputs 1

print(majority_element([1, 3, 4, 1, 2, 6, 2, 1, 1, 1])) outputs 0

\$\endgroup\$
  • \$\begingroup\$ This is not a review of your code (which is why it's not an answer) but a comment on your problem with the stated solution. If it comes to it, you can afford within the O(n log(n)) time bound to count occurences of both candidates in the section under consideration. There are more elegant options (in fact there is a linear time algorithm available for this problem described here: en.wikipedia.org/wiki/…) but I think going back and counting would at least have met your requirements. \$\endgroup\$ – Josiah Apr 21 '18 at 22:28
  • 1
    \$\begingroup\$ when the majority element of both sublists is not the same, you need to ount the occurences of each in the other sublist to know if there is a global majority element. It is explained in detail here stackoverflow.com/a/28960878/3308055 \$\endgroup\$ – juvian Apr 22 '18 at 4:00
  • \$\begingroup\$ docs.python.org/3/library/… \$\endgroup\$ – Maarten Fabré Apr 22 '18 at 9:58

Your Answer

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

Browse other questions tagged or ask your own question.