Count the number of distinct slices (containing only unique numbers).
- Difficulty Level: Easy
- Question URL: https://app.codility.com/programmers/lessons/15-caterpillar_method/count_distinct_slices/
- Time Complexity:
Solution:
Solution to Codility's Count Distinct Slices problem which is from the Codility Lesson 15: Caterpillar method and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to count the number of distinct slices (containing only unique numbers). You can find the question of this CountDistinctSlices problem in the Codility website.
package Codility.Lesson15;
import java.util.*;
public class CountDistinctSlices {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 3, 4, 5, 1, 2, 6 };
int a = 6;
int result2 = solution(a, a1);
System.out.println(result2);
}
public static int solution(int M, int[] A) {
System.out.println(5 - 4 + 1);
// write your code in Java SE 8
// This solution is more clever, and much faster O(n)
// main idea:
// use "boolean[]" to record if an integer is already seen
// also use "leftEnd" and "rightEnd"
boolean[] seen = new boolean[M + 1]; // from 0 to M
// Arrays.fill(seen, false); // note: "false" by default
int leftEnd = 0;
int rightEnd = 0;
int numSlice = 0;
// key point: move the "leftEnd" and "rightEnd" of a slice
while (leftEnd < A.length && rightEnd < A.length) {
// case 1: distinct (rightEnd)
if (seen[A[rightEnd]] == false) {
// note: not just +1
// there could be (rightEnd - leftEnd + 1) combinations (be careful)
numSlice = numSlice + (rightEnd - leftEnd + 1);
if (numSlice >= 1_000_000_000)
return 1_000_000_000;
// increase the slice to right by "1" (important)
seen[A[rightEnd]] = true;
rightEnd++;
}
// case 2: not distinct
else {
// decrease the slice from left by "1" (important)
// remove A[leftEnd] from "seen" (be careful)
seen[A[leftEnd]] = false;
leftEnd++;
}
}
return numSlice;
}
}