3
\$\begingroup\$

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 > lenOfHalfA: domList.append(key) return domList def solution(K, M, A): # write your code in Python 3.6 dominantList = [] x = 0 while x <= len(A) - K: modifiedA = A[:] modifiedA[x:K+x] = modify(A[x:K+x]) dominantList += dominant(modifiedA) x += 1 return list(set(dominantList))
\$\endgroup\$
4
  • \$\begingroup\$ This question might benefit from an example and it's output. That would make the workings a bit clearer than just text. \$\endgroup\$ Commented Oct 4, 2019 at 14:12
  • \$\begingroup\$ @Gloweye I have added some examples now. \$\endgroup\$ Commented Oct 4, 2019 at 18:21
  • \$\begingroup\$ yes, looks a lot easier to understand the purpose. I've suggested a few edits that show it more like python lists. So essentially, the "leader" is the most common number, and the output is the most common number in either the current array ( increasing a slice of length zero) or any array with a certain slice incremented. \$\endgroup\$ Commented Oct 4, 2019 at 22:13
  • \$\begingroup\$ Are you using list(set(dominantList)) to sort your list? \$\endgroup\$ Commented Apr 1, 2020 at 13:16

3 Answers 3

Reset to default
2
\$\begingroup\$

You can speed some things up by using more list and dict comprehensions, and by reducing your function calls. Some examples follow.

d = dict() vs d = {}: 131 ns vs 30 ns.

len_of_half_a = int(len(a)/2) vs len_of_half_a = len(a)//2: 201 ns vs 99 ns.

I used Python 3.8.1 for both tests.

Granted that this isn't much, but several of these tiny improvements could help you reach the target. You should see similar if not better performance increases by using list and dict comprehensions, e.g. for domList, d, and dominantList. And replacing your while x <= len(A) - K: with a range-based iterator should bump you up a little more.

And a final small note is that you should try to follow standards with your naming and ensure clear and obvious names. A is not a good name for a variable, nor is d, and python tends to use snake_case over camelCase.

\$\endgroup\$
2
\$\begingroup\$

Algorithm in O(N^2)

The current solution will be slow for large N, because it has a complexity of O(N^2) (It checks every element in the array for every possible position of the k adjusted elements => O(N * (N-K)) => O(N^2)).

There is an O(N) solution.

Consider that as the K-element segment "slides" along the array, there are only two elements whose value changes: the one entering and the one leaving the segment.

Something like:

def solution(K, M, A): threshold = len(A)//2 counts = Counter(A) # increment count for each element in the initial window for head in A[:K]: counts[head] -= 1 counts[head+1] += 1 # initial leaders leaders = set(k for k,v in counts.items() if v > threshold) # slide window along the array adjusting the counts for # elements that leave (tail) or enter (head) the window. # An element entering gets incremented, so # count[element] -= 1 and count[element+1] += 1. # It is the reverse for element leaving. for tail, head in zip(A, A[K:]): counts[tail] += 1 counts[tail + 1] -= 1 counts[head] -= 1 counts[head + 1] += 1 if counts[tail] > threshold: leaders.add(tail) if counts[head + 1] > threshold: leaders.add(head + 1) return leaders
\$\endgroup\$
1
  • \$\begingroup\$ What is Counter? \$\endgroup\$ Commented Mar 22, 2022 at 8:38
1
\$\begingroup\$ 
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 >= max_occurred: dom_list.append(key) return dom_list
\$\endgroup\$
4
  • 3
    \$\begingroup\$ That often means it's better to just inline it - In this case I agree, but in general I don't. Functions are cheap, and inlining for performance is about the last thing you should try. The modularity, testability and legibility that functions offer is important, and well worth the tiny performance hit. The only reason I agree here is that the purpose of the function isn't well-defined. \$\endgroup\$ Commented Oct 4, 2019 at 14:37
  • 1
    \$\begingroup\$ There's loads of cases where functions are appropriate, but it can also be premature optimization and/or a lot of scrolling to see what a line does. In my opinion, primary reason for functions is to avoid repetition, and secondary is to aid readability and make it easier to see what a block of code does. If there's no repetition to avoid and no readability gained with a function, then IMO it shouldn't exist. \$\endgroup\$ Commented Oct 4, 2019 at 14:46
  • \$\begingroup\$ Would inline here even give a speed increase? I was under the impression that lambda functions appear identical to normal (local) functions in the bytecode. \$\endgroup\$ Commented Apr 1, 2020 at 13:01
  • \$\begingroup\$ It should, but that's not important. The reason I suggested it is to make the code easier to read. \$\endgroup\$ Commented Apr 2, 2020 at 9:48

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.