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 C#
Time spent on task 1 minutes
Notes
not defined yet
Code: 10:05:19 UTC,
java,
autosave
Code: 10:05:21 UTC,
cs,
autosave
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int[] solution(int K, int M, int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
Code: 10:05:26 UTC,
cs,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int K;
public static int THRESHOLD;
public int[] solution(int k, int m, int[] arr)
{
if (k > 100000 || k < 1 || k > arr.Length)
throw new ArgumentOutOfRangeException(nameof(k));
if (k > 100000 || k < 1)
throw new ArgumentOutOfRangeException(nameof(m));
if (arr.Length == 0)
return new int[] { };
if (arr.Length == 1)
return new int[] {arr[0] + 1};
K = k;
THRESHOLD = arr.Length / 2;
var dict = GetCandidates(arr);
var candidates = dict.Where(kp => kp.Value > THRESHOLD - K)
.OrderByDescending(kp => kp.Value).Take(3)
.ToArray();
if (dict.Count > THRESHOLD)
{
if (candidates.Sum(v => v.Value) < THRESHOLD)
return new int[] { };
}
var leaders = FindLeaders(candidates, arr);
return leaders;
}
int[] FindLeaders(KeyValuePair<int, int>[] candidates, int[] arr)
{
var list = new List<Counter>(candidates.Length);
foreach (var kp in candidates)
{
if (list.All(c => c.Key != kp.Key))
{
var counter = new Counter(kp.Key, kp.Value);
list.Add(counter);
}
if (kp.Value >= THRESHOLD && candidates.All(c => c.Key != kp.Key + 1))
{
list.Add(new Counter(kp.Key + 1, 0));
}
}
var leaders = new List<int>(2);
foreach (var counter in list)
{
for (int i = 0; i < arr.Length; i++)
{
if (i >= K)
{
if(counter.IsLeader)
break;
counter.Count(arr[i], arr[i - K]);
}
else
{
counter.Count(arr[i], null);
}
}
if(counter.IsLeader)
leaders.Add(counter.Key);
}
return leaders.OrderBy(v => v).ToArray();
}
Dictionary<int, int> GetCandidates(int[] arr)
{
var dict = new Dictionary<int, int>(arr.Length);
for (int i = 0; i < arr.Length; i++)
{
if (!dict.ContainsKey(arr[i]))
{
dict.Add(arr[i], 1);
}
else
{
dict[arr[i]]++;
}
}
return dict;
}
class Counter
{
public readonly int Key;
public int RequiredSegCount { get; private set; }
public readonly bool ReCount = false;
private int N;
private readonly int Predecessor;
private int _queueLength = 0;
private int _segCount = 0;
private int _segDeductCount = 0;
private int SegCount
{
get
{
if (_queueLength < K)
return -1;
return _segCount - _segDeductCount;
}
}
private int BestSegCount =0;
public Counter(int key, int n)
{
Key = key;
Predecessor = key - 1;
N = n;
if(n == 0)
ReCount = true;
RequiredSegCount = THRESHOLD + 1 - n;
}
public void Count(int elem, int? elemBeforeSeg)
{
if (IsLeader)
return;
if (ReCount && elem == Key)
N++;
if (_queueLength < K)
_queueLength++;
if (elem == Key)
_segDeductCount++;
if (elem == Predecessor)
_segCount++;
if (elemBeforeSeg.HasValue)
{
if (elemBeforeSeg.Value == Key)
_segDeductCount--;
if (elemBeforeSeg.Value == Predecessor)
_segCount--;
}
var segCount = SegCount;
if (segCount >= RequiredSegCount && _queueLength == K)
{
//leader detected!!!
IsLeader = true;
return;
}
if (segCount > BestSegCount)
BestSegCount = segCount;
if (ReCount && N + BestSegCount > THRESHOLD)
{
//leader detected!!!
IsLeader = true;
}
}
public bool IsLeader { get; private set; }
public override string ToString()
{
return $"{Key} - [#{N}+{SegCount}]{(IsLeader?" LEADER":"")}";
}
}
}
Code: 10:05:27 UTC,
cs,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int K;
public static int THRESHOLD;
public int[] solution(int k, int m, int[] arr)
{
if (k > 100000 || k < 1 || k > arr.Length)
throw new ArgumentOutOfRangeException(nameof(k));
if (k > 100000 || k < 1)
throw new ArgumentOutOfRangeException(nameof(m));
if (arr.Length == 0)
return new int[] { };
if (arr.Length == 1)
return new int[] {arr[0] + 1};
K = k;
THRESHOLD = arr.Length / 2;
var dict = GetCandidates(arr);
var candidates = dict.Where(kp => kp.Value > THRESHOLD - K)
.OrderByDescending(kp => kp.Value).Take(3)
.ToArray();
if (dict.Count > THRESHOLD)
{
if (candidates.Sum(v => v.Value) < THRESHOLD)
return new int[] { };
}
var leaders = FindLeaders(candidates, arr);
return leaders;
}
int[] FindLeaders(KeyValuePair<int, int>[] candidates, int[] arr)
{
var list = new List<Counter>(candidates.Length);
foreach (var kp in candidates)
{
if (list.All(c => c.Key != kp.Key))
{
var counter = new Counter(kp.Key, kp.Value);
list.Add(counter);
}
if (kp.Value >= THRESHOLD && candidates.All(c => c.Key != kp.Key + 1))
{
list.Add(new Counter(kp.Key + 1, 0));
}
}
var leaders = new List<int>(2);
foreach (var counter in list)
{
for (int i = 0; i < arr.Length; i++)
{
if (i >= K)
{
if(counter.IsLeader)
break;
counter.Count(arr[i], arr[i - K]);
}
else
{
counter.Count(arr[i], null);
}
}
if(counter.IsLeader)
leaders.Add(counter.Key);
}
return leaders.OrderBy(v => v).ToArray();
}
Dictionary<int, int> GetCandidates(int[] arr)
{
var dict = new Dictionary<int, int>(arr.Length);
for (int i = 0; i < arr.Length; i++)
{
if (!dict.ContainsKey(arr[i]))
{
dict.Add(arr[i], 1);
}
else
{
dict[arr[i]]++;
}
}
return dict;
}
class Counter
{
public readonly int Key;
public int RequiredSegCount { get; private set; }
public readonly bool ReCount = false;
private int N;
private readonly int Predecessor;
private int _queueLength = 0;
private int _segCount = 0;
private int _segDeductCount = 0;
private int SegCount
{
get
{
if (_queueLength < K)
return -1;
return _segCount - _segDeductCount;
}
}
private int BestSegCount =0;
public Counter(int key, int n)
{
Key = key;
Predecessor = key - 1;
N = n;
if(n == 0)
ReCount = true;
RequiredSegCount = THRESHOLD + 1 - n;
}
public void Count(int elem, int? elemBeforeSeg)
{
if (IsLeader)
return;
if (ReCount && elem == Key)
N++;
if (_queueLength < K)
_queueLength++;
if (elem == Key)
_segDeductCount++;
if (elem == Predecessor)
_segCount++;
if (elemBeforeSeg.HasValue)
{
if (elemBeforeSeg.Value == Key)
_segDeductCount--;
if (elemBeforeSeg.Value == Predecessor)
_segCount--;
}
var segCount = SegCount;
if (segCount >= RequiredSegCount && _queueLength == K)
{
//leader detected!!!
IsLeader = true;
return;
}
if (segCount > BestSegCount)
BestSegCount = segCount;
if (ReCount && N + BestSegCount > THRESHOLD)
{
//leader detected!!!
IsLeader = true;
}
}
public bool IsLeader { get; private set; }
public override string ToString()
{
return $"{Key} - [#{N}+{SegCount}]{(IsLeader?" LEADER":"")}";
}
}
}
Analysis
Code: 10:05:30 UTC,
cs,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int K;
public static int THRESHOLD;
public int[] solution(int k, int m, int[] arr)
{
if (k > 100000 || k < 1 || k > arr.Length)
throw new ArgumentOutOfRangeException(nameof(k));
if (k > 100000 || k < 1)
throw new ArgumentOutOfRangeException(nameof(m));
if (arr.Length == 0)
return new int[] { };
if (arr.Length == 1)
return new int[] {arr[0] + 1};
K = k;
THRESHOLD = arr.Length / 2;
var dict = GetCandidates(arr);
var candidates = dict.Where(kp => kp.Value > THRESHOLD - K)
.OrderByDescending(kp => kp.Value).Take(3)
.ToArray();
if (dict.Count > THRESHOLD)
{
if (candidates.Sum(v => v.Value) < THRESHOLD)
return new int[] { };
}
var leaders = FindLeaders(candidates, arr);
return leaders;
}
int[] FindLeaders(KeyValuePair<int, int>[] candidates, int[] arr)
{
var list = new List<Counter>(candidates.Length);
foreach (var kp in candidates)
{
if (list.All(c => c.Key != kp.Key))
{
var counter = new Counter(kp.Key, kp.Value);
list.Add(counter);
}
if (kp.Value >= THRESHOLD && candidates.All(c => c.Key != kp.Key + 1))
{
list.Add(new Counter(kp.Key + 1, 0));
}
}
var leaders = new List<int>(2);
foreach (var counter in list)
{
for (int i = 0; i < arr.Length; i++)
{
if (i >= K)
{
if(counter.IsLeader)
break;
counter.Count(arr[i], arr[i - K]);
}
else
{
counter.Count(arr[i], null);
}
}
if(counter.IsLeader)
leaders.Add(counter.Key);
}
return leaders.OrderBy(v => v).ToArray();
}
Dictionary<int, int> GetCandidates(int[] arr)
{
var dict = new Dictionary<int, int>(arr.Length);
for (int i = 0; i < arr.Length; i++)
{
if (!dict.ContainsKey(arr[i]))
{
dict.Add(arr[i], 1);
}
else
{
dict[arr[i]]++;
}
}
return dict;
}
class Counter
{
public readonly int Key;
public int RequiredSegCount { get; private set; }
public readonly bool ReCount = false;
private int N;
private readonly int Predecessor;
private int _queueLength = 0;
private int _segCount = 0;
private int _segDeductCount = 0;
private int SegCount
{
get
{
if (_queueLength < K)
return -1;
return _segCount - _segDeductCount;
}
}
private int BestSegCount =0;
public Counter(int key, int n)
{
Key = key;
Predecessor = key - 1;
N = n;
if(n == 0)
ReCount = true;
RequiredSegCount = THRESHOLD + 1 - n;
}
public void Count(int elem, int? elemBeforeSeg)
{
if (IsLeader)
return;
if (ReCount && elem == Key)
N++;
if (_queueLength < K)
_queueLength++;
if (elem == Key)
_segDeductCount++;
if (elem == Predecessor)
_segCount++;
if (elemBeforeSeg.HasValue)
{
if (elemBeforeSeg.Value == Key)
_segDeductCount--;
if (elemBeforeSeg.Value == Predecessor)
_segCount--;
}
var segCount = SegCount;
if (segCount >= RequiredSegCount && _queueLength == K)
{
//leader detected!!!
IsLeader = true;
return;
}
if (segCount > BestSegCount)
BestSegCount = segCount;
if (ReCount && N + BestSegCount > THRESHOLD)
{
//leader detected!!!
IsLeader = true;
}
}
public bool IsLeader { get; private set; }
public override string ToString()
{
return $"{Key} - [#{N}+{SegCount}]{(IsLeader?" LEADER":"")}";
}
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M)
expand all
Correctness tests
1.
0.020 s
OK
2.
0.032 s
OK
3.
0.032 s
OK
4.
0.032 s
OK
5.
0.032 s
OK
6.
0.032 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
3.
0.032 s
OK
4.
0.032 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
3.
0.032 s
OK
expand all
Performance 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.040 s
OK
1.
0.060 s
OK
2.
0.064 s
OK
3.
0.068 s
OK
1.
0.064 s
OK
2.
0.064 s
OK