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 3 minutes
Notes
not defined yet
Code: 17:50:12 UTC,
java,
autosave
Code: 17:50:51 UTC,
java,
autosave
// you can also use imports, for example:
import java.util.HashMap;
// 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) {
// write your code in Java SE 8
Object[] buckets = new Object[N];
for(int i=0; i<N; i++) {
buckets[i] = new HashMap<Integer, Integer>();
}
for(int i=0; i<B.length; i++) {
int bucketBall = B[i];
int colorBall = C[i];
HashMap<Integer, Integer> map = (HashMap<Integer, Integer>) buckets[bucketBall];
Integer color = map.get(colorBall);
if (color == null) {
color = new Integer(1);
} else {
color = color.intValue() + 1;
}
if (color.intValue() == Q) {
return i;
} else {
map.put(colorBall, color);
buckets[bucketBall] = map;
}
}
return -1;
}
}
Code: 17:51:27 UTC,
java,
autosave
// you can also use imports, for example:
import java.util.HashMap;
// 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) {
// write your code in Java SE 8
Object[] buckets = new Object[N];
for(int i=0; i<N; i++) {
buckets[i] = new HashMap<Integer, Integer>();
}
for(int i=0; i<B.length; i++) {
int bucketBall = B[i];
int colorBall = C[i];
HashMap<Integer, Integer> map = (HashMap<Integer, Integer>) buckets[bucketBall];
Integer color = map.get(colorBall);
if (color == null) {
color = new Integer(1);
} else {
color = color.intValue() + 1;
}
if (color.intValue() == Q) {
return i;
} else {
map.put(colorBall, color);
buckets[bucketBall] = map;
}
}
return -1;
}
}
Code: 17:51:37 UTC,
java,
autosave
// you can also use imports, for example:
import java.util.HashMap;
// 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) {
// write your code in Java SE 8
Object[] buckets = new Object[N];
for(int i=0; i<N; i++) {
buckets[i] = new HashMap<Integer, Integer>();
}
for(int i=0; i<B.length; i++) {
int bucketBall = B[i];
int colorBall = C[i];
HashMap<Integer, Integer> map = (HashMap<Integer, Integer>) buckets[bucketBall];
if(map == null) {
}
Integer color = map.get(colorBall);
if (color == null) {
color = new Integer(1);
} else {
color = color.intValue() + 1;
}
if (color.intValue() == Q) {
return i;
} else {
map.put(colorBall, color);
buckets[bucketBall] = map;
}
}
return -1;
}
}
Code: 17:51:51 UTC,
java,
autosave
// you can also use imports, for example:
import java.util.HashMap;
// 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) {
// write your code in Java SE 8
Object[] buckets = new Object[N];
for(int i=0; i<B.length; i++) {
int bucketBall = B[i];
int colorBall = C[i];
HashMap<Integer, Integer> map = (HashMap<Integer, Integer>) buckets[bucketBall];
if(map == null) {
map = new HashMap<Integer, Integer>();
}
Integer color = map.get(colorBall);
if (color == null) {
color = new Integer(1);
} else {
color = color.intValue() + 1;
}
if (color.intValue() == Q) {
return i;
} else {
map.put(colorBall, color);
buckets[bucketBall] = map;
}
}
return -1;
}
}
Code: 17:52:36 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.HashMap;
// 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) {
// write your code in Java SE 8
Object[] buckets = new Object[N];
for(int i=0; i<B.length; i++) {
int bucketBall = B[i];
int colorBall = C[i];
HashMap<Integer, Integer> map = (HashMap<Integer, Integer>) buckets[bucketBall];
if(map == null) {
map = new HashMap<Integer, Integer>();
}
Integer color = map.get(colorBall);
if (color == null) {
color = new Integer(1);
} else {
color = color.intValue() + 1;
}
if (color.intValue() == Q) {
return i;
} else {
map.put(colorBall, color);
buckets[bucketBall] = map;
}
}
return -1;
}
}
Analysis
expand all
User tests
1.
0.008 s
OK
function result: 0
function result: 0
1.
0.008 s
OK
function result: 2
function result: 2
1.
0.004 s
OK
function result: 2
function result: 2
User test case 1:
[500000, 1, [0], [0]]
User test case 2:
[2, 2, [1, 1, 1, 1], [0, 1, 0, 1]]
User test case 3:
[2, 2, [0, 1, 0, 1], [1, 1, 1, 1]]
Code: 17:53:03 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.HashMap;
// 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) {
// write your code in Java SE 8
Object[] buckets = new Object[N];
for(int i=0; i<B.length; i++) {
int bucketBall = B[i];
int colorBall = C[i];
HashMap<Integer, Integer> map = (HashMap<Integer, Integer>) buckets[bucketBall];
if(map == null) {
map = new HashMap<Integer, Integer>();
}
Integer color = map.get(colorBall);
if (color == null) {
color = new Integer(1);
} else {
color = color.intValue() + 1;
}
if (color.intValue() == Q) {
return i;
} else {
map.put(colorBall, color);
buckets[bucketBall] = map;
}
}
return -1;
}
}
Analysis
expand all
User tests
1.
0.008 s
OK
function result: 0
function result: 0
1.
0.008 s
OK
function result: 2
function result: 2
1.
0.004 s
OK
function result: 2
function result: 2
User test case 1:
[500000, 1, [0], [0]]
User test case 2:
[2, 2, [1, 1, 1, 1], [0, 1, 0, 1]]
User test case 3:
[2, 2, [0, 1, 0, 1], [1, 1, 1, 1]]
Code: 17:53:09 UTC,
java,
final,
score:
100
// you can also use imports, for example:
import java.util.HashMap;
// 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) {
// write your code in Java SE 8
Object[] buckets = new Object[N];
for(int i=0; i<B.length; i++) {
int bucketBall = B[i];
int colorBall = C[i];
HashMap<Integer, Integer> map = (HashMap<Integer, Integer>) buckets[bucketBall];
if(map == null) {
map = new HashMap<Integer, Integer>();
}
Integer color = map.get(colorBall);
if (color == null) {
color = new Integer(1);
} else {
color = color.intValue() + 1;
}
if (color.intValue() == Q) {
return i;
} else {
map.put(colorBall, color);
buckets[bucketBall] = map;
}
}
return -1;
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(M*log(M))
expand all
Correctness tests
1.
0.008 s
OK
2.
0.012 s
OK
3.
0.012 s
OK
4.
0.008 s
OK
expand all
Correctness/performance tests
1.
0.024 s
OK
2.
0.032 s
OK
1.
0.016 s
OK
2.
0.016 s
OK
1.
0.012 s
OK
2.
0.012 s
OK
3.
0.660 s
OK
4.
0.472 s
OK
1.
0.008 s
OK
2.
0.012 s
OK
3.
0.680 s
OK
4.
0.472 s
OK
1.
0.640 s
OK
2.
0.920 s
OK
3.
0.976 s
OK
1.
0.600 s
OK
2.
0.648 s
OK
3.
0.948 s
OK