Cuadrados de un Array Ordenado (LeetCode 977)

Dado un array de enteros nums que está ordenado en orden no-decreciente, el objetivo es generar un nuevo array que contenga los cuadrados de cada número, también ordenado en no-decreciente. Este problema presenta una peculiaridad: al elevar al cuadrado un número negativo, este puede resultar en un valor mayor que el cuadrado de un número positivo más pequeño. Por ejemplo, (-5)² = 25 mientras que (3)² = 9.

Debido a esta característica, los valores más grandes después de la operación de cuadrado provendrán de los elementos con el mayor valor absoluto, que siempre se encuentran en los extremos del array original (ya sea el valor más negativo o el valor más positivo). Esto sugiere la aplicación de la técnica de doble puntero para una solución eficiente.

El algoritmo consiste en lo siguiente:

1. Inicializar dos punteros: uno en el inicio (ptrIzquierdo) y otro en el final (ptrDerecho) del array de entrada.
2. Crear un nuevo array resultadoCuadrados del mismo tamaño, donde almacenaremos los cuadrados ordenados.
3. Utilizar un índice (indiceEscritura) para rellenar resultadoCuadrados de derecha a izquierda (es decir, desde la posición más grande a la más pequeña), ya que estamos buscando un orden ascendente y los valores más grandes se encuentran primero.
4. En cada paso, comparar el cuadrado del número apuntado por ptrIzquierdo con el cuadrado del número apuntado por ptrDerecho.
5. El valor cuadrado más grande se asigna a resultadoCuadrados[indiceEscritura]. Luego, se decrementa indiceEscritura y se mueve el puntero cuyo valor fue utilizado (incrementando ptrIzquierdo o decrementando ptrDerecho).
6. Este proceso continúa hasta que ptrIzquierdo cruce a ptrDerecho.

public class Solution {
   public int[] SortedSquares(int[] inputNumbers) {
       int n = inputNumbers.Length;
       int[] squaredOrdered = new int[n];
       
       int ptrLeft = 0;
       int ptrRight = n - 1;
       int currentWriteIndex = n - 1; // Escribir desde el final para ordenar de forma ascendente

       while (ptrLeft <= ptrRight) {
           int squareOfLeft = inputNumbers[ptrLeft] * inputNumbers[ptrLeft];
           int squareOfRight = inputNumbers[ptrRight] * inputNumbers[ptrRight];

           if (squareOfLeft > squareOfRight) {
               squaredOrdered[currentWriteIndex] = squareOfLeft;
               ptrLeft++;
           } else {
               squaredOrdered[currentWriteIndex] = squareOfRight;
               ptrRight--;
           }
           currentWriteIndex--;
       }
       return squaredOrdered;
   }
}

Longitud Mínima de Subarray con Suma Dada (LeetCode 209)

Se nos proporciona un array de enteros positivos dataArray y un entero positivo targetSum. El objetivo es encontrar la longitud mínima de un subarray contiguo (un segmento consecutivo de elementos) cuya suma sea igual o mayor que targetSum. Si no existe ningún subarray que cumpla esta condición, la función debe retornar 0.

Enfoque de Fuerza Bruta

Una manera directa de abordar este problema es mediante un enfoque de fuerza bruta, que consiste en examinar todos los posibles subarrays contiguos. Para ello, se utilizan dos bucles anidados: el bucle exterior selecciona el punto de inicio de cada subarray, y el bucle interior se encarga de extender el subarray desde ese punto, calculando su suma. Si la suma alcanza o supera el targetSum, se registra la longitud y se actualiza la mínima longitud encontrada hasta el momento.

Aunque conceptualmente sencillo, este método tiene una complejidad temporal de O(N²), lo que lo hace poco práctico para arrays de gran tamaño debido a su ineficiencia.

public class Solution {
   public int MinSubArrayLen(int requiredSum, int[] numbers) {
       int minimumLength = int.MaxValue;
       
       for (int i = 0; i < numbers.Length; i++) { // Define el inicio del subarray
           int currentSum = 0;
           for (int j = i; j < numbers.Length; j++) { // Extiende el subarray hasta 'j'
               currentSum += numbers[j];
               if (currentSum >= requiredSum) {
                   int subarrayLength = j - i + 1;
                   minimumLength = Math.Min(minimumLength, subarrayLength);
                   break; // Ya que buscamos el subarray más corto, podemos salir una vez que encontramos uno válido
               }
           }
       }
       return minimumLength == int.MaxValue ? 0 : minimumLength;
   }
}

Enfoque de Ventana Deslizante (Sliding Window)

Para mejorar la eficiencia, se emplea la técnica de la ventana deslizante, que reduce la complejidad temporal a O(N). Esta aproximación utiliza dos punteros, windowStart y windowEnd, para definir dinámicamente el tamaño y la posición de un "ventana" sobre el array.

La estrategia es la siguiente:

1. El puntero windowEnd se mueve progresivamente hacia la derecha, expandiendo la ventana. Los elementos que ingresan a la ventana se añaden a currentWindowSum.
2. Una vez que currentWindowSum alcanza o supera el targetSum, hemos identificado un subarray válido. En este punto, se calcula y se registra su longitud, actualizando la minLength si es menor que cualquier otra longitud encontrada previamente.
3. Para buscar un subarray aún más corto que cumpla la condición, la ventana se "encoge" desde el lado izquierdo: el elemento en windowStart se resta de currentWindowSum, y windowStart se mueve hacia la derecha. Este paso de encogimiento se repite mientras currentWindowSum siga siendo mayor o igual que targetSum.
4. El proceso se repite, expandiendo la ventana con windowEnd y encogiéndola con windowStart, hasta que windowEnd recorra todo el array.

public class Solution {
   public int MinSubArrayLen(int targetValue, int[] dataCollection) {
       int smallestLength = int.MaxValue;
       int currentSum = 0;
       int windowBegin = 0; // Puntero de inicio de la ventana deslizante

       for (int windowEnd = 0; windowEnd < dataCollection.Length; windowEnd++) {
           currentSum += dataCollection[windowEnd]; // Añadir el nuevo elemento a la ventana
           
           // Mientras la suma de la ventana sea suficiente, intentar reducirla
           while (currentSum >= targetValue) {
               int currentWindowSize = windowEnd - windowBegin + 1;
               smallestLength = Math.Min(smallestLength, currentWindowSize); // Actualizar la longitud mínima
               
               currentSum -= dataCollection[windowBegin]; // Eliminar el elemento más a la izquierda de la ventana
               windowBegin++; // Mover el inicio de la ventana
           }
       }
       return smallestLength == int.MaxValue ? 0 : smallestLength; // Si no se encontró ninguno, devolver 0
   }
}

Generar Matriz Espiral II (LeetCode 59)

El problema consiste en generar una matriz cuadrada de n x n, rellenándola con números enteros consecutivos desde 1 hasta n² siguiendo un patrón espiral en sentido horario. Por ejemplo, para n=3, la matriz resultante sería:

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

La solución a este problema se basa en simular el proceso de llenado de la matriz capa por capa. Se mantienen cuatro variables para controlar los límites de la capa actual: filaInicio (fila superior), filaFin (fila inferior), columnaInicio (columna izquierda) y columnaFin (columna derecha). Los números se insertan en un bucle que recorre las cuatro direcciones principales: izquierda a derecha, arriba a abajo, derecha a izquierda y abajo a arriba. Después de completar cada una de estas cuatro direcciones para una capa, los límites se ajustan para enfocarse en la siguiente capa interna de la matriz.

El proceso de llenado se detiene cuando los límites de las filas (filaInicio y filaFin) o las columnas (columnaInicio y columnaFin) se cruzan, indicando que todas las celdas han sido rellenadas. Este algoritmo maneja de forma natural tanto matrices de dimensión par como impar sin requerir un tratmaiento especial para el centro de la matriz cuando n es impar.

public class Solution {
   public int[][] GenerateMatrix(int dimension) {
       int[][] spiralGrid = new int[dimension][];
       for (int r = 0; r < dimension; r++) {
           spiralGrid[r] = new int[dimension];
       }

       int currentFillValue = 1;
       int rowStart = 0;
       int rowEnd = dimension - 1;
       int colStart = 0;
       int colEnd = dimension - 1;

       // Continuar llenando mientras queden celdas por procesar
       while (currentFillValue <= dimension * dimension) {
           // 1. Rellenar de izquierda a derecha (fila superior)
           for (int c = colStart; c <= colEnd; c++) {
               spiralGrid[rowStart][c] = currentFillValue++;
           }
           rowStart++; // Mover el límite superior hacia abajo

           // 2. Rellenar de arriba a abajo (columna derecha)
           for (int r = rowStart; r <= rowEnd; r++) {
               spiralGrid[r][colEnd] = currentFillValue++;
           }
           colEnd--; // Mover el límite derecho hacia la izquierda

           // 3. Rellenar de derecha a izquierda (fila inferior)
           // Se debe verificar si los límites no se han cruzado antes de este paso,
           // especialmente para matrices con dimensiones impares
           if (rowStart <= rowEnd) {
               for (int c = colEnd; c >= colStart; c--) {
                   spiralGrid[rowEnd][c] = currentFillValue++;
               }
               rowEnd--; // Mover el límite inferior hacia arriba
           }
           
           // 4. Rellenar de abajo a arriba (columna izquierda)
           // Similar a la anterior, verificar límites antes de proceder
           if (colStart <= colEnd) {
               for (int r = rowEnd; r >= rowStart; r--) {
                   spiralGrid[r][colStart] = currentFillValue++;
               }
               colStart++; // Mover el límite izquierdo hacia la derecha
           }
       }
       return spiralGrid;
   }
}