{"record":{"id":"e01704ffe127dbcb","repo":"TheAlgorithms/Java","slug":"keys-must-be-distinct","errorCode":null,"errorMessage":"Keys must be distinct","messagePattern":"Keys must be distinct","errorType":"validation","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/dynamicprogramming/OptimalBinarySearchTree.java","lineNumber":114,"sourceCode":"            if (frequency < 0) {\n                throw new IllegalArgumentException(\"Frequencies cannot be negative\");\n            }\n        }\n    }\n\n    private static int[][] sortNodes(int[] keys, int[] frequencies) {\n        int[][] sortedNodes = new int[keys.length][2];\n        for (int index = 0; index < keys.length; index++) {\n            sortedNodes[index][0] = keys[index];\n            sortedNodes[index][1] = frequencies[index];\n        }\n\n        // Sort by key so the nodes can be treated as an in-order BST sequence.\n        Arrays.sort(sortedNodes, Comparator.comparingInt(node -> node[0]));\n\n        for (int index = 1; index < sortedNodes.length; index++) {\n            if (sortedNodes[index - 1][0] == sortedNodes[index][0]) {\n                throw new IllegalArgumentException(\"Keys must be distinct\");\n            }\n        }\n\n        return sortedNodes;\n    }\n\n    private static long[] buildPrefixSums(int[][] sortedNodes) {\n        long[] prefixSums = new long[sortedNodes.length + 1];\n        for (int index = 0; index < sortedNodes.length; index++) {\n            // prefixSums[i] holds the total frequency of the first i sorted keys.\n            // This lets us get the frequency sum of any range in O(1) time.\n            prefixSums[index + 1] = prefixSums[index] + sortedNodes[index][1];\n        }\n        return prefixSums;\n    }\n}\n","sourceCodeStart":96,"sourceCodeEnd":131,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/dynamicprogramming/OptimalBinarySearchTree.java#L96-L131","documentation":"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'.","triggerScenarios":"Duplicate keys in the input; keys read from a set that was supposed to deduplicate but didn't; merging two key lists without dedup.","commonSituations":"User-supplied identifiers with accidental repeats; data loaded from a non-unique column.","solutions":["Deduplicate keys (decide which frequency to keep or sum duplicates) before calling optimize.","Validate distinctness at the source with a Set and fail loudly on collision.","Treat duplicate key as a data-quality error and report it upstream."],"exampleFix":"// before\nint[] keys = {10, 20, 10}; // duplicate\n\n// after\nSet<Integer> seen = new HashSet<>();\nfor (int k : keys) if (!seen.add(k)) throw new IllegalStateException(\"dup key: \" + k);","handlingStrategy":"validation","validationCode":"Set<Integer> seen = new HashSet<>();\nfor (int k : keys) {\n    if (!seen.add(k)) throw new IllegalStateException(\"duplicate key: \" + k);\n}","typeGuard":null,"tryCatchPattern":null,"preventionTips":["Source keys from a Set to guarantee distinctness.","Decide a merge policy for duplicates (sum frequencies) before calling.","Validate distinctness at the data boundary."],"tags":["input-validation","duplicate-keys","dynamic-programming","bst"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}