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
  • Nico
  • Tanuj Sharma
  • M. Rahil Rafiq

    java Solution (100 out of 100 points )

    public static int solution(int[] A){
    int arrLength = 0;
    arrLength = A.length;
    if(arrLength == 0) return -1;
    int temp=0;
    List list = null;
    Map<Integer, List> valMap = new HashMap<Integer, List>();
    for(int i = 0; i < A.length; i++){
    temp = A[i];
    if(valMap.containsKey(temp)){
    list = new ArrayList();
    list = valMap.get(temp);
    list.add(i);
    valMap.put(temp, list);
    }else{
    list = new ArrayList();
    list.add(i);
    valMap.put(temp, list);
    }

    }
    int maxValKey = 0;
    int valuCount = 0;
    for(Map.Entry<Integer, List> val : valMap.entrySet()){
    if(valuCount < val.getValue().size()){
    valuCount = val.getValue().size();
    maxValKey = val.getKey();
    }
    }

    //Check if values of repeating number is greater than half of the array
    double halfVal = (A.length)/2;
    double valueofMax = valuCount;
    if(halfVal < valueofMax){
    return valMap.get(maxValKey).get(0);
    }else{
    return -1;
    }

    }