Codility ‘Dominator’ Solution

Short Problem Definition:

Find an index of an array such that its value occurs at more than half of indices in the array.

Link

Dominator

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1)

Execution:

As explained in the training material…

Solution:
def solution(A):
    candidate_ele = ''
    candidate_cnt = 0
    
    for value in A:
        if candidate_ele == '':
            candidate_ele = value
            candidate_cnt = 1
        else:
            if value != candidate_ele:
                candidate_cnt -= 1
                if candidate_cnt == 0:
                    candidate_ele = ''
            else:
                candidate_cnt += 1
        
    if candidate_cnt == 0:
        return -1
        
    cnt = 0
    last_idx = 0
    
    for idx, value in enumerate(A):
        if value == candidate_ele:
            cnt += 1
            last_idx = idx
            
    if cnt > len(A)//2:
        return last_idx
        
    return -1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin