TheAlgorithms/Java · error · IllegalArgumentException

Matrix must be square

Error message

Matrix must be square

What it means

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.

Source

Thrown at src/main/java/com/thealgorithms/graph/TravelingSalesman.java:120

        }
    }

    /**
     * Solves the Traveling Salesman Problem (TSP) using dynamic programming with the Held-Karp algorithm.
     *
     * @param distanceMatrix A square matrix where element [i][j] represents the distance from city i to city j.
     * @return The shortest possible route distance visiting all cities exactly once and returning to the starting city.
     * @throws IllegalArgumentException if the input matrix is not square.
     */
    public static int dynamicProgramming(int[][] distanceMatrix) {
        if (distanceMatrix.length == 0) {
            return 0;
        }
        int n = distanceMatrix.length;

        for (int[] row : distanceMatrix) {
            if (row.length != n) {
                throw new IllegalArgumentException("Matrix must be square");
            }
        }

        int[][] dp = new int[n][1 << n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][1] = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) == 0 || dp[u][mask] == Integer.MAX_VALUE) {
                    continue;
                }
                for (int v = 0; v < n; v++) {
                    if ((mask & (1 << v)) != 0 || distanceMatrix[u][v] == Integer.MAX_VALUE) {
                        continue;
                    }

View on GitHub (pinned to fdfb9a395b)

Solutions

1. 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].
2. Build the matrix with new int[n][n] so all rows are n-wide by construction, then fill only the needed cells.
3. Add a pre-check: Arrays.stream(matrix).allMatch(r -> r.length == matrix.length).
4. 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.

Example fix

// before
int[][] dist = {
    {0, 10, 15},
    {10, 0},      // ragged
    {15, 20, 0}
};
TravelingSalesman.dynamicProgramming(dist);

// after
int n = 3;
int[][] dist = new int[n][n];
dist[0][1]=10; dist[0][2]=15;
dist[1][0]=10; dist[1][2]=20;
dist[2][0]=15; dist[2][1]=20;
TravelingSalesman.dynamicProgramming(dist);

int n = distanceMatrix.length;
for (int[] row : distanceMatrix) {
    if (row == null || row.length != n) {
        throw new IllegalArgumentException("distance matrix must be square (" + n + "x" + n + ")");
    }
}
TravelingSalesman.dynamicProgramming(distanceMatrix);

When it happens

Trigger: 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.

Common situations: 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.

Related errors

• Weights matrix must be square
• Capacity matrix must not be null or empty
• Capacity matrix must be square
• Capacities must be non-negative
• adjacencyList size must equal vertexCount

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