Drop values to keep only N occurrences

Question

I was doing today some katas from Codewars. I had to write function which keeps only N of same elements from array, for example:

{1,2,3,4,1}, N=1 -> {1,2,3,4}
{2,2,2,2}, N=2 -> {2,2}

I come up with that solution using streams:

 public static int[] deleteNth(int[] elements, int maxOcurrences) {
    List<Integer> ints = Arrays.stream(elements)
                               .boxed()
                               .collect(Collectors.toList());
    return ints.stream().filter(x -> Collections.frequency(ints, x) <= maxOcurrences)
        .mapToInt(Integer::intValue)
        .toArray();
}

So, firstly change ints to Integers, then filter if freq is higher than N. But this isn't working, because repeating elements have identical frequency regardless of theirs positions. It looks like values are filtered after filter call. How can I fix this to get correct values?

PS: I know thats O(n^2), but this isn't a problem for me.

Answer 1

The solution I've found to accomplish the task at hand is as follows:

public static int[] deleteNth(int[] elements, int maxOccurrences) {
    return Arrays.stream(elements)
                 .boxed()
                 .collect(Collectors.groupingBy(Function.identity(), 
                        LinkedHashMap::new,
                        Collectors.counting()))
                 .entrySet()
                 .stream()
                 .flatMapToInt(entry ->
                    IntStream.generate(entry::getKey)
                             .limit(Math.min(maxOccurrences, entry.getValue())))
                 .toArray();
}

We first group the elements and then apply a Collectors.counting() as a downstream collector to get us the counts of a given element. After that is done we simply map a given number n number of times and then collect to an array with the toArray eager operations.

Answer 2

Actually you exclude elements that are superior to the maxOcurrences value :

.filter(x -> Collections.frequency(ints, x) <= maxOcurrences)

I am not sure that a full Stream solution be the best choice for this use case as you want to add some values according to how many was "currently collected" for these values.

Here it how I would implement that :

public class DeleteN {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(deleteNth(new int[] { 1, 2, 3, 4, 1 }, 1)));
        System.out.println(Arrays.toString(deleteNth(new int[] { 2, 2, 2, 2 }, 2)));
    }

    public static int[] deleteNth(int[] elements, int maxOcurrences) {

        Map<Integer, Long> actualOccurencesByNumber = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        Arrays.stream(elements)
              .forEach(i -> {
                  Long actualValue = actualOccurencesByNumber.computeIfAbsent(i, k -> Long.valueOf(0L));
                  if (actualValue < maxOcurrences) {
                      result.add(i);
                      actualOccurencesByNumber.computeIfPresent(i, (k, v) -> v + 1L);
                  }
              });

        return result.stream().mapToInt(i -> i).toArray();
    }
}

Output :

[1, 2, 3, 4]

[2, 2]

Answer 3

I think this is a great case to not use streams. Stream are not always the best approach when stateful operations are involved.

But it can be definitely done, and also the question asks specifically for streams, so you can use the followings.

---

Using forEachOrdered

You can use forEachOrdered with should ensure the order (here obvioulsy the stream has to be sequential):

public static int[] deleteNth(int[] elements, int maxOcurrs) {
    List<Integer> list = new ArrayList<>();
    Arrays.stream(elements).forEachOrdered(elem -> {
        if (Collections.frequency(list, elem) < maxOcurrs) list.add(elem);
    });
    return list.stream().mapToInt(Integer::intValue).toArray();
}

---

Using collect

Given some circunstanses you can use the collect method to accomplish this.

When the stream is ordered and sequential, which is the case of Arrays.stream(elements).boxed(), the collect() method does not use the combiner operator (this is truth for java8 and java9 current realease, and however is not guaranteed to work exactly the same in next releases, because many optimizations can occur).

This implementation keeps the order of the stream, and as mentioned before works fine in the current releases. Like the answer in the link below says, and also in my personal opinion, i find very difficult that the implementation of collect in sequential streams will ever need to use the combiner.

The code of the collect method is the following:

public static int[] deleteNth(int[] elements, int maxOcurrs) {
    return Arrays.stream(elements).boxed()
            .collect(() -> new ArrayList<Integer>(),
                    (list, elem) -> {
                        if (Collections.frequency(list, elem) < maxOcurrs) list.add(elem);
                    },
                    (list1, list2) -> { 
                        throw new UnsupportedOperationException("Undefined combiner"); 
                    })
            .stream()
            .mapToInt(Integer::intValue)
            .toArray();
}

This collector creates an ArrayList, and when is goind to add the new element checks if the maxOcurrences is met, if is not, then adds the element. Like mentioned before, and in the answer below, the combiner is not called at all. This persforms a little better than n^2.

More information of why the combiner method is not called in sequentials streams can be found here.