Tasks Details
medium
Given a list of integers, return the maximum number of consecutive integers equal to each other after replacing at most K of them.
Task Score
100%
Correctness
100%
Performance
100%
There are N obligatory books in a school program syllabus. The program also defines the order in which books should be read. Each book comes from a specific age, such as the enlightenment or the baroque period. The more books in a row the students read from any given age, the more they learn about it. Moreover, if they read a book from a different age, they will get distracted.
Teachers are allowed to replace K books from the program with alternatives. They want students to learn as much as possible from a single age (although they have not picked a particular specific age). The amount learned can be measured by the number of consecutive books from the same age read by the students. What is the maximum number of consecutive books from the same age after replacing at most K of them?
Note that the new books (after replacement) can be any books from the chosen age. They do not need to be listed in the syllabus, so the teacher can always find K books from the same age.
Write a function:
def solution(A, K)
that, given an array of integers A of length N, representing the ages of consecutive books from the school program syllabus, and an integer K, returns the maximum number of consecutive books from the same age after replacing at most K of them.
Examples:
1. Given A = [1, 1, 3, 4, 3, 3, 4] and K = 2, the function should return 5. Teachers can replace books from age 4 with books from age 3.
2. Given A = [4, 5, 5, 4, 2, 2, 4] and K = 0, the function should return 2. Teachers are not allowed to replace any books.
3. Given A = [1, 3, 3, 2] and K = 2, the function should return 4. Teachers can replace all the books from other ages with books from age 3.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- K is an integer within the range [0..N];
- each element of array A is an integer within the range [1..100,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 7 minutes
Notes
not defined yet
Code: 23:38:47 UTC,
java,
autosave
Code: 23:41:50 UTC,
py,
autosave
Code: 23:42:20 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start = 0
max_rep_len = 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - win
Code: 23:42:30 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start = 0
max_rep_len = 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1
Code: 23:43:01 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start = 0
max_rep_len = 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > k:
last_seen_occ[window_start) -= 1
window_start += 1
max_len = max(max_len,
Code: 23:43:21 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start = 0
max_rep_len = 0
max_len = 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > k:
last_seen_occ[window_start) -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Code: 23:43:42 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start, max_rep_len, max_len = 0, 0, 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > k:
last_seen_occ[window_start) -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Code: 23:43:56 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start, max_rep_len, max_len = 0, 0, 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > k:
last_seen_occ[window_start] -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Code: 23:43:58 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start, max_rep_len, max_len = 0, 0, 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > k:
last_seen_occ[window_start] -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 133, in <module>
main()
File "exec.py", line 95, in main
result = solution( A, K )
File "/tmp/solution.py", line 13, in solution
if (index - window_start + 1 - max_rep_len) > k:
NameError: name 'k' is not defined
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 133, in <module>
main()
File "exec.py", line 95, in main
result = solution( A, K )
File "/tmp/solution.py", line 13, in solution
if (index - window_start + 1 - max_rep_len) > k:
NameError: name 'k' is not defined
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 133, in <module>
main()
File "exec.py", line 95, in main
result = solution( A, K )
File "/tmp/solution.py", line 13, in solution
if (index - window_start + 1 - max_rep_len) > k:
NameError: name 'k' is not defined
Code: 23:44:05 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start, max_rep_len, max_len = 0, 0, 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > K:
last_seen_occ[window_start] -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Analysis
Code: 23:45:29 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start, max_rep_len, max_len = 0, 0, 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > K:
last_seen_occ[Awindow_start] -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Code: 23:45:33 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start, max_rep_len, max_len = 0, 0, 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > K:
last_seen_occ[A[window_start]] -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Analysis
Code: 23:45:38 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start, max_rep_len, max_len = 0, 0, 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > K:
last_seen_occ[A[window_start]] -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Analysis
Code: 23:45:40 UTC,
py,
final,
score:
100
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, K):
# write your code in Python 3.6
import collections
last_seen_occ = collections.defaultdict(int)
window_start, max_rep_len, max_len = 0, 0, 0
for index, val in enumerate(A):
last_seen_occ[val] += 1
max_rep_len = max(max_rep_len, last_seen_occ[val])
if (index - window_start + 1 - max_rep_len) > K:
last_seen_occ[A[window_start]] -= 1
window_start += 1
max_len = max(max_len, index - window_start + 1)
return max_len
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
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
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
start_with_wrong
Tests where best interval does not start or does not end with book which should be chosen for optimal result
Tests where best interval does not start or does not end with book which should be chosen for optimal result
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
expand all
Correctness/performance tests
least_common_age_dominates
Tests where the overall least common age dominates the best interval.
Tests where the overall least common age dominates the best interval.
✔
OK
1.
0.040 s
OK
2.
0.040 s
OK
3.
0.068 s
OK
1.
0.224 s
OK
2.
0.216 s
OK
3.
0.236 s
OK
4.
0.236 s
OK
1.
0.220 s
OK
2.
0.224 s
OK
3.
0.252 s
OK
4.
0.236 s
OK
1.
0.256 s
OK
2.
0.224 s
OK
expand all
Performance tests
1.
0.036 s
OK
2.
0.036 s
OK
semilarge_random
Semi-large random tests to distinguish between O(n**2) and O(nlog**2) solutions.
Semi-large random tests to distinguish between O(n**2) and O(nlog**2) solutions.
✔
OK
1.
0.048 s
OK
2.
0.052 s
OK
3.
0.060 s
OK
1.
0.040 s
OK
1.
0.240 s
OK
2.
0.240 s
OK
3.
0.264 s
OK