{"record":{"id":"a72969fe8d7efc84","repo":"TheAlgorithms/Java","slug":"costs-must-be-non-negative","errorCode":null,"errorMessage":"Costs must be non-negative","messagePattern":"Costs must be non-negative","errorType":"validation","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/graph/HungarianAlgorithm.java","lineNumber":145,"sourceCode":"        }\n        return new Result(assignment, total);\n    }\n\n    private static void validate(int[][] cost) {\n        if (cost == null || cost.length == 0) {\n            throw new IllegalArgumentException(\"Cost matrix must not be null or empty\");\n        }\n        int c = cost[0].length;\n        if (c == 0) {\n            throw new IllegalArgumentException(\"Cost matrix must have at least 1 column\");\n        }\n        for (int i = 0; i < cost.length; i++) {\n            if (cost[i] == null || cost[i].length != c) {\n                throw new IllegalArgumentException(\"Cost matrix must be rectangular with equal row lengths\");\n            }\n            for (int j = 0; j < c; j++) {\n                if (cost[i][j] < 0) {\n                    throw new IllegalArgumentException(\"Costs must be non-negative\");\n                }\n            }\n        }\n    }\n}\n","sourceCodeStart":127,"sourceCodeEnd":151,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/graph/HungarianAlgorithm.java#L127-L151","documentation":"HungarianAlgorithm.validate throws this IllegalArgumentException when any cost[i][j] is negative. The Hungarian algorithm's potential/labeling math assumes non-negative costs; negative entries can break dual feasibility and produce incorrect assignments.","triggerScenarios":"Passing a cost matrix containing any negative cell, e.g. a discount represented as a negative cost.","commonSituations":"Using negative costs for 'bonus' assignments instead of subtracting a constant. Signed cost values from input not normalized. Penalty subtraction producing negatives.","solutions":["Shift all costs to non-negative by subtracting the minimum: cost[i][j] -= minCost.","Clamp: cost[i][j] = Math.max(0, val).","If using profit instead of cost, convert via cost = maxProfit - profit."],"exampleFix":"// before\nint[][] cost = { {-5, 2}, {3, 4} }; // negative cost\n\n// after\nint min = findMin(cost);\nfor (int i = 0; i < cost.length; i++)\n    for (int j = 0; j < cost[0].length; j++)\n        cost[i][j] -= min; // now all >= 0","handlingStrategy":"validation","validationCode":"int min = Integer.MAX_VALUE;\nfor (int[] row : cost) for (int v : row) min = Math.min(min, v);\nif (min < 0) {\n    for (int i = 0; i < cost.length; i++)\n        for (int j = 0; j < cost[i].length; j++)\n            cost[i][j] -= min;\n}","typeGuard":"boolean allNonNegative(int[][] cost) {\n    for (int[] row : cost) for (int v : row) if (v < 0) return false;\n    return true;\n}","tryCatchPattern":null,"preventionTips":["Shift costs to non-negative by subtracting the global minimum.","Convert profits to costs via cost = maxProfit - profit.","Clamp if shifting is undesirable."],"tags":["graph-algorithm","argument-validation","value-constraint","assignment-problem"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}