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:
class Solution { public int[] solution(int K, int M, int[] 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 Java 21
Time spent on task 13 minutes
Notes
not defined yet
Code: 22:08:55 UTC,
java,
autosave
Code: 22:08:58 UTC,
swift4,
autosave
Code: 22:09:59 UTC,
swift4,
autosave
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> [Int] {
var leaders = Set<Int>()
var counts = [Int](repeating: 0, count: M + 2)
let leaderThereshold = A.count/2
}
Code: 22:17:55 UTC,
swift4,
autosave
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> [Int] {
var leaders = Set<Int>()
var counts = [Int](repeating: 0, count: M + 2)
let leaderThereshold = A.count/2
for i in 0..<K {
A[i] += 1
}
for i in A {
counts[i] += 1
}
if let leader = counts.first(where: { $0 > leaderThereshold }) {
leaders.insert(leader)
}
func moveToRight(left: Int, right: Int) {
counts[A[left]] -= 1
A[left] -= 1
counts[A[left]] += 1
counts[A[right]] -= 1
A[right] += 1
counts[A[right]] += 1
if counts[A[left]] > leaderThereshold {
leaders.insert(A[left])
}
if counts[A[right]] > leaderThereshold {
leaders.insert(A[right])
}
}
guard A.count > 1 else { return Array(leaders) }
for i in 1..<(A.count - K + 1) {
moveToRight(left: i - 1, right: i + K - 1)
}
return Array(leaders).sorted()
}
Code: 22:18:01 UTC,
swift4,
verify,
result: Failed
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> [Int] {
var leaders = Set<Int>()
var counts = [Int](repeating: 0, count: M + 2)
let leaderThereshold = A.count/2
for i in 0..<K {
A[i] += 1
}
for i in A {
counts[i] += 1
}
if let leader = counts.first(where: { $0 > leaderThereshold }) {
leaders.insert(leader)
}
func moveToRight(left: Int, right: Int) {
counts[A[left]] -= 1
A[left] -= 1
counts[A[left]] += 1
counts[A[right]] -= 1
A[right] += 1
counts[A[right]] += 1
if counts[A[left]] > leaderThereshold {
leaders.insert(A[left])
}
if counts[A[right]] > leaderThereshold {
leaders.insert(A[right])
}
}
guard A.count > 1 else { return Array(leaders) }
for i in 1..<(A.count - K + 1) {
moveToRight(left: i - 1, right: i + K - 1)
}
return Array(leaders).sorted()
}
Analysis
Code: 22:19:22 UTC,
swift4,
verify,
result: Failed
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> [Int] {
var leaders = Set<Int>()
var counts = [Int](repeating: 0, count: M + 2)
let leaderThereshold = A.count/2
for i in 0..<K {
A[i] += 1
}
for i in A {
counts[i] += 1
}
if let leader = counts.first(where: { $0 > leaderThereshold }) {
leaders.insert(leader)
}
func moveToRight(left: Int, right: Int) {
counts[A[left]] -= 1
A[left] -= 1
counts[A[left]] += 1
counts[A[right]] -= 1
A[right] += 1
counts[A[right]] += 1
if counts[A[left]] > leaderThereshold {
leaders.insert(A[left])
}
if counts[A[right]] > leaderThereshold {
leaders.insert(A[right])
}
}
guard A.count > 1 else { return Array(leaders) }
for i in 1..<(A.count - K + 1) {
moveToRight(left: i - 1, right: i + K - 1)
}
return Array(leaders).sorted()
}
Analysis
Code: 22:21:18 UTC,
swift4,
autosave
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> [Int] {
var leaders = Set<Int>()
var counts = [Int](repeating: 0, count: M + 2)
let leaderThereshold = A.count/2
for i in 0..<K {
A[i] += 1
}
for i in A {
counts[i] += 1
}
if let leader = counts.firstIndex(where: { $0 > leaderThereshold }) {
leaders.insert(leader)
}
func moveToRight(left: Int, right: Int) {
counts[A[left]] -= 1
A[left] -= 1
counts[A[left]] += 1
counts[A[right]] -= 1
A[right] += 1
counts[A[right]] += 1
if counts[A[left]] > leaderThereshold {
leaders.insert(A[left])
}
if counts[A[right]] > leaderThereshold {
leaders.insert(A[right])
}
}
guard A.count > 1 else { return Array(leaders) }
for i in 1..<(A.count - K + 1) {
moveToRight(left: i - 1, right: i + K - 1)
}
return Array(leaders).sorted()
}
Code: 22:21:21 UTC,
swift4,
verify,
result: Passed
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> [Int] {
var leaders = Set<Int>()
var counts = [Int](repeating: 0, count: M + 2)
let leaderThereshold = A.count/2
for i in 0..<K {
A[i] += 1
}
for i in A {
counts[i] += 1
}
if let leader = counts.firstIndex(where: { $0 > leaderThereshold }) {
leaders.insert(leader)
}
func moveToRight(left: Int, right: Int) {
counts[A[left]] -= 1
A[left] -= 1
counts[A[left]] += 1
counts[A[right]] -= 1
A[right] += 1
counts[A[right]] += 1
if counts[A[left]] > leaderThereshold {
leaders.insert(A[left])
}
if counts[A[right]] > leaderThereshold {
leaders.insert(A[right])
}
}
guard A.count > 1 else { return Array(leaders) }
for i in 1..<(A.count - K + 1) {
moveToRight(left: i - 1, right: i + K - 1)
}
return Array(leaders).sorted()
}
Analysis
Code: 22:21:27 UTC,
swift4,
final,
score:
100
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> [Int] {
var leaders = Set<Int>()
var counts = [Int](repeating: 0, count: M + 2)
let leaderThereshold = A.count/2
for i in 0..<K {
A[i] += 1
}
for i in A {
counts[i] += 1
}
if let leader = counts.firstIndex(where: { $0 > leaderThereshold }) {
leaders.insert(leader)
}
func moveToRight(left: Int, right: Int) {
counts[A[left]] -= 1
A[left] -= 1
counts[A[left]] += 1
counts[A[right]] -= 1
A[right] += 1
counts[A[right]] += 1
if counts[A[left]] > leaderThereshold {
leaders.insert(A[left])
}
if counts[A[right]] > leaderThereshold {
leaders.insert(A[right])
}
}
guard A.count > 1 else { return Array(leaders) }
for i in 1..<(A.count - K + 1) {
moveToRight(left: i - 1, right: i + K - 1)
}
return Array(leaders).sorted()
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M)
expand all
Correctness tests
1.
0.024 s
OK
2.
0.024 s
OK
3.
0.024 s
OK
4.
0.024 s
OK
5.
0.024 s
OK
6.
0.024 s
OK
1.
0.024 s
OK
2.
0.024 s
OK
3.
0.024 s
OK
4.
0.024 s
OK
1.
0.024 s
OK
2.
0.024 s
OK
1.
0.024 s
OK
2.
0.024 s
OK
1.
0.024 s
OK
2.
0.024 s
OK
3.
0.024 s
OK
expand all
Performance tests
1.
0.024 s
OK
2.
0.024 s
OK
3.
0.024 s
OK
1.
0.028 s
OK
2.
0.028 s
OK
3.
0.028 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.032 s
OK
2.
0.032 s
OK