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].
// 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) {
if (Q == 1) {
return 0;
}
Map<Integer, Map<Integer, Integer>> mapOfMaps = new HashMap();
for (int i = 0; i < B.length; i++) {
if (mapOfMaps.get(B[i]) == null) {
mapOfMaps.put(B[i], new HashMap<>());
}
Map<Integer, Integer> currentMap = mapOfMaps.get(B[i]);
if (!currentMap.keySet().contains(C[i])) {
currentMap.put(C[i], 1);
} else {
int count = currentMap.get(C[i]);
if (++count == Q) {
return i;
}
currentMap.put(C[i], count);
}
}
return -1;
}
private static boolean arrayContainsValue(int[] B, int i) {
for (final int e : B)
if (e == i) {
return true;
}
return false;
}
}// you can also use imports, for example:
import java.util.HashMap;
import java.util.Map;
// 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) {
if (Q == 1) {
return 0;
}
Map<Integer, Map<Integer, Integer>> mapOfMaps = new HashMap();
for (int i = 0; i < B.length; i++) {
if (mapOfMaps.get(B[i]) == null) {
mapOfMaps.put(B[i], new HashMap<>());
}
Map<Integer, Integer> currentMap = mapOfMaps.get(B[i]);
if (!currentMap.keySet().contains(C[i])) {
currentMap.put(C[i], 1);
} else {
int count = currentMap.get(C[i]);
if (++count == Q) {
return i;
}
currentMap.put(C[i], count);
}
}
return -1;
}
private static boolean arrayContainsValue(int[] B, int i) {
for (final int e : B)
if (e == i) {
return true;
}
return false;
}
}// you can also use imports, for example:
import java.util.HashMap;
import java.util.Map;
// 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) {
if (Q == 1) {
return 0;
}
Map<Integer, Map<Integer, Integer>> mapOfMaps = new HashMap();
for (int i = 0; i < B.length; i++) {
if (mapOfMaps.get(B[i]) == null) {
mapOfMaps.put(B[i], new HashMap<>());
}
Map<Integer, Integer> currentMap = mapOfMaps.get(B[i]);
if (!currentMap.keySet().contains(C[i])) {
currentMap.put(C[i], 1);
} else {
int count = currentMap.get(C[i]);
if (++count == Q) {
return i;
}
currentMap.put(C[i], count);
}
}
return -1;
}
private static boolean arrayContainsValue(int[] B, int i) {
for (final int e : B)
if (e == i) {
return true;
}
return false;
}
}// you can also use imports, for example:
import java.util.HashMap;
import java.util.Map;
// 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) {
if (Q == 1) {
return 0;
}
Map<Integer, Map<Integer, Integer>> mapOfMaps = new HashMap();
for (int i = 0; i < B.length; i++) {
if (mapOfMaps.get(B[i]) == null) {
mapOfMaps.put(B[i], new HashMap<>());
}
Map<Integer, Integer> currentMap = mapOfMaps.get(B[i]);
if (!currentMap.keySet().contains(C[i])) {
currentMap.put(C[i], 1);
} else {
int count = currentMap.get(C[i]);
if (++count == Q) {
return i;
}
currentMap.put(C[i], count);
}
}
return -1;
}
private static boolean arrayContainsValue(int[] B, int i) {
for (final int e : B)
if (e == i) {
return true;
}
return false;
}
}// you can also use imports, for example:
import java.util.HashMap;
import java.util.Map;
// 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) {
if (Q == 1) {
return 0;
}
Map<Integer, Map<Integer, Integer>> mapOfMaps = new HashMap();
for (int i = 0; i < B.length; i++) {
if (mapOfMaps.get(B[i]) == null) {
mapOfMaps.put(B[i], new HashMap<>());
}
Map<Integer, Integer> currentMap = mapOfMaps.get(B[i]);
if (!currentMap.keySet().contains(C[i])) {
currentMap.put(C[i], 1);
} else {
int count = currentMap.get(C[i]);
if (++count == Q) {
return i;
}
currentMap.put(C[i], count);
}
}
return -1;
}
private static boolean arrayContainsValue(int[] B, int i) {
for (final int e : B)
if (e == i) {
return true;
}
return false;
}
}The solution obtained perfect score.