Tasks Details
medium
1.
Buckets
Given N buckets and M colored balls to put in them, find the earliest moment when some bucket contains Q balls of the same color.
Task Score
100%
Correctness
100%
Performance
100%
There are N buckets numbered from 0 to N−1. There are also M balls of different colors, numbered from 0 to M−1. The K-th ball has color C[K]. For simplicity we denote each color by an integer.
Initially all buckets are empty. At moment K (for K from 0 to M−1), we put the K-th ball into bucket B[K].
Calculate the earliest moment when there are at least Q balls of the same color in some bucket.
Write a function:
class Solution { public int solution(int N, int Q, int[] B, int[] C); }
that, given two integers N and Q, and two arrays B and C consisting of M integers each, returns the earliest moment in which there is some bucket with at least Q balls of the same color. The function should return −1 if no such moment occurs.
Examples:
1. Given N = 3, Q = 2, B = [1, 2, 0, 1, 1, 0, 0, 1] and C = [0, 3, 0, 2, 0, 3, 0, 0], the function should return 4. At moment 3 we have a ball of color 0 in bucket 0, balls of colors 0 and 2 in bucket 1, and a ball of color 3 in bucket 2. At moment 4 we put another ball of color 0 into bucket 1, and there are thus two balls of the same color in this bucket.
2. Given N = 2, Q = 2, B = [0, 1] and C = [5, 5], the function should return −1. There is no moment in which there is some bucket with at least 2 balls of the same color.
3. Given N = 2, Q = 2, B = [0, 1, 0, 1, 0, 1] and C = [1, 3, 0, 0, 3, 3], the function should return 5.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..1,000,000];
- Q and M are integers within the range [1..100,000];
- each element of array B is an integer within the range [0..N-1];
- each element of array C is an integer within the range [0..1,000,000].
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 11 minutes
Notes
not defined yet
Code: 23:42:52 UTC,
java,
autosave
Code: 23:45:24 UTC,
java,
autosave
Code: 23:46:24 UTC,
java,
autosave
Code: 23:46:35 UTC,
java,
autosave
Code: 23:51:43 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int Q, int[] B, int[] C) {
// N is number of buckets ...
// q is the count we check for ...
HashMap<Integer, HashMap<Integer, Integer>> bucketsMap = new HashMap<Integer, HashMap<Integer,Integer>>() ;
int bucket = -1 ;
int color = -1 ;
int count = -1 ;
for(int i = 0 ; i < B.length ; i++){
bucket = B[i];
color = C[i] ;
HashMap<Integer, Integer> bucketMap = bucketsMap.getOrDefault(bucket, new HashMap<Integer, Integer>()) ;
count = bucketMap.getOrDefault(color, 0) ;
count++ ;
if(count == Q){
return i+1;
}
bucketMap.put(color, count) ;
}
return -1 ;
}
}
Code: 23:51:52 UTC,
java,
verify,
result: Failed
import java.util.HashMap;
class Solution {
public int solution(int N, int Q, int[] B, int[] C) {
// N is number of buckets ...
// q is the count we check for ...
HashMap<Integer, HashMap<Integer, Integer>> bucketsMap = new HashMap<Integer, HashMap<Integer,Integer>>() ;
int bucket = -1 ;
int color = -1 ;
int count = -1 ;
for(int i = 0 ; i < B.length ; i++){
bucket = B[i];
color = C[i] ;
HashMap<Integer, Integer> bucketMap = bucketsMap.getOrDefault(bucket, new HashMap<Integer, Integer>()) ;
count = bucketMap.getOrDefault(color, 0) ;
count++ ;
if(count == Q){
return i+1;
}
bucketMap.put(color, count) ;
}
return -1 ;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got -1 expected 4
1.
0.004 s
OK
1.
0.004 s
WRONG ANSWER,
got -1 expected 5
Code: 23:52:40 UTC,
java,
autosave
import java.util.HashMap;
class Solution {
public int solution(int N, int Q, int[] B, int[] C) {
// N is number of buckets ...
// q is the count we check for ...
HashMap<Integer, HashMap<Integer, Integer>> bucketsMap = new HashMap<Integer, HashMap<Integer,Integer>>() ;
int bucket = -1 ;
int color = -1 ;
int count = -1 ;
for(int i = 0 ; i < B.length ; i++){
bucket = B[i];
color = C[i] ;
HashMap<Integer, Integer> bucketMap = bucketsMap.getOrDefault(bucket, new HashMap<Integer, Integer>()) ;
count = bucketMap.getOrDefault(color, 0) ;
count++ ;
if(count == Q){
return i+1;
}
bucketMap.put(color, count) ;
bucketsMap.put(bucket, bucketMap) ;
}
return -1 ;
}
}
Code: 23:52:44 UTC,
java,
verify,
result: Failed
import java.util.HashMap;
class Solution {
public int solution(int N, int Q, int[] B, int[] C) {
// N is number of buckets ...
// q is the count we check for ...
HashMap<Integer, HashMap<Integer, Integer>> bucketsMap = new HashMap<Integer, HashMap<Integer,Integer>>() ;
int bucket = -1 ;
int color = -1 ;
int count = -1 ;
for(int i = 0 ; i < B.length ; i++){
bucket = B[i];
color = C[i] ;
HashMap<Integer, Integer> bucketMap = bucketsMap.getOrDefault(bucket, new HashMap<Integer, Integer>()) ;
count = bucketMap.getOrDefault(color, 0) ;
count++ ;
if(count == Q){
return i+1;
}
bucketMap.put(color, count) ;
bucketsMap.put(bucket, bucketMap) ;
}
return -1 ;
}
}
Analysis
expand all
Example tests
1.
0.008 s
WRONG ANSWER,
got 5 expected 4
1.
0.008 s
OK
1.
0.012 s
WRONG ANSWER,
got 6 expected 5
Code: 23:53:00 UTC,
java,
verify,
result: Passed
import java.util.HashMap;
class Solution {
public int solution(int N, int Q, int[] B, int[] C) {
// N is number of buckets ...
// q is the count we check for ...
HashMap<Integer, HashMap<Integer, Integer>> bucketsMap = new HashMap<Integer, HashMap<Integer,Integer>>() ;
int bucket = -1 ;
int color = -1 ;
int count = -1 ;
for(int i = 0 ; i < B.length ; i++){
bucket = B[i];
color = C[i] ;
HashMap<Integer, Integer> bucketMap = bucketsMap.getOrDefault(bucket, new HashMap<Integer, Integer>()) ;
count = bucketMap.getOrDefault(color, 0) ;
count++ ;
if(count == Q){
return i;
}
bucketMap.put(color, count) ;
bucketsMap.put(bucket, bucketMap) ;
}
return -1 ;
}
}
Analysis
Code: 23:53:21 UTC,
java,
verify,
result: Passed
import java.util.HashMap;
class Solution {
public int solution(int N, int Q, int[] B, int[] C) {
// N is number of buckets ...
// q is the count we check for ...
HashMap<Integer, HashMap<Integer, Integer>> bucketsMap = new HashMap<Integer, HashMap<Integer,Integer>>() ;
int bucket = -1 ;
int color = -1 ;
int count = -1 ;
for(int i = 0 ; i < B.length ; i++){
bucket = B[i];
color = C[i] ;
HashMap<Integer, Integer> bucketMap = bucketsMap.getOrDefault(bucket, new HashMap<Integer, Integer>()) ;
count = bucketMap.getOrDefault(color, 0) ;
count++ ;
if(count == Q){
return i;
}
bucketMap.put(color, count) ;
bucketsMap.put(bucket, bucketMap) ;
}
return -1 ;
}
}
Analysis
Code: 23:53:25 UTC,
java,
final,
score:
100
import java.util.HashMap;
class Solution {
public int solution(int N, int Q, int[] B, int[] C) {
// N is number of buckets ...
// q is the count we check for ...
HashMap<Integer, HashMap<Integer, Integer>> bucketsMap = new HashMap<Integer, HashMap<Integer,Integer>>() ;
int bucket = -1 ;
int color = -1 ;
int count = -1 ;
for(int i = 0 ; i < B.length ; i++){
bucket = B[i];
color = C[i] ;
HashMap<Integer, Integer> bucketMap = bucketsMap.getOrDefault(bucket, new HashMap<Integer, Integer>()) ;
count = bucketMap.getOrDefault(color, 0) ;
count++ ;
if(count == Q){
return i;
}
bucketMap.put(color, count) ;
bucketsMap.put(bucket, bucketMap) ;
}
return -1 ;
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M*log(M))
expand all
Correctness tests
1.
0.012 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.012 s
OK
expand all
Correctness/performance tests
1.
0.028 s
OK
2.
0.036 s
OK
1.
0.016 s
OK
2.
0.016 s
OK
1.
0.012 s
OK
2.
0.008 s
OK
3.
0.772 s
OK
4.
0.624 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.920 s
OK
4.
0.624 s
OK
1.
0.880 s
OK
2.
1.200 s
OK
3.
1.372 s
OK
1.
0.720 s
OK
2.
0.820 s
OK
3.
1.396 s
OK