How solve Codility equiLeader challenge

Question

After finding the "leader" I tried finding the possible equiLeaders in the given array but couldn't. Tried to find a solution of someone else but can't wrap my head around what he did.

I left a comment on the part I am lost in his code. can someone who gets it kindly walk me through that part. especially with those calculations

this is his solution

function solution(A) {
    // I understand this part as he was trying to find the leader
    if (A.length === 1) return 0
    let maxRepetition = 1;
    let maxIndex = -1
    let occurance = new Object()
    for (let i = 0; i < A.length; i++) {
        if (occurance.hasOwnProperty(A[i])) {
            occurance[A[i]][0]++
            if (occurance[A[i]][0] > maxRepetition) {
                if (occurance[A[i]][0] > A.length / 2) {
                    maxRepetition = occurance[A[i]][0]
                    maxIndex = occurance[A[i]][1]
                }
            }
        }
        else {
            occurance[A[i]] = new Array()

            occurance[A[i]][0] = 1
            occurance[A[i]][1] = i
        }
    }

    leader = A[maxIndex]


    // THis is the part I am not getting where he was trying to get the possible equiLeaders

    let equiLeader = 0
    let stack = []
    let stackIndex = -1
    for (let i = 0; i < A.length; i++) {

        if (stack.length > (Math.floor(i / 2)) && (maxRepetition - stack.length > Math.floor((A.length - i) / 2))) {
            equiLeader++
        }
        if (A[i] === leader) stack.push(i)

    }


    return equiLeader

}

this is the full question

A non-empty array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

For example, given array A such that: A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

we can find two equi leaders:

    0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
    2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

The goal is to count the number of equi leaders.

Write a function:

function solution(A);

that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

For example, given: A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

the function should return 2, as explained above.

Write an efficient algorithm for the following assumptions:

    N is an integer within the range [1..100,000];
    each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

Answer 1

I think we can all agree that the most difficult part to understand is this part

if (stack.length > (Math.floor(i / 2)) &&
   (maxRepetition - stack.length > Math.floor((A.length - i) / 2))) {
        equiLeader++
   }

I'm going to rename maxRepetition as countOfLeadingValues, since it is the number of leading values that exist in the entire array/list. Take the simple example

[2,4,4,4,4,4,6]

Then countOfLeadingValues == 5

I'm also going to move

if (A[i] === leader) stack.push(i)

above the problematic line, since it makes more sense that way. We're pushing to the stack when the current element equals the leader value (in this example 4).

Looking at the first condition

stack.length > (Math.floor(i / 2))

What's happening here is that we're ensuring that the current stack has at least half of the elements equal to the leading value (i.e. otherwise it wouldn't be an equileader)

so

2,4

will be false (if 4 is the leading value in the array)

but

2,4,4

will be true (if 4 is the leading value in the array), so this will be an equileader, since its dominant value is also the leading value.

In the second condition

countOfLeadingValues - stack.length > Math.floor((A.length - i) / 2)

on the left hand side,

countOfLeadingValues - stack.length

will get progressively smaller as we traverse the array/list, since the first term is constant (5 in the example) and the second is incrementing with each equileader match (every element that is 4). We want to check that the stack is not yet at the total number of leading values.

Then

Math.floor((A.length - i) / 2)

will get progressively larger as we approach the end of the array. We haven't gone over the halfway of the array, so we're being as efficient as possible, not exhaustive. From the learning materials of Codility:

if it is greater than n/2 then we have found the leader; otherwise the sequence does not contain a leader

Answer 2

Answer in C++ with 100% result.

int solution(vector<int> &A){

    // write your code in C++14 (g++ 6.2.0)
    int leader,leadercnt=0,element=0,cnt=0,leaderfound=0,seq=0,candidate=0;
    for(uint i=0;i<A.size();i++)
    {
        if(cnt == 0)
        {
            element = A[i];
            cnt++;
        }
        else
        {
            if(A[i]!=element)
            {
                cnt--;
            }
            else
            {
                cnt++;
            }
        }
    }
    if(cnt>0)
    {
        candidate=element;
        leadercnt=cnt;
        
    }
    cnt=0;
    for(uint i=0;i<A.size();i++)
    {
        if(candidate==A[i])
        {
            cnt++;
        }
    }
    if(cnt>(int)A.size()/2)
    {
        leaderfound=1;
        leader = candidate;   
        leadercnt =  cnt;   
    }
    if(leaderfound == 0)
    {
        //printf("Return 0 no leader found\n");
        return 0;
    }

    int nonleadercntr=A.size()-leadercnt;
    int nonleadercntl=0;
    int leadercntr=leadercnt;
    int leadercntl=0;
    //printf("Found leader %d and leadercnt %d\n",leader,leadercnt);
    for(uint i=0;i<A.size();i++)
    {
        if(A[i]==leader)
        {
            leadercntl++;
            leadercntr--;
        }
        else
        {
            nonleadercntl++;
            nonleadercntr--;
        }
        if((leadercntl > nonleadercntl) && (leadercntr > nonleadercntr))
        {
            seq++;
        }
    }
    return seq;

}

Answer 3

This is my solution Java. Result 100% and O(N). The first part of the code is to find (if any) the most frequent number in the array (max) and the number of its occurrences (maxCount).

Then the algorithm counts the number of occurrences of the situations indicated in the task. The key condition is:

if((leaderCount>((S+1)/2)) && ((maxCount - leaderCount) > (N - (S+1))/2))

It checks if array divided into two subarrays contains a leader more than half the length of the subarray times.

import java.util.*;

class Solution {
    public int solution(int[] A) {                      
        Map <Integer, Integer> map = new HashMap<>();
        int N = A.length;
        for(int i=0; i<N; i++) {
            if(map.containsKey(A[i])) {
                map.put(A[i], map.get(A[i]) + 1);
            } else {
                map.put(A[i], 1);
            }
        }
        int max = 0;
        int maxCount= 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(maxCount < entry.getValue()) {
                maxCount = entry.getValue();
                max = entry.getKey();
            }
        }
        
        if(maxCount <= N/2) {
            return 0;
        }
    
        int leaderCount = 0;
        int equiCounter = 0; 
        for(int S=0; S<N-1; S++) {
            if(A[S] == max) {
                leaderCount++;
            }
            if((leaderCount>((S+1)/2)) && ((maxCount - leaderCount) > (N - (S+1))/2)) {
                equiCounter++;
            }
        }
        
        return equiCounter;

    }
}

Answer 4

This is my solution in C++. I solved that using prefix sum additionally. Hope it helps other people to understand it.

#include <unordered_map>

int getSlice(vector<int>& pf, int start, int end) {
    return pf[end + 1] - pf[start];
}

int solution(vector<int> &A) {
    // get leader
    unordered_map<int, int> mp;
    int N = A.size();
    int leader = 0;
    for (int i = 0; i < N; ++i) {
        mp[A[i]]++;
        if (mp[A[i]] > N / 2) {
            leader = A[i];
            break;
        }
    }

// count leaders
vector<int> pf (N + 1, 0);
pf[0] = 0;
for (int i = 1; i < N + 1; ++i) {
    if (A[i - 1] == leader)
        pf[i] = pf[i - 1] + 1;
    else
        pf[i] = pf[i - 1];
}

// Check if the leader occurs in more than the half of each slice size
int eqLeader = 0;
for (int i = 0; i < N; ++i) {
    int left = getSlice(pf, 0, i);
    int right = getSlice(pf, i + 1, N - 1);

    double halfLeft = (double) (i + 1) / 2;
    double halfRight = (double) ((N - 1) - i) / 2;

    if (left > halfLeft && right > halfRight) {
        eqLeader++;
    }
}
return eqLeader;
}

Answer 5

Here is the final version of my solution with time complexity O(N) and %100 correctness:

from collections import deque

def solution(A):

 stack=deque()
 n=len(A)
 leader=None
 leader_count=0
 for i in range(n):
     if(len(stack)==0):
         stack.append(A[i])
     else:
         if(stack[-1]!=A[i]):
             stack.pop()
         else:
             stack.append(A[i])
 if(len(stack)>0):
     leader=stack[0]
 for i in range(n):
     if(A[i]==leader):
         leader_count+=1
 if(leader_count<=n//2):
     return 0
 else:
     equi_leaders = 0
     leader_count_so_far = 0
     for index in range(n):
         if A[index] == leader:
             leader_count_so_far += 1
         if leader_count_so_far > (index+1)//2 and \
         leader_count-leader_count_so_far > (n-index-1)//2:
              # Both the head and tail have leaders of the same value
             # as "leader"
             equi_leaders += 1
     return equi_leaders

Answer 6

Here is my solution with O(N**2) but 100% correctness:

def leader(A):
    stack=deque()
    n=len(A)
    leader=-1
    counter=0
    leader_index=-1
    for i in range(n):
        if(len(stack)==0):
            stack.append(A[i])
        else:
            if(stack[-1]!=A[i]):
                stack.pop()
            else:
                stack.append(A[i])
    
    if(len(stack)>0):
        leader=stack[0]
    for i in range(n):
        if(A[i]==leader):
            counter+=1
            leader_index=i
    if(counter>n//2):
        return leader,leader_index
    else:
        return (-1,-1)

    def solution1(A):
    n=len(A)
    counter=0
    for i in range(n):
        L1,i1=leader(A[0:i+1])
        L2,i2=leader(A[i+1:n])
        print("{},{}=> ({},{}) and ({},{})".format(A[0:i+1],A[i+1:n],L1,i1,L2,i2))
        if(i1!=-1 and i2!=-1 and L1==L2):
            counter+=1
            #print("find")
    return counter

Answer 7

I found a solution, it's very simple, if we can find a max occurs of any element and by the second loop just divide into two can produce the right result.

This is the code using Javascript, please have look.

function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
 let totalEleFound = {};
for(let i=0;i<A.length;i++){
    if(!totalEleFound[ A[i] ]){
        totalEleFound[ A[i] ] = 1;
    }
    else{
        totalEleFound[ A[i] ]++;
    }

}

//console.log("totalEleFound",totalEleFound);
let maxOccures = 0;
for(const [key,value] of Object.entries(totalEleFound) ){
    maxOccures = Math.max(maxOccures,Math.floor(value/2))
}

return maxOccures;
}

Have a happy coding, Cheers.

Answer 8

This is a 100% O(N) solution for javascript, for getting the leader I use the fastest technique they suggest on the docs:

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)

  const { leader, leaderCount } = getLeader(A);

  if (leader == undefined) {
    return 0;
  }

  let countEquiLeaders = 0;
  let currentLeaderCount = 0;

  for (let i = 0; i < A.length; i++) {
    if (A[i] == leader) {
      currentLeaderCount++;
    }
    if (i < A.length - 1) {
      if (
        currentLeaderCount > (i + 1) / 2 &&
        leaderCount - currentLeaderCount > (A.length - i - 1) / 2
      ) {
        countEquiLeaders++;
      }
    }
  }

  return countEquiLeaders;
}

function getLeader(A) {
  const stack = [];

  for (let i = 0; i < A.length; i++) {
    const currentElement = A[i];

    stack.push(currentElement);

    const lastStackElement = stack[stack.length - 1];
    const penultimateStackElement = stack[stack.length - 2];

    if (
      penultimateStackElement != undefined &&
      lastStackElement != penultimateStackElement
    ) {
      stack.pop();
      stack.pop();
    }
  }
  const possibleLeader = stack.pop();

  let leaderCount = 0;

  for (let i = 0; i < A.length; i++) {
    const currentElement = A[i];

    if (possibleLeader == currentElement) {
      leaderCount++;
    }
  }
  if (leaderCount > A.length / 2) {
    return { leader: possibleLeader, leaderCount };
  }
  return {};
}

Answer 9

function solution(A) {
  // there is only one leader because its counts > n/2
  // 1. find it
  var n = A.length;
  var freq = {};
  var leader =-1;
  for(let i = 0; i < n; i++){
    freq[A[i]]?freq[A[i]]++:freq[A[i]]=1;
    if(freq[A[i]] * 2 > n) { 
      leader = i;
      break;
    }
  }
  // 2. count the occurances of leader up to each i
  // so you can know how many of it is to the left and how many to the right
  var counts = [];
  var occurances = 0;
  for(let i = 0; i < n; i++){
    if(A[i]==A[leader]) occurances++;
    counts[i] = occurances;
  }

  // 3. get equiLeaders 
  // now you know the counts to the left of i = counts[i] and to the right of i = maxCounts-countsUpToI
  // apply the equation and if it is satisified for both sides then this index is at equiLeader so increment the result.
  // note i+1/2 is equivalent to what is written. (multiplication is better so no losing of precision happens)
  var equiLeaders = 0;
  for(let i = 0; i < n; i++){
    if(counts[i] * 2 > i+1 && (counts[counts.length-1] - counts[i] )* 2 > n-i-1) 
      equiLeaders++;
  }

  return equiLeaders;
}

Answer 10

Python solution with O(n) and 100% in Codility.

def solution(A):
# write your code in Python 3.6
dic = {}
equileader = 0
leader_cnt = 0

for i in A:
    if i in dic:
        dic[i] +=1
        if dic[i] > leader_cnt:
            leader_cnt = dic[i]
            leader = i
    else :
        dic[i]=1

if leader_cnt<=len(A)/2:
    return 0

left = 0
right = leader_cnt
for ix, i in enumerate(A):
    if i == leader:
        left+=1
        right-=1
    if left>(ix+1)/2 and right> (len(A)-ix-1)/2:
        equileader +=1
return equileader

Answer 11

Java solution,100% and O(N). first of all, find the candidate value and how many times it appears in the array. secondly, check the first subarray and second subarray to calculate the result.

public static int solution(int[] A) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < A.length; i++) {
        map.put(A[i], map.getOrDefault(A[i], 0) + 1);
    }
    int candidate = Integer.MAX_VALUE;
    int maxTimes = Integer.MAX_VALUE;
    for (HashMap.Entry<Integer, Integer> m : map.entrySet()) {
        int value = m.getValue();
        int key = m.getKey();
        if (value > A.length / 2) {
            candidate = key;
            maxTimes = value;
        }
    }
    int first = 0;// the num for candidate display in the first subarray
    int firstCount = 0;// the total count in the first subarray
    int second = maxTimes;
    int secondCount = A.length;
    int result = 0;
    for (int i = 0; i < A.length; i++) {
        firstCount++;
        secondCount--;
        if (A[i] == candidate) {
            first++;
            second--;
        }
        if (first > firstCount / 2 && second > secondCount / 2) {
            result++;
        }
    }
    return result;
}

Answer 12

Python Solution: O(N), 100%

from itertools import groupby

def solution(A):
    groups = [(i, len(list(j))) for i, j in groupby(sorted(A))]
    n = len(A)
    lead_count = max(groups, key=lambda t: t[1])[1]
    if lead_count <= (n/2): return 0  # not possible
    leader = max(groups, key=lambda t: t[1])[0]
    count = 0
    equi_leaders = 0
    for i in range(n):
        if A[i] == leader: count += 1
        right = lead_count - count
        if count > (i+1)/2 and right > (n-i-1)/2:
        equi_leaders += 1
    return equi_leaders