TheAlgorithms/Java · error · IllegalArgumentException

Keys must be distinct

Error message

Keys must be distinct

What it means

Thrown by OptimalBinarySearchTree.sortNodes after sorting keys when two adjacent keys are equal. BST keys must be distinct for the in-order sequence to be well-defined and for the DP to partition correctly. Message: 'Keys must be distinct'.

Source

Thrown at src/main/java/com/thealgorithms/dynamicprogramming/OptimalBinarySearchTree.java:114

            if (frequency < 0) {
                throw new IllegalArgumentException("Frequencies cannot be negative");
            }
        }
    }

    private static int[][] sortNodes(int[] keys, int[] frequencies) {
        int[][] sortedNodes = new int[keys.length][2];
        for (int index = 0; index < keys.length; index++) {
            sortedNodes[index][0] = keys[index];
            sortedNodes[index][1] = frequencies[index];
        }

        // Sort by key so the nodes can be treated as an in-order BST sequence.
        Arrays.sort(sortedNodes, Comparator.comparingInt(node -> node[0]));

        for (int index = 1; index < sortedNodes.length; index++) {
            if (sortedNodes[index - 1][0] == sortedNodes[index][0]) {
                throw new IllegalArgumentException("Keys must be distinct");
            }
        }

        return sortedNodes;
    }

    private static long[] buildPrefixSums(int[][] sortedNodes) {
        long[] prefixSums = new long[sortedNodes.length + 1];
        for (int index = 0; index < sortedNodes.length; index++) {
            // prefixSums[i] holds the total frequency of the first i sorted keys.
            // This lets us get the frequency sum of any range in O(1) time.
            prefixSums[index + 1] = prefixSums[index] + sortedNodes[index][1];
        }
        return prefixSums;
    }
}

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Deduplicate keys (decide which frequency to keep or sum duplicates) before calling optimize.
2. Validate distinctness at the source with a Set and fail loudly on collision.
3. Treat duplicate key as a data-quality error and report it upstream.

Example fix

// before
int[] keys = {10, 20, 10}; // duplicate

// after
Set<Integer> seen = new HashSet<>();
for (int k : keys) if (!seen.add(k)) throw new IllegalStateException("dup key: " + k);

Set<Integer> seen = new HashSet<>();
for (int k : keys) {
    if (!seen.add(k)) throw new IllegalStateException("duplicate key: " + k);
}

When it happens

Trigger: Duplicate keys in the input; keys read from a set that was supposed to deduplicate but didn't; merging two key lists without dedup.

Common situations: User-supplied identifiers with accidental repeats; data loaded from a non-unique column.

Related errors

• Input string must not be null
• Input array should not contain negative number(s).
• Keys and frequencies cannot be null
• Keys and frequencies must have the same length
• Frequencies cannot be negative

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/e01704ffe127dbcb. Report an issue: GitHub.