IllegalStateException: “Duplicate key” for Collectors.toMap()

Question

Reference Question: Numbers which constitute the Maximum sum

I was writing a program which would print the elements which have constituted to the maximum sum. I have been able to pass through any random scenario but when my maximum sum constitutes of two sets, my code fails.

My code:

class Ideone {
    public static void main(String[] args) throws java.lang.Exception {
        Scanner reader = new Scanner(System.in);
        int TestCases = reader.nextInt();
        reader.nextLine();
        String[] output = new String[TestCases];
        String sss = "";
        String ddd = "";

        for (int k = 0; k < TestCases; k++) {
            int noofELements = reader.nextInt();
            reader.nextLine();
            String[] al = reader.nextLine().split(" ");
            List<Integer> numbers = Arrays.stream(al).map(Integer::valueOf).collect(Collectors.toList());
            Ideone mm = new Ideone();
            String maxi = mm.maximumm(numbers, ddd);
            sss = sss.concat(maxi);

        }
        System.out.println(sss);

    }

    public String maximumm(List<Integer> numbers, String sss) {
        int toIndex = 3, fromIndex = 0;
        List<Integer> result = new ArrayList<>();
        while (toIndex < numbers.size()) {
            Map<Integer, Integer> map =
                IntStream.range(fromIndex, toIndex).mapToObj(i -> new AbstractMap.SimpleEntry<>(i, numbers.get(i)))
                    .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));
            // find max of sublist
            int maxOfSub = numbers.subList(fromIndex, toIndex).stream().max(Integer::compareTo).get();
            //update indexes
            fromIndex = map.get(maxOfSub) + 2;
            toIndex += fromIndex;

            result.add(maxOfSub);
        }
        int lastMax = numbers.subList(fromIndex, numbers.size()).stream().max(Integer::compareTo).get();
        if (lastMax > 0) {
            result.add(lastMax);
        }
        result = result.stream().sorted(Integer::compareTo).collect(Collectors.toList());
        //System.out.println(result);
        sss = sss.concat(result.toString().replace(", ", "").replace("]", "").replace("[", ""));
        return sss;
        //  return result.stream().reduce(0,Integer::sum);
    }
}

For example when i am giving a input of 4 5 4 3 , then maximum sum of non adjacent elements is 8 , which would be made from 4 4 or 5 3.

My full code is working fine, just that i am not able to get both results in my final result.

My Error Log:

Exception in thread "main" java.lang.IllegalStateException: Duplicate key 0 at java.util.stream.Collectors.lambda$throwingMerger$0(Collectors.java:133) at java.util.HashMap.merge(HashMap.java:1254) at java.util.stream.Collectors.lambda$toMap$58(Collectors.java:1320) at java.util.stream.ReduceOps$3ReducingSink.accept(ReduceOps.java:169) at java.util.stream.IntPipeline$4$1.accept(IntPipeline.java:250) at java.util.stream.Streams$RangeIntSpliterator.forEachRemaining(Streams.java:110) at java.util.Spliterator$OfInt.forEachRemaining(Spliterator.java:693) at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:481) at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471) at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708) at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:499) at Ideone.maximumm(Ideone.java:47) at Ideone.main(Ideone.java:27)

Error is pointed to this line: result.add(maxOfSub);

Any help would be nice :)

Answer 1

The reason of this error is that you have a duplicated <key> when you call the Stream.collect(). Remember, this method performs mutable reduction operation on the stream elements. So when your call:

.collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));

Here, you are defining the <keys> of a Map object as the <values> of Entry<index, values> defined by the Stream.mapToObj() method. Now, when in your data test you have 4, 5, 4, 3, it means, you are trying to create the <key> for the number 4 twice. Therefore, you got this IllegalStateException.

But how can I fix this?

Very simple, just switch the definition of your Map object from <values, indexes> to <indexes, values> in the Stream.collect() call. How can I do this? Well, just replace the Map.Entry::getValue with Map.Entry::getKey and vise versa, like this:

.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

Also, there is better equivalent by using the IntStream.boxed() method. This method returns a Stream consisting of the elements of this stream, each boxed to an Integer. For me this is the best way to convert a List object into a Map object like this:

Map<Integer, Integer> map = IntStream
        .range(fromIndex, toIndex)
        .boxed()
        .collect(Collectors.toMap(i -> i, i -> numbers.get(i) > 0 ? numbers.get(i) : 0));

Notice that I'm using this expression i -> numbers.get(i) > 0 ? numbers.get(i) : 0 to assign the <values> of the Map object. Why are you doing this? Because, we need to track remove the negative numbers so I replaced them with zero. The Stream.filter() method is an alternative, but the Map object will not contain the filtered elements.

However, this modification will affect how you are updating your indexes, because now the map values are the <values> and not <indexes> as shown in this line:

fromIndex = map.getOrDefault(maxOfSub, toIndex - 1) + 2;

To fix this you just need convert get the <index> from the corespondent <value> like this:

fromIndex = IntStream
        .range(fromIndex, toIndex)
        .filter(i -> map.get(i).equals(maxOfSub))
        .findFirst()
        .orElse(toIndex - 1) + 2;

Alternative solution

Now, the above information will only solve the IllegalStateException. However, I found that there is another error. If I use this array of numbers 1, 9, 1, 7, 7, 5, 4, 1, 6, the max sum of non adjacent numbers should be [9 + 7 + 5 + 6] = 27 but your code got [9 + 7 + 6] = 22. So I tried to find a solution for this here:

public class Ideone
{
    public static void main(String[] args)
    {
//        List<Integer> numbers = Arrays.asList(4, 5, 4, 3);
//        List<Integer> numbers = Arrays.asList(1, 9, 1, 7, 7, 5, 4, 1, 6);
        List<Integer> numbers = Arrays.asList(-1, 7, 8, -5, 4, 9, -2, 3);

        String sss = "";
        String ddd = "";
        Ideone mm = new Ideone();

        List<List<Integer>> maxi = mm.findMaxSumNonAdjacentStream(numbers, numbers.size());
        System.out.println(Collections.singletonList(maxi));

    }

    public List<List<Integer>> findMaxSumNonAdjacentStream(List<Integer> numbers, int size)
    {
        int fromIndex = 0;

        Map<Integer, Integer> maxSumMap = IntStream
                .range(fromIndex, size)
                .boxed()
                .collect(Collectors.toMap(i -> i, i -> numbers.get(i) > 0 ? numbers.get(i) : 0));

        Map<Integer, List<Integer>> indexMap = IntStream
                .range(fromIndex, size)
                .mapToObj(i -> new AbstractMap.SimpleEntry<>(i, Collections.singletonList(numbers.get(i))))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

        maxSumMap.replace(1, Math.max(numbers.get(1), numbers.get(0)));

        List<Integer> maxValList = maxSumMap
                .entrySet()
                .stream()
                .filter(entry -> entry.getKey() > 1)
                .map(entry -> {
                    int index = entry.getKey();
                    int prevOne = index - 1;
                    int prevTwo = index - 2;
                    int prevValOne = maxSumMap.getOrDefault(prevOne, 0);
                    int prevValTwo = maxSumMap.getOrDefault(prevTwo, 0);

                    int maxVal = Math.max(prevValOne, prevValTwo + entry.getValue());
                    boolean exclude = prevValOne > (prevValTwo + entry.getValue());

                    List<Integer> elements = new ArrayList<>();
                    if (prevValOne > 0 && exclude) {
                        elements = new ArrayList<>(indexMap.get(prevOne));
                    } else if (prevValTwo > 0 && !exclude) {
                        elements = new ArrayList<>(indexMap.get(prevTwo));
                    }

                    if (!exclude) {
                        elements.add(entry.getValue());
                        elements = elements.stream().sorted(Integer::compareTo).collect(Collectors.toList());
                    }

                    maxSumMap.replace(index, maxVal);
                    indexMap.replace(index, elements);

                    return index;
                })
                .collect(Collectors.toList());

        Integer max = maxValList
                .stream()
                .mapToInt(v -> v)
                .max().orElseThrow(NoSuchElementException::new);

        int lastMax = maxValList.stream().max(Integer::compareTo).orElse(-1);
        Integer maxVal = maxSumMap.get(max);

        List<Integer> result = maxSumMap
                .entrySet()
                .stream()
                .filter(entry -> entry.getValue().equals(maxVal))
                .map(i -> i.getKey())
                .collect(Collectors.toList());

        Predicate<Map.Entry<Integer, List<Integer>>> containMaxList =
                mapEntry -> result.contains(mapEntry.getKey());

        return indexMap.entrySet()
                .stream()
                .filter(containMaxList)
                .map(i -> i.getValue())
                .collect(Collectors.toList());
    }
}

Answer 2

You are trying to build an inverse map from a map with duplicate values, which causes duplicate keys. You must avoid this.

A map like

{0: 4, 1: 5, 2: 4, 3: 3}

cannot be inverted to

{4: 0, 5: 1, 4: 2, 3: 3}

because what would map.get(4) then be? 4 or 0?

The error happens in

// 1)
IntStream.range(fromIndex, toIndex)
    // 2)
    .mapToObj(i -> new AbstractMap.SimpleEntry<>(i, numbers.get(i)))
    // 3)
    .collect(Collectors.toMap(
                 Map.Entry::getValue, 
                 Map.Entry::getKey));

• 1) First you create an int range stream (0, 1, 2, 3)
• 2) then you create a Stream of SimpleEntry ((0: numbers[0]), (1: numbers[1]), (2: numbers[2]))

• 3) then you try to invert this as a map:

  {numbers[0]: 0, numbers[1]: 1...}

Answer 3

There are some duplicates <keys> in you values. Look:

Map<Integer, Integer> map =
                IntStream.range(fromIndex, toIndex).mapToObj(i -> new AbstractMap.SimpleEntry<>(i, numbers.get(i)))
                    .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));

How to solve it

You exchange the key-value in code Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey),so you got duplicate error.