Reordering similar elements within an array

Question

I have a requirement where I need to group similar elements together within an original list.

For example:

I/P array:

[1, 2, 3, A1, B1, 4, B2, 5, 6, C1, B3, B4, 7, 8, 9, 10, A2, A3, 11, 12, A4, C2, D1]

Now I would like to group the elements starting with an alphabet such that all the elements belonging to a specific alphabet are together and would be placed right after the first occurrence of that alphabet.

O/P array:

[1, 2, 3, A1, A2, A3, A4, B1, B2, B3, B4, 4, 5, 6, C1, C2, 7, 8, 9, 10, 11, 12, D1]

One trivial solution that I came up with is to maintain a HashMap denoting the alphabets and its elements, Map<Character, Queue<Element>> and do the following steps:

1. Iterate through the list and if an alphabet is encountered, do one of the following:

   1.1 If the alphabet doesn't exist in the map, add it to the map with an empty queue, map.put('A', new LinkedList<>())

   1.2 If the alphabet exists in the map, then remove it from the original list and add it to its corresponding queue in the map, list.remove(element) and map.get('A').add(element)

2. Iterate through the original list again and when an alphabet is encountered, add its corresponding queue from the map right after it.

I think this solution would work but I am not sure if it might fail for an edge case or if it is an optimal one(even though its complexity is O(n)).

Can anyone suggest a better alternative?

Answer 1

Stream API may be used in this case:

1. Build a LinkedHashMap grouping by letter prefix or number in each input element and collect the elements with equal prefixes into sorted set (or sorted list if duplicates are possible)
2. Get the values of the intermediate map of step 1 and join the sets/lists into a single list/array using flatMap

String[] arr = {
    "1",  "2",  "3", "A1", "B1", "4", "B2",  "5",  "6", "C1", 
    "B3", "B4", "7", "8",  "9", "10", "A2", "A3", "11", "12", 
    "A4", "C2", "D1"
};

List<String> values = Arrays.stream(arr)
    .collect(Collectors.groupingBy(
        s -> s.matches("[A-Z]\\d+") ? s.charAt(0) : s,
        LinkedHashMap::new,
        Collectors.mapping(s -> s, Collectors.toCollection(TreeSet::new))
    )).values().stream()
    .flatMap(TreeSet::stream)
    .collect(Collectors.toList());
System.out.println(values);

Output

[1, 2, 3, A1, A2, A3, A4, B1, B2, B3, B4, 4, 5, 6, C1, C2, 7, 8, 9, 10, 11, 12, D1]