Problema
El problema es combinar dos arrays que ya están ordenados en uno solo, sin utilizar memoria adicional. El primer array tiene espacio suficiente para contener ambos.
Solución en Java
Esta es una de las soluciones que llegan a pedir en las entrevistas técnicas:
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
}
}
Explicación
La clave está en recorrer los arrays **desde el final**. De esta forma evitamos tener que desplazar elementos y logramos una solución muy eficiente.
Complejidad
- Tiempo: O(m + n)
- Espacio: O(1)
Conceptos aprendidos
Two Pointers, manipulación eficiente de arrays y resolución in-place.
