How to count groups of integers within arrays, without sorting the array?

group multiple occurrence of array elements ordered by first occurrence
array is a group of
array java
determine if two arrays have no elements in common
find all numbers disappeared in an array - geeksforgeeks
for a given array of transactions each transaction has an item id
array in c
check if given arrays are disjoint

My goal is to be able to count groups of the same integer within an array. For example, in an array like so, {1, 1, 1, 2, 2, 3, 1, 1}, there are 4 groups:

  • of at least size 1: 3 groups
  • of at least size 2: 1 group
  • of at least size 3

I'm having issues accomplishing this without sorting the array. When it gets sorted I lose count of the group of two 1's at the end of the array, since it gets put next to the other groups of 1's.

int result = (int) Stream.of(1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 4, 4, 4, 6)
        .collect(Collectors.groupingBy(i -> i))
        .entrySet().stream()
        .filter(entry -> entry.getValue().size() >= 1) // specify the size
        .count()

return result;

This expected output for each size is as follows:

size 1 count == 8

size 2 count == 5

size 6 count == 1

size 8 count == 1

The actual output is as follows:

size 1 count == 6

size 2 count == 3

size 6 count == 2

size 8 count == 1

The difference is a result of the array being sorted prior to the count taking place. Is there any way to accomplish this?

Edit: A group is essentially any place where the same integer repeats, until an integer of a different value, is ahead of it; so, the groups of size 2 in this in this code are any at index 0 to 2(inclusive), index 4 - 5(inclusive), index 6 - 15(inclusive, index 16 - 18(inclusive, and index 20 -22(inclusive). Since there are 5 groups that are of at least size 2 a count of 5 should be returned.

An imperative style of code for my goal.

Scanner key = new Scanner("1 1 1 2 1 1 3 3 3 3 3 3 3 3 3 3 4 4 4 5 4 4 4 6");

        int cnt = 0;
        int counter = 0;
        int i = 0;

            while(key.hasNextInt()) {   
                int next = key.nextInt();

                if(next == array[i]) {
                    counter++;
                }

                if(i + 1 < array.length && i -1 >= 0 
                   && counter >=size  
                   && next != array[i + 1] 
                   && next == array[i-size + 1]) {
                    cnt++;
                    counter = 0;
                }
                i++;
            }
        return cnt;

The expected return for this is the same as above.

The actual return is:

size 1 count == 7

size 2 count == 5

size 6 count == 3

size 8 count == 1

The problem with this loop is I believe it is skipping first piece and the end piece of the array.

I'm not having the same sorting issue as the Stream way.

Ideally, this wouldn't require any external utilities/libraries.

First I would suggest to find all subgroups. For this you can use Stream.collect() with a custom collector:

List<List<Integer>> sublists = IntStream.of(1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 4, 4, 4, 6)
        .collect(ArrayList::new, (lists, value) -> {
            if (lists.isEmpty() || lists.get(lists.size() - 1).stream().noneMatch(e -> e == value)) {
                lists.add(new ArrayList<>());
            }
            lists.get(lists.size() - 1).add(value);
        }, (l1, l2) -> {
            throw new RuntimeException("not supported for parallel streams");
        });

The result is:

[[1, 1, 1], [2], [1, 1], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [4, 4, 4], [5], [4, 4, 4], [6]]

Now you can use this to group the list sizes:

Map<Integer, Long> result = sublists.stream()
        .collect(Collectors.groupingBy(List::size, Collectors.counting()));
result.forEach((size, count) -> System.out.println(String.format("size %s count %s", size, count)));

This finds all existing group sizes and prints:

size 1 count 3
size 2 count 1
size 3 count 3
size 10 count 1

To count all groups with a min length you can use:

Map<Integer, Long> result = IntStream.rangeClosed(1, sublists.stream().mapToInt(List::size).max().orElse(0)).boxed()
        .collect(Collectors.toMap(Function.identity(), i -> sublists.stream().filter(l -> l.size() >= i).count()));
result.forEach((size, count) -> System.out.println(String.format("size %s count %s", size, count)));

This prints:

size 1 count 8
size 2 count 5
size 3 count 4
size 4 count 1
size 5 count 1
size 6 count 1
size 7 count 1
size 8 count 1
size 9 count 1
size 10 count 1

To get only a predefined set of sizes (e. g. 1, 2, 6, 8) you can modify the last solution:

Map<Integer, Long> result = IntStream.of(1, 2, 6, 8).boxed()
        .collect(Collectors.toMap(Function.identity(), i -> sublists.stream().filter(l -> l.size() >= i).count()));
result.forEach((size, count) -> System.out.println(String.format("size %s count %s", size, count)));

The result of this is:

size 1 count 8
size 2 count 5
size 6 count 1
size 8 count 1

Group multiple occurrence of array elements ordered by first , Given an unsorted array with repetitions, the task is to group multiple The grouping should happen in a way that the order of first void groupElements( int arr[], int n) Traverse the array elements, and store count for every element from an Array such that no element is K times any other element in the� int arr[10]={},count=0; Again we’re initializing the same 2 variables as the previous scenario. “arr[10]” is the array of type int with the size of 10 elements “count” is used to count the number of elements in the array You might have noticed the “{}” after the array is initialized.

If using StreamEx is an option it get's quite easy

IntStream s = IntStream.of(1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 4, 4, 4, 6);
List<List<Integer>> t = IntStreamEx.of (s).boxed().groupRuns(Integer::equals).toList();
t.forEach(e -> {
  System.out.println(String.format("Group of %s - %s times", e.get(0), e.size()));
});

Count all possible groups of size 2 or 3 that have sum as multiple of , Find XOR of all elements in an Array � Efficiently merging two sorted arrays with Given an unsorted integer (positive values only) array of size 'n', we can form a Hash all elements in a count array based on remainder, i.e, for all No. of such groups are c[0]*c[1]*c[2]. 5. More related articles in Arrays. Given an array arr[] of positive integers, the task is to sort the array in decreasing order of count of set bits in binary representations of array elements. For integers having same number of set bits in their binary representation, sort according to their position in the original array i.e., a stable sort.

First of all, let me start by saying this is not really what the Stream API is made for but however, it is possible, in maybe not the most elegant way, but it is nonetheless possible.

Here is a possible solution for you to use

  1. Convert everything to a big string and split it where number get different.
  2. Now stream through the stream and collect the groups and their count
  3. Add the number of higher groups to each of the smaller ones (to get the at least of logic)
  4. There, you should have all the info you needed
Demo
String[] groups = Stream.of(1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 4, 4, 4, 6)
        .map(String::valueOf)
        .collect(Collectors.joining(","))
        .split("(?<=(\\d))(,)(?!\\1)");

Map<Integer, Long> groupedByGroupSizes = Arrays.stream(groups)
        .map(group -> group.split(",").length)
        .collect(Collectors.groupingBy(x -> x, Collectors.counting()));

TreeMap<Integer, Long> integerLongTreeMap = new TreeMap<>(groupedByGroupSizes);
int size = integerLongTreeMap.size();

for (Integer integer : integerLongTreeMap.keySet()) {
    Long value = integerLongTreeMap.get(integer);
    integerLongTreeMap.put(integer, value + --size);
}

integerLongTreeMap.entrySet().forEach(entry -> System.out.println(String.format("of at least size %s: %s groups", entry.getKey(), entry.getValue())));
Prints
of at least size 1: 6 groups
of at least size 2: 3 groups
of at least size 3: 4 groups
of at least size 10: 1 groups

Aggregate Functions in Standard SQL | BigQuery, An aggregate function is a function that summarizes the rows of a group into a single value. When the associated SELECT has no GROUP BY clause or when certain In this case, the COUNT and COUNTIF functions return 0 , while all other elements in non-NULL input arrays (an error is raised, however, if an array in� But what if we want to create not an array of numbers, strings, or other objects, but rather an array of arrays? Java lets you do this. The sort of array we are already familiar with (int[] myArray = new int[8]) is known as a one-dimensional array. But an array of arrays is called a two-dimensional array.

Arrays \ Processing.org, In computer programming, an array is a set of data elements stored under the same There can be arrays of numbers, characters, sentences, boolean values, and so on. The first element is at position [0] because it has no offset; the second Processing provides a group of functions that assist in managing array data. Given an integer k and an array arr[], the task is to repeat the following operation exactly k times: Find the minimum non-zero element in the array, print it and then subtract this number from all the non-zero elements of the array. If all the elements of the array are < 0, just print 0. Examples: Input: arr[] = {3, 6, 4, 2}, k = 5 Output: 2 1 1 2 0

Set union of two arrays - MATLAB union, This MATLAB function returns the combined data from A and B with no repetitions . Generally, the values in C are a sorted combination of the elements of A(ia) and B(ib) . vars is a positive integer, a vector of positive integers, a variable name, a cell array of Calculate with arrays that have more rows than fit in memory. Given an array arr[] of N integers and an index range [a, b].The task is to sort the array in this given index range i.e., sort the elements of the array from arr[a] to arr[b] while keeping the positions of other elements intact and print the modified array.

sort - Manual, sort ( array &$array [, int $sort_flags = SORT_REGULAR ] ) : bool If two members compare as equal, their relative order in the sorted array is undefined. Be careful when sorting arrays with mixed types values because sort() can $ total = count($array); Here is no word about sorting UTF-8 strings by any collation. Find duplicates in an Array with values 1 to N using counting sort; Smallest number to be added in first Array modulo M to make frequencies of both Arrays equal; Count of Array elements greater than or equal to twice the Median of K trailing Array elements; Check if Array elements can be maximized upto M by adding all elements from another array

Comments
  • Could you explain, how is the size 1 count == 8 according to the provided input? Could you also define the groups and share an imperative style for loop code to explain what you intend to do as well?
  • Changes have been made to make this more clear. Thank You for your response.