Molybdenum2019 challenge efficient implementation

Question

I'm working on a solution that is correct but inefficient.

https://app.codility.com/programmers/task/leader_slice_inc/

This is my code :

public static void main(String[] args) {
 int[] A = { 2, 1, 3, 1, 2, 2, 3 };
 int[] B = null;
 int M = 5, K = 3;
 int array_lengh = A.length;
 Map<Integer, Integer> counter = null;
 Set<Integer> listaLideres = new LinkedHashSet<Integer>();
 // valor minimo =0 ; valor maximo = Longitud del array - k;
 // el lider sera aquel que ocurra mas de longitud/2
 for (int i = 0; i < array_lengh - K + 1; i++) {
 B = Arrays.copyOf(A, array_lengh);
 counter = new HashMap<Integer, Integer>();
 for (int j = i; j < i + K; j++) {
 B[j] = B[j] + 1;
 }
 for (int n = 0; n < array_lengh; n++) {
 int repeticones = counter.get(B[n]) == null ? 0 : counter.get(B[n]);
 counter.put(B[n], repeticones + 1);
 }
 int liderProvisional = 0;
 for (Map.Entry<Integer, Integer> valorRepeticion : counter.entrySet()) {
 liderProvisional = valorRepeticion.getValue();
 if (liderProvisional > array_lengh / 2) {
 listaLideres.add(valorRepeticion.getKey());
 }
 }
 }
 List<Integer> listaLideresOrdenada = new ArrayList<Integer>();
 listaLideresOrdenada.addAll(listaLideres);
 listaLideresOrdenada.sort(Comparator.naturalOrder());
 for (Integer integer : listaLideresOrdenada) {
 System.out.println(integer);
 }
}

Answer 1

Nice solution, find below my suggestions.

---

Creating a list from a set:

List<Integer> listaLideresOrdenada = new ArrayList<Integer>();
listaLideresOrdenada.addAll(listaLideres);

The set can be passed directly to the constructor of ArrayList:

List<Integer> listaLideresOrdenada = new ArrayList<Integer>(listaLideres);

---

Copying the input array A to B:

B = Arrays.copyOf(A, array_lengh);

This can be avoided since A can be modified in place in this problem.

---

Getting a value of a map or a default:

int repeticones = counter.get(B[n]) == null ? 0 : counter.get(B[n]);

Since Java 8 Map offers getOrDefault:

int repeticones = counter.getOrDefault(B[n], 0);

Optimization

The current solution uses this approach:

1. For each sliding window in A
2. Increment all elements of the sliding window by 1
3. Calculate the frequencies of all elements in A
4. Update the result if a leader is found

It can be considered a \$O(n^2)\$ brute force approach, typically not enough to solve a HARD problem on Codility.

Consider this approach: every time the sliding window moves to the right, the element on the left leaves the window, and the element on the right enters the windows. Therefore it is enough to update the frequencies of only these two numbers.

This approach improves the complexity to \$O(n*log(n))\$. The sorting operation is now the bottleneck.

A trick to avoid sorting is to use an array (for example, leaders) of size M (which is the value of the biggest element in A). Every time a leader x is found add it to leaders like leaders[x] = true. Finally, iterate on leaders and collect the results in order.

Getting rid of the sorting operation improves the complexity to \$O(m)\$, but it's still too slow! The solution needs to run in less than 0.1 seconds for an input array A of 100K elements.

So as a last optimization we can get rid of the map for counting the frequencies and use a simple array freq. Although updating a map is a very quick operation, updating an array is faster.

Reworked code

public static int[] solution(int K, int M, int[] A) {
 boolean[] leaders = new boolean[M + 2];
 int[] freq = new int[M + 2];
 int threshold = A.length / 2;
 // Increment initial sliding window by 1
 for (int i = 0; i < K; A[i]++, i++);
 // Calculate frequencies of all elements in A
 for (int i = 0; i < A.length; freq[A[i]]++, i++);
 // If there are leaders save them
 for (int i = 0; i < freq.length; i++) {
 leaders[i] = freq[i] > threshold || leaders[i];
 }
 for (int i = 1; i < A.length - K + 1; i++) {
 // Update frequency of element (on the left) leaving the sliding window
 int left = i - 1;
 freq[A[left]]--;
 A[left]--;
 freq[A[left]]++;
 // Update frequency of element (on the right) entering the sliding window
 int right = i + K - 1;
 freq[A[right]]--;
 A[right]++;
 freq[A[right]]++;
 // If there are new leaders save them
 leaders[A[right]] = freq[A[right]] > threshold || leaders[A[right]];
 leaders[A[left]] = freq[A[left]] > threshold || leaders[A[left]];
 }
 // Collect the leaders (in order)
 return IntStream.range(0, leaders.length)
 .filter(i -> leaders[i])
 .toArray();
}

• Antonio Diaz: really awesome solution, just one thing I dont understand, why m+2 on freq and leaders? boolean[] leaders = new boolean[M + 2]; int[] freq = new int[M + 2]
• Marc: @AntonioDiaz I am glad I could help. +1 because the array is zero-indexed. +1 because the sliding window is going to increase all elements by 1. So total +2.