Diagonal Traverse

Descripción del Problema

El problema, conocido como Diagonal Traverse (Recorrido Diagonal), nos presenta una matriz de tamaño M x N (M filas y N columnas). El objetivo es devolver un arreglo que contenga todos los elementos de la matriz, pero recorridos en un orden diagonal específico de "zig-zag".

Ejemplo:

Dada la siguiente matriz de 3 x 3:

Las diagonales se recorren en este orden:

1. Primera diagonal (hacia arriba): [1]
2. Segunda diagonal (hacia abajo): [2, 4]
3. Tercera diagonal (hacia arriba): [7, 5, 3]
4. Cuarta diagonal (hacia abajo): [6, 8]
5. Quinta diagonal (hacia arriba): [9]

Salida esperada: [1, 2, 4, 7, 5, 3, 6, 8, 9]

La Observación Clave (El "Insight")

Para simplificar el problema, se propone no intentar simular el movimiento de zig-zag directamente (lo cual implica manejar muchos índices y límites), sino buscar una propiedad matemática común.

La observación fundamental es: Todos los elementos que pertenecen a la misma diagonal comparten la misma suma de sus índices.

Si un elemento está en la posición (fila, columna), entonces:

• El elemento (0 + 0 = 0) pertenece a la diagonal 0
• Los elementos (0,1) y (1,0) tienen suma de índices 1
• Los elementos (0,2), (1,1), (2,0) tienen suma 2

Conclusión: Podemos agrupar los elementos en listas basadas en la suma de sus índices i + j.

La Estrategia de Solución

Una vez que agrupamos los elementos por su número de diagonal (i + j), notamos un patrón:

Al recorrer la matriz fila por fila, los elementos de una misma diagonal quedan guardados de arriba hacia abajo.

Pero el problema pide orden “zig-zag”:

• Diagonales pares (0, 2, 4…) deben ir hacia arriba
• Diagonales impares (1, 3, 5…) deben ir hacia abajo

Idea: invertir solo las diagonales pares.

Solución Paso a Paso (Código)

Paso 1: Inicialización

Definimos el número de filas (m) y columnas (n). Calculamos el total de diagonales como (M + N - 1). Creamos un vector de vectores:

int m = mat.size();
int n = mat[0].size();

// Creamos un vector de vectores para las diagonales
vector<vector<int>> diagonals(m + n - 1);

Paso 2: Agrupación (Bucketing)

Recorremos la matriz. Para cada elemento mat[i][j] calculamos la diagonal como i + j:

for (int row_index = 0; row_index < m; row_index++) {
    for (int col_index = 0; col_index < n; col_index++) {
        int diagonal_number = row_index + col_index;
        diagonals[diagonal_number].push_back(mat[row_index][col_index]);
    }
}

Nota: quedan ordenadas de arriba hacia abajo.

Paso 3: Construcción de la Respuesta e Inversión

Creamos el vector final ans. Iteramos sobre cada diagonal:

• Si el número de diagonal es par, invertimos con rbegin() y rend().
• Si es impar, usamos begin() y end().

vector<int> ans;
for (int diagonal_number = 0; diagonal_number < diagonals.size(); diagonal_number++) {
    if (diagonal_number % 2 == 0) {
        // Diagonal PAR: Invertir orden
        ans.insert(ans.end(), diagonals[diagonal_number].rbegin(), diagonals[diagonal_number].rend());
    } else {
        // Diagonal IMPAR: Mantener orden
        ans.insert(ans.end(), diagonals[diagonal_number].begin(), diagonals[diagonal_number].end());
    }
}
return ans;

Análisis de Complejidad

• Complejidad de Tiempo: O(M × N). Recorremos cada celda una vez y luego construimos el vector final.
• Complejidad de Espacio: O(M × N). Guardamos temporalmente todos los valores agrupados por diagonal.