Remove all Numbers that occur more than N times in the given Array

user_13983643 0
Viewed 126

I am working on the level 1 of the Google FooBar Minion scheduling challenge:

Write a function called solution(data, n) that takes in a list of less than 100 integers and a number n, and returns that same list but with all of the numbers that occur more than n times removed entirely.

The returned list should retain the same ordering as the original list - you don't want to mix up those carefully-planned shift rotations!

For instance, if data was [5, 10, 15, 10, 7] and n was 1, solution(data, n) would return the list [5, 15, 7] because 10 occurs twice, and thus was removed from the list entirely.

This is my solution, but for some reason only 2 test cases are passing out of 10.

The strange thing is, the open test case {1, 2, 2, 3, 3, 3, 4, 5, 5}, n = 1 is also failing, while in my local IDE it passes.

public static int[] solution(int[] data, int n) {
    Map<Integer, Integer> map = new LinkedHashMap<>();
    
    if (data.length < 1) {
        return data;
    }
    
    if (n < 1) {
        return new int[0];
    }
    
    for (final int datum : data) {
        map.put(datum, map.getOrDefault(datum, 0) + 1);
    }
    
    List<Integer> t = map.entrySet()
        .stream()
        .filter(x -> x.getValue() == 1)
        .map(Map.Entry::getKey)
        .toList();
    
    int[] b = new int[t.size()];
    
    for (int i = 0; i < t.size(); i++) {
        b[i] = t.get(i);
    }
    
    return b;
}
java-stream collections arrays java
1 Answers

returns that same list but with all of the numbers that occur more than n times removed entirely.

The returned list should retain the same ordering

According to the original problem statement, you need to discard only elements having the number of occurrences more than n, and nothing else.

There's no requirement that all elements in the resulting array should be distinct. It means you have to preserve all duplicated elements that will be encountered n or less than n times.

The approach of build building a histogram of frequencies (counting the number of occurrences) is correct, but you don't need LinkedHashMap.

This logic can be written like that using Java 8 method merge():

public static Map<Integer, Integer> countFrequencies(int[] arr) {
    Map<Integer, Integer> frequencies = new HashMap<>();
    for (int next: arr) {
        frequencies.merge(next, 1, Integer::sum);
    }
    return frequencies;
}

Or with Stream API:

public static Map<Integer, Long> countFrequencies(int[] arr) {
    
    return Arrays.stream(arr)
        .boxed()
        .collect(Collectors.groupingBy(
            Function.identity(),
            Collectors.counting()));
}

To ensure the order, you just need to iterate over the given array, and filter out the element having frequency less or equal to n.

Also, there's no need to create an intermediate list, you can get the resulting array as a result of execution of the stream pipeline.

public static int[] solution(int[] data, int n) {
    
    Map<Integer, Long> frequencies = countFrequencies(data);
    
    return Arrays.stream(data)
        .filter(num -> frequencies.get(num) <= n)
        .toArray();
}

See the Online Demo

Also make sure that you have all the imports at the top of the file you're submitting (imports for the code given above are listed in the demo).

And don't use import java.util.*, because of that your solution might not pass the tests.

user_179499450
Related