Given an array, find all its elements that can become a leader I was successful in solving a challenge in codility, but my solution failed performance tests. How can I improve my solution?


  Challenge:
  
  Integers K, M and a non-empty array A consisting of N integers, not
  bigger than M, are given.
  
  The leader of the array is a value that occurs in more than half of
  the elements of the array, and the segment of the array is a sequence
  of consecutive elements of the array.
  
  You can modify A by choosing exactly one segment of length K and
  increasing by 1 every element within that segment.
  
  The goal is to find all of the numbers that may become a leader after
  performing exactly one array modification as described above.
  
  Write a function:

def solution(K, M, A)

  
  that, given integers K and M and an array A consisting of N integers,
  returns an array of all numbers that can become a leader, after
  increasing by 1 every element of exactly one segment of A of length K.
  The returned array should be sorted in ascending order, and if there
  is no number that can become a leader, you should return an empty
  array. Moreover, if there are multiple ways of choosing a segment to
  turn some number into a leader, then this particular number should
  appear in an output array only once.
  
  For example, given integers K = 3, M = 5 and the following array A:

A[0] = 2
A[1] = 1
A[2] = 3
A[3] = 1
A[4] = 2
A[5] = 2
A[6] = 3

  
  the function should return [2, 3]. If we choose segment A[1], A[2],
  A[3] then we get the following array A:

A[0] = 2
A[1] = 2
A[2] = 4
A[3] = 2
A[4] = 2
A[5] = 2
A[6] = 3

  
  and 2 is the leader of this array. If we choose A[3], A[4], A[5] then
  A will appear as follows:

A[0] = 2
A[1] = 1
A[2] = 3
A[3] = 2
A[4] = 3
A[5] = 3
A[6] = 3

  
  and 3 will be the leader.
  
  And, for example, given integers K = 4, M = 2 and the following array:

A[0] = 1
A[1] = 2
A[2] = 2
A[3] = 1
A[4] = 2

  
  the function should return [2, 3], because choosing a segment A[0],
  A[1], A[2], A[3] and A[1], A[2], A[3], A[4] turns 2 and 3 into the
  leaders, respectively.
  
  Write an efficient algorithm for the following assumptions:
  
  
  N and M are integers within the range [1..100,000];
  K is an integer within the range [1..N];
  Each element of array A is an integer within the range [1..M].
  


My Solution

def modify(segment):
   return [e+1 for e in segment]

def dominant(A):
   d = dict()
   lenOfHalfA = int(len(A)/2)
   domList = []

   for i in A:
       if not i in d:
           d[i] = 1
       else:
           d[i] = d[i]+1

   for key, value in d.items():
       if value &gt; lenOfHalfA:
           domList.append(key)

   return domList


def solution(K, M, A):
   # write your code in Python 3.6
   dominantList = []

   x = 0
   while x &lt;= len(A) - K:
       modifiedA = A[:]
       modifiedA[x:K+x] = modify(A[x:K+x])
       dominantList += dominant(modifiedA)
       x += 1

   return list(set(dominantList))
def modify(segment):
   return [e+1 for e in segment]


This function is used only in one place, and is only one line. That often means it's better to just inline it:

modifiedA[x:K+x] = modify(A[x:K+x])
# Becomes:
modifiedA[x:K+x] = [e+1 for e in A[x:K+x]]


Use meaningful variable names. No matter what your challenge says, K, M and A are not meaningful variable names. It also seems like you're not doing anything with that M, so why do we even pass it to the function?

In your dominant() function, you look like you want to use collections.Counter. For practice with a language it can be good to check how to set it up yourself, but sometimes we have a good solution ready-made and available, and much better tested than any individual developer could ever do.

With Counter, you can make it work like this:

from collections import Counter

def dominant(string):
    count = Counter(string)
    return [key for key, value in count.items() if value == count.most_common(1)[0][1]]


Yeah, it's as simple as that. You could split it out over multiple lines, for clarity:

from collections import Counter

def dominant(string):
    count = Counter(string)
    dom_list = []
    max_occurred = count.most_common(1)[0][1]
    for key, value in count.items():
        if value &gt;= max_occurred:
            dom_list.append(key)
    return dom_list