Tasks Details
hard
Given an array, find all its elements that can become a leader, after increasing by 1 all of the numbers in some segment of a given length.
Task Score
100%
Correctness
100%
Performance
100%
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] = 3the 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] = 3and 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] = 3and 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] = 2the 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].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 3 minutes
Notes
not defined yet
Code: 06:54:45 UTC,
java,
autosave
Code: 06:56:26 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
minCount = len(A)//2
for i in range(K):
A[i] += 1
d = {}
for x in A:
d[x] = d.get(x,0) + 1
h = MaxHeap(len(A)*2)
ret = set()
for val,count in d.items():
h.insert(count,val)
count, val = h.q[1]
if count > minCount:
ret.add(val)
for i in range(K, len(A)):
#change A[i-K] to A[i-K] - 1
h.decrease(A[i-K])
A[i-K] -= 1
h.increase(A[i-K])
#change A[i] to A[i]+1
h.decrease(A[i])
A[i] += 1
h.increase(A[i])
count, val = h.q[1]
if count > minCount:
ret.add(val)
ret = list(ret)
ret.sort()
return ret
Code: 06:56:36 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
minCount = len(A)//2
for i in range(K):
A[i] += 1
d = {}
for x in A:
d[x] = d.get(x,0) + 1
h = MaxHeap(len(A)*2)
ret = set()
for val,count in d.items():
h.insert(count,val)
count, val = h.q[1]
if count > minCount:
ret.add(val)
for i in range(K, len(A)):
#change A[i-K] to A[i-K] - 1
h.decrease(A[i-K])
A[i-K] -= 1
h.increase(A[i-K])
#change A[i] to A[i]+1
h.decrease(A[i])
A[i] += 1
h.increase(A[i])
count, val = h.q[1]
if count > minCount:
ret.add(val)
ret = list(ret)
ret.sort()
return ret
class MaxHeap:
def __init__(self,n):
self.q = [None]*(n+1)
self.count = 0
self.pos = {}
def insert(self, c, v):
self.count += 1
self.q[self.count] = (c,v)
self.pos[v] = self.count
self.swim(self.count)
def increase(self, val):
if val not in self.pos:
self.insert(1, val)
else:
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count+1, val)
self.swim(pos)
def decrease(self, val):
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count-1, val)
self.sink(pos)
def swim(self, k):
q = self.q
pos = self.pos
while (k > 1 and q[k//2] < q[k]):
up = k//2
q[up], q[k] = q[k], q[up]
pos[q[up][1]] = up
pos[q[k][1]] = k
k = up
def sink(self, k):
q = self.q
pos = self.pos
while (2*k <= self.count):
j = 2*k;
if j < self.count and q[j] < q[j+1]: j += 1
if q[k] >= q[j]: break
q[k], q[j] = q[j], q[k]
pos[q[k][1]] = k
pos[q[j][1]] = j
k = j
Code: 06:56:49 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
minCount = len(A)//2
for i in range(K):
A[i] += 1
d = {}
for x in A:
d[x] = d.get(x,0) + 1
h = MaxHeap(len(A)*2)
ret = set()
for val,count in d.items():
h.insert(count,val)
count, val = h.q[1]
if count > minCount:
ret.add(val)
for i in range(K, len(A)):
#change A[i-K] to A[i-K] - 1
h.decrease(A[i-K])
A[i-K] -= 1
h.increase(A[i-K])
#change A[i] to A[i]+1
h.decrease(A[i])
A[i] += 1
h.increase(A[i])
count, val = h.q[1]
if count > minCount:
ret.add(val)
ret = list(ret)
ret.sort()
return ret
class MaxHeap:
def __init__(self,n):
self.q = [None]*(n+1)
self.count = 0
self.pos = {}
def insert(self, c, v):
self.count += 1
self.q[self.count] = (c,v)
self.pos[v] = self.count
self.swim(self.count)
def increase(self, val):
if val not in self.pos:
self.insert(1, val)
else:
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count+1, val)
self.swim(pos)
def decrease(self, val):
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count-1, val)
self.sink(pos)
def swim(self, k):
q = self.q
pos = self.pos
while (k > 1 and q[k//2] < q[k]):
up = k//2
q[up], q[k] = q[k], q[up]
pos[q[up][1]] = up
pos[q[k][1]] = k
k = up
def sink(self, k):
q = self.q
pos = self.pos
while (2*k <= self.count):
j = 2*k;
if j < self.count and q[j] < q[j+1]: j += 1
if q[k] >= q[j]: break
q[k], q[j] = q[j], q[k]
pos[q[k][1]] = k
pos[q[j][1]] = j
k = j
Code: 06:56:51 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
minCount = len(A)//2
for i in range(K):
A[i] += 1
d = {}
for x in A:
d[x] = d.get(x,0) + 1
h = MaxHeap(len(A)*2)
ret = set()
for val,count in d.items():
h.insert(count,val)
count, val = h.q[1]
if count > minCount:
ret.add(val)
for i in range(K, len(A)):
#change A[i-K] to A[i-K] - 1
h.decrease(A[i-K])
A[i-K] -= 1
h.increase(A[i-K])
#change A[i] to A[i]+1
h.decrease(A[i])
A[i] += 1
h.increase(A[i])
count, val = h.q[1]
if count > minCount:
ret.add(val)
ret = list(ret)
ret.sort()
return ret
class MaxHeap:
def __init__(self,n):
self.q = [None]*(n+1)
self.count = 0
self.pos = {}
def insert(self, c, v):
self.count += 1
self.q[self.count] = (c,v)
self.pos[v] = self.count
self.swim(self.count)
def increase(self, val):
if val not in self.pos:
self.insert(1, val)
else:
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count+1, val)
self.swim(pos)
def decrease(self, val):
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count-1, val)
self.sink(pos)
def swim(self, k):
q = self.q
pos = self.pos
while (k > 1 and q[k//2] < q[k]):
up = k//2
q[up], q[k] = q[k], q[up]
pos[q[up][1]] = up
pos[q[k][1]] = k
k = up
def sink(self, k):
q = self.q
pos = self.pos
while (2*k <= self.count):
j = 2*k;
if j < self.count and q[j] < q[j+1]: j += 1
if q[k] >= q[j]: break
q[k], q[j] = q[j], q[k]
pos[q[k][1]] = k
pos[q[j][1]] = j
k = j
Analysis
User test case 1:
[3, 5, [2, 1, 3, 1, 2, 2, 3]]
User test case 2:
[4, 2, [1, 2, 2, 1, 2]]
Code: 06:56:58 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
minCount = len(A)//2
for i in range(K):
A[i] += 1
d = {}
for x in A:
d[x] = d.get(x,0) + 1
h = MaxHeap(len(A)*2)
ret = set()
for val,count in d.items():
h.insert(count,val)
count, val = h.q[1]
if count > minCount:
ret.add(val)
for i in range(K, len(A)):
#change A[i-K] to A[i-K] - 1
h.decrease(A[i-K])
A[i-K] -= 1
h.increase(A[i-K])
#change A[i] to A[i]+1
h.decrease(A[i])
A[i] += 1
h.increase(A[i])
count, val = h.q[1]
if count > minCount:
ret.add(val)
ret = list(ret)
ret.sort()
return ret
class MaxHeap:
def __init__(self,n):
self.q = [None]*(n+1)
self.count = 0
self.pos = {}
def insert(self, c, v):
self.count += 1
self.q[self.count] = (c,v)
self.pos[v] = self.count
self.swim(self.count)
def increase(self, val):
if val not in self.pos:
self.insert(1, val)
else:
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count+1, val)
self.swim(pos)
def decrease(self, val):
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count-1, val)
self.sink(pos)
def swim(self, k):
q = self.q
pos = self.pos
while (k > 1 and q[k//2] < q[k]):
up = k//2
q[up], q[k] = q[k], q[up]
pos[q[up][1]] = up
pos[q[k][1]] = k
k = up
def sink(self, k):
q = self.q
pos = self.pos
while (2*k <= self.count):
j = 2*k;
if j < self.count and q[j] < q[j+1]: j += 1
if q[k] >= q[j]: break
q[k], q[j] = q[j], q[k]
pos[q[k][1]] = k
pos[q[j][1]] = j
k = j
Analysis
User test case 1:
[3, 5, [2, 1, 3, 1, 2, 2, 3]]
User test case 2:
[4, 2, [1, 2, 2, 1, 2]]
Code: 06:57:00 UTC,
py,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(K, M, A):
minCount = len(A)//2
for i in range(K):
A[i] += 1
d = {}
for x in A:
d[x] = d.get(x,0) + 1
h = MaxHeap(len(A)*2)
ret = set()
for val,count in d.items():
h.insert(count,val)
count, val = h.q[1]
if count > minCount:
ret.add(val)
for i in range(K, len(A)):
#change A[i-K] to A[i-K] - 1
h.decrease(A[i-K])
A[i-K] -= 1
h.increase(A[i-K])
#change A[i] to A[i]+1
h.decrease(A[i])
A[i] += 1
h.increase(A[i])
count, val = h.q[1]
if count > minCount:
ret.add(val)
ret = list(ret)
ret.sort()
return ret
class MaxHeap:
def __init__(self,n):
self.q = [None]*(n+1)
self.count = 0
self.pos = {}
def insert(self, c, v):
self.count += 1
self.q[self.count] = (c,v)
self.pos[v] = self.count
self.swim(self.count)
def increase(self, val):
if val not in self.pos:
self.insert(1, val)
else:
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count+1, val)
self.swim(pos)
def decrease(self, val):
pos = self.pos[val]
count, val = self.q[pos]
self.q[pos] = (count-1, val)
self.sink(pos)
def swim(self, k):
q = self.q
pos = self.pos
while (k > 1 and q[k//2] < q[k]):
up = k//2
q[up], q[k] = q[k], q[up]
pos[q[up][1]] = up
pos[q[k][1]] = k
k = up
def sink(self, k):
q = self.q
pos = self.pos
while (2*k <= self.count):
j = 2*k;
if j < self.count and q[j] < q[j+1]: j += 1
if q[k] >= q[j]: break
q[k], q[j] = q[j], q[k]
pos[q[k][1]] = k
pos[q[j][1]] = j
k = jAnalysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M)
expand all
Correctness tests
1.
0.040 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
expand all
Performance tests
1.
0.088 s
OK
2.
0.104 s
OK
3.
0.100 s
OK
1.
0.192 s
OK
2.
0.112 s
OK
3.
0.116 s
OK
1.
0.720 s
OK
2.
0.676 s
OK
3.
0.716 s
OK
1.
0.168 s
OK
2.
0.352 s
OK