{"record":{"id":"768561d0b6131bf4","repo":"TheAlgorithms/Java","slug":"matrix-must-be-square","errorCode":null,"errorMessage":"Matrix must be square","messagePattern":"Matrix must be square","errorType":"validation","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/graph/TravelingSalesman.java","lineNumber":120,"sourceCode":"        }\n    }\n\n    /**\n     * Solves the Traveling Salesman Problem (TSP) using dynamic programming with the Held-Karp algorithm.\n     *\n     * @param distanceMatrix A square matrix where element [i][j] represents the distance from city i to city j.\n     * @return The shortest possible route distance visiting all cities exactly once and returning to the starting city.\n     * @throws IllegalArgumentException if the input matrix is not square.\n     */\n    public static int dynamicProgramming(int[][] distanceMatrix) {\n        if (distanceMatrix.length == 0) {\n            return 0;\n        }\n        int n = distanceMatrix.length;\n\n        for (int[] row : distanceMatrix) {\n            if (row.length != n) {\n                throw new IllegalArgumentException(\"Matrix must be square\");\n            }\n        }\n\n        int[][] dp = new int[n][1 << n];\n        for (int[] row : dp) {\n            Arrays.fill(row, Integer.MAX_VALUE);\n        }\n        dp[0][1] = 0;\n\n        for (int mask = 1; mask < (1 << n); mask++) {\n            for (int u = 0; u < n; u++) {\n                if ((mask & (1 << u)) == 0 || dp[u][mask] == Integer.MAX_VALUE) {\n                    continue;\n                }\n                for (int v = 0; v < n; v++) {\n                    if ((mask & (1 << v)) != 0 || distanceMatrix[u][v] == Integer.MAX_VALUE) {\n                        continue;\n                    }","sourceCodeStart":102,"sourceCodeEnd":138,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/graph/TravelingSalesman.java#L102-L138","documentation":"TravelingSalesman.dynamicProgramming solves TSP via the Held-Karp bitmask DP, which requires a square distance matrix: dp[u][mask] indexes distanceMatrix[u][v] for every pair of cities. A ragged matrix (rows of differing lengths) would throw ArrayIndexOutOfBoundsException deep in the DP, so the method validates all rows match n up front.","triggerScenarios":"Passing a ragged 2D array where some row.length != distanceMatrix.length, e.g. {{0,1,2},{1,0},{2,1,0}} (middle row too short). Also passing a matrix built from list-of-lists converted with mismatched inner sizes.","commonSituations":"Parsing a CSV/edge-list into rows where some city has no outbound edges recorded (row left short), partial matrix population in a loop that skips i==j or missing pairs, or copy-paste errors in test fixtures.","solutions":["Ensure every row has length n — pad missing entries with a large sentinel (Integer.MAX_VALUE / 2) or 0 for self-loops distanceMatrix[i][i].","Build the matrix with new int[n][n] so all rows are n-wide by construction, then fill only the needed cells.","Add a pre-check: Arrays.stream(matrix).allMatch(r -> r.length == matrix.length).","If the graph is asymmetric or incomplete, confirm you intend a directed/weighted TSP and that absent edges are represented by a large finite cost, not a missing cell."],"exampleFix":"// before\nint[][] dist = {\n    {0, 10, 15},\n    {10, 0},      // ragged\n    {15, 20, 0}\n};\nTravelingSalesman.dynamicProgramming(dist);\n\n// after\nint n = 3;\nint[][] dist = new int[n][n];\ndist[0][1]=10; dist[0][2]=15;\ndist[1][0]=10; dist[1][2]=20;\ndist[2][0]=15; dist[2][1]=20;\nTravelingSalesman.dynamicProgramming(dist);","handlingStrategy":"validation","validationCode":"int n = distanceMatrix.length;\nfor (int[] row : distanceMatrix) {\n    if (row == null || row.length != n) {\n        throw new IllegalArgumentException(\"distance matrix must be square (\" + n + \"x\" + n + \")\");\n    }\n}\nTravelingSalesman.dynamicProgramming(distanceMatrix);","typeGuard":null,"tryCatchPattern":null,"preventionTips":["Allocate matrices with new int[n][n] so all rows are equal-length by construction.","When loading from edge lists, iterate both dimensions [0,n) to guarantee full coverage.","Add a unit test asserting squareness for matrix builders."],"tags":["graph","validation","matrix","tsp","ragged-array"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}