0Pricing
Coding Interview Prep · Lección

Plantilla de divide y vencerás

Extraiga de merge sort la plantilla de tres pasos —dividir, conquistar y combinar— y aplíquela sistemáticamente a nuevas formas de problemas.

Plantilla de divide y vencerás es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué es divide y vencerás?

Divide y vencerás (D&C) resuelve un problema dividiéndolo en subproblemas independientes del mismo tipo, resolviendo cada uno de forma recursiva y combinando sus soluciones. La palabra clave es independientes: los subproblemas no comparten estado (a diferencia de la programación dinámica, donde se solapan). Ejemplos clásicos: merge sort, búsqueda binaria, quick sort, par de puntos más cercanos y multiplicación rápida de matrices. D&C suele conseguir un tiempo O(n log n) mediante esta plantilla de tres pasos.

# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP:  sub-problems OVERLAP (same sub-problem solved multiple times)

# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing

# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n)  [merge sort]
# T(n) = T(n/2) + O(1) → O(log n)     [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]

La plantilla de tres pasos

Todo algoritmo de D&C sigue tres pasos: (1) Dividir: separar el problema en dos (o más) subproblemas más pequeños, normalmente por el punto medio. (2) Vencer: resolver recursivamente cada subproblema. Defina un caso base para detener la recursión (normalmente n ≤ 1). (3) Combinar: fusionar o combinar las soluciones de los subproblemas para obtener la solución global. La creatividad reside por completo en el paso de combinación; dividir normalmente consiste simplemente en separar por el punto medio.

def divide_and_conquer(arr, lo, hi):
    # BASE CASE: trivial sub-problem
    if lo >= hi:
        return base_case_result(arr, lo, hi)
    
    # DIVIDE: split at midpoint
    mid = (lo + hi) // 2
    
    # CONQUER: solve sub-problems recursively
    left_result  = divide_and_conquer(arr, lo, mid)
    right_result = divide_and_conquer(arr, mid + 1, hi)
    
    # COMBINE: merge results
    return combine(left_result, right_result, arr, lo, mid, hi)

def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)

Merge sort como ejemplo canónico

Merge sort ilustra perfectamente D&C: dividir el array por el punto medio. Vencer ordenando recursivamente cada mitad. Combinar fusionando las dos mitades ordenadas en O(n). Todo el trabajo se realiza en el paso de fusión. Recurrencia: T(n) = 2T(n/2) + O(n). Según el caso 2 del teorema maestro: T(n) = O(n log n). Esta es la recurrencia de D&C más importante que debe memorizar.

def merge_sort(arr):
    # BASE CASE
    if len(arr) <= 1:
        return arr
    # DIVIDE
    mid = len(arr) // 2
    # CONQUER
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # COMBINE
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

print(merge_sort([5, 3, 8, 1, 9, 2]))  # [1,2,3,5,8,9]

Referencia rápida del teorema maestro

El teorema maestro resuelve recurrencias de la forma T(n) = aT(n/b) + f(n): caso 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Caso 2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Caso 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). En merge sort: a=2, b=2, f(n)=O(n), n^log_2(2)=n → caso 2 → O(n log n).

# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n)    → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1)    → a=2,b=2,f=1,n^1=n >> 1  → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2)  → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1)     → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree

recurrences = [
    ('Merge sort: 2T(n/2)+n', 'O(n log n)'),
    ('Binary search: T(n/2)+1', 'O(log n)'),
    ('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
    ('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)

Subarray máximo: enfoque de divide y vencerás

El enfoque de D&C para el subarray máximo considera que la respuesta está completamente en la mitad izquierda, completamente en la mitad derecha o cruza el punto medio. Para el caso que cruza el punto medio, se expande hacia la izquierda desde mid y hacia la derecha desde mid+1, tomando la suma máxima en cada dirección, y después se combinan ambas. Este enfoque D&C de O(n log n) es más lento que el algoritmo de Kadane, que es O(n), pero demuestra la plantilla de forma excelente y es una pregunta habitual de entrevistas sobre D&C.

def max_subarray_dc(nums, lo=None, hi=None):
    if lo is None: lo, hi = 0, len(nums) - 1
    if lo == hi: return nums[lo]
    mid = (lo + hi) // 2
    # Conquer
    left_max  = max_subarray_dc(nums, lo, mid)
    right_max = max_subarray_dc(nums, mid + 1, hi)
    # Cross-midpoint sum
    left_sum = curr = 0
    for i in range(mid, lo - 1, -1):
        curr += nums[i]
        left_sum = max(left_sum, curr)
    right_sum = curr = 0
    for i in range(mid + 1, hi + 1):
        curr += nums[i]
        right_sum = max(right_sum, curr)
    cross_max = left_sum + right_sum
    return max(left_max, right_max, cross_max)

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums))  # 6

Función de potencia: exponenciación rápida

Fast Power (LeetCode 50): calcule x^n en O(log n) mediante D&C. Si n es par: x^n = (x^(n/2))^2. Si n es impar: x^n = x × x^(n-1). Gestione los valores negativos de n con x^(-n) = 1/x^n. Cada llamada recursiva divide n por la mitad, por lo que la profundidad es O(log n). Este es un ejemplo claro en el que el paso de combinación consiste simplemente en una multiplicación: es trivial, pero eficaz.

def my_pow(x, n):
    if n < 0:
        return 1 / my_pow(x, -n)
    # BASE CASE
    if n == 0: return 1
    # DIVIDE and CONQUER
    half = my_pow(x, n // 2)
    if n % 2 == 0:
        return half * half          # even: x^n = (x^(n/2))^2
    else:
        return x * half * half      # odd: x^n = x * (x^(n/2))^2

print(my_pow(2, 10))   # 1024
print(my_pow(2, -2))   # 0.25
print(my_pow(3, 5))    # 243
print(my_pow(0, 0))    # 1

De un array ordenado a un BST

Convert Sorted Array to BST (LeetCode 108) utiliza D&C: toma el punto medio como raíz (lo que garantiza el equilibrio de altura), construye recursivamente el subárbol izquierdo a partir de la mitad izquierda y el subárbol derecho a partir de la mitad derecha. Esto produce un BST equilibrado en altura con una altura mínima de O(log n). La estructura de D&C refleja la búsqueda binaria: en cada nivel de recursión, el punto medio se asigna como raíz del subrango actual.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sorted_array_to_bst(nums):
    def helper(lo, hi):
        if lo > hi: return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])    # DIVIDE at midpoint
        node.left  = helper(lo, mid - 1)  # CONQUER left
        node.right = helper(mid + 1, hi)  # CONQUER right
        # COMBINE: already done by assignment
        return node
    return helper(0, len(nums) - 1)

def inorder(node):
    if not node: return []
    return inorder(node.left) + [node.val] + inorder(node.right)

root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root))  # [-10,-3,0,5,9] (sorted, proving BST property)

Cuándo divide y vencerás no es la mejor opción

D&C tiene costes adicionales: la profundidad de la pila de llamadas a funciones, el uso de segmentos de arrays (si no se utilizan índices) y el paso de combinación. Es óptimo cuando el paso de combinación es O(n) o menor. Cuando los subproblemas se solapan, D&C vuelve a calcular soluciones innecesariamente, por lo que se necesita programación dinámica. Cuando domina el paso de combinación (por ejemplo, con O(n²)), D&C no mejora los enfoques ingenuos. Sepa cuándo elegir cada opción: D&C para subproblemas independientes y programación dinámica para subproblemas solapados.

# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead

def fib_dc(n):
    if n <= 1: return n
    return fib_dc(n-1) + fib_dc(n-2)  # O(2^n)!

def fib_dp(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a+b
    return a  # O(n)

print(fib_dp(30))  # fast
# fib_dc(40) would take seconds — do not run large values!

Divide y vencerás para búsqueda binaria en una matriz ordenada

La búsqueda en una matriz 2D (LeetCode 240) cuyas filas y columnas están ordenadas puede resolverse con D&C: comience en la esquina superior derecha. Si current > target, muévase a la izquierda (elimina la columna). Si current < target, muévase hacia abajo (elimina la fila). Si son iguales, lo ha encontrado. Este algoritmo O(m+n) no es técnicamente un D&C recursivo, pero comparte la idea clave: eliminar la mitad del espacio de búsqueda en cada paso.

def search_matrix(matrix, target):
    if not matrix: return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1  # start top-right
    while row < m and col >= 0:
        val = matrix[row][col]
        if val == target:
            return True
        elif val > target:
            col -= 1  # eliminate this column
        else:
            row += 1  # eliminate this row
    return False

matrix = [
    [1,   4,  7, 11, 15],
    [2,   5,  8, 12, 19],
    [3,   6,  9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5))   # True
print(search_matrix(matrix, 20))  # False

Análisis del árbol de recursión

Para las recurrencias de D&C que no encajan en el teorema maestro, utilice el método del árbol de recursión. Dibuje cada nivel de llamadas recursivas y sume el trabajo de cada nivel. En merge sort, en el nivel k hay 2^k subproblemas de tamaño n/2^k. Trabajo por nivel = 2^k × O(n/2^k) = O(n). El número total de niveles = log n. Trabajo total = O(n log n). Este método visual funciona con cualquier recurrencia y ayuda a entender por qué D&C suele alcanzar O(n log n).

# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)

import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')

Comunicación en entrevistas sobre divide y vencerás

Al presentar una solución de D&C en una entrevista: (1) Exponga explícitamente los tres pasos: «Dividiré por el punto medio, resolveré recursivamente cada mitad y después combinaré fusionándolas». (2) Identifique claramente el caso base. (3) Derive la recurrencia: T(n) = 2T(n/2) + O(n). (4) Aplique el teorema maestro o el árbol de recursión para obtener O(n log n). (5) Mencione cuándo D&C es mejor o peor que otras alternativas (programación dinámica para subproblemas solapados y el algoritmo de Kadane para el subarray máximo).

# D&C interview template to memorize:
def dc_template(problem, lo, hi):
    # 1. BASE CASE (state it first)
    if lo == hi: return solve_base(problem, lo)
    # 2. DIVIDE
    mid = (lo + hi) // 2
    # 3. CONQUER
    left  = dc_template(problem, lo, mid)
    right = dc_template(problem, mid + 1, hi)
    # 4. COMBINE (this is where the algorithm-specific logic goes)
    return combine_results(left, right, problem, lo, mid, hi)

def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)

print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')

Comprobación rápida

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Resumen de la lección

En esta lección aprendió: divide y vencerás sigue la plantilla: caso base → dividir por el punto medio → vencer recursivamente → combinar; T(n) = 2T(n/2) + O(n) da O(n log n) según el caso 2 del teorema maestro; y D&C es óptimo para subproblemas independientes, mientras que se necesita programación dinámica cuando los subproblemas se solapan. A continuación aplicaremos D&C para contar inversiones en un array mediante un merge sort modificado.

Preguntas frecuentes

¿La lección «Plantilla de divide y vencerás» es gratis?

Sí — el texto completo de «Plantilla de divide y vencerás» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Plantilla de divide y vencerás»?

Extraiga de merge sort la plantilla de tres pasos —dividir, conquistar y combinar— y aplíquela sistemáticamente a nuevas formas de problemas. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Coding Interview Prep?

No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.

¿Cuánto tiempo toma la lección «Plantilla de divide y vencerás»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?

Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Plantilla de divide y vencerás
  2. Contar inversiones con merge sort modificado
  3. Elemento mayoritario: votación de Boyer-Moore
  4. Mediana de dos arrays ordenados
← Volver a Coding Interview Prep