Найти максимум и минимум без Math.max/min

Решение

Поиск минимального и максимального элемента — базовая задача, которая показывает понимание алгоритмов и обработки граничных случаев. Хотя Math.max/min существуют, запрет на них заставляет написать собственную реализацию.

Подход 1: Простой цикл (классический)

interface MinMax {
  min: number;
  max: number;
}

function findMinMax(arr: number[]): MinMax {
  // Граничный случай: пустой массив
  if (arr.length === 0) {
    throw new Error("Array must not be empty");
  }
  
  let min = arr[0];
  let max = arr[0];
  
  // Начинаем с индекса 1, так как 0 уже обработана
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  
  return { min, max };
}

// Примеры:
console.log(findMinMax([3, 1, 4, 1, 5, 9, 2, 6]));
// { min: 1, max: 9 }

console.log(findMinMax([-5, 0, 5, 10, -10]));
// { min: -10, max: 10 }

Анализ:

• Временная сложность: O(n) — один проход по массиву
• Пространственная сложность: O(1) — только две переменные
• Обрабатывает пустой массив исключением
• Начинаем с индекса 1, так как первый элемент уже инициализирует min и max

Подход 2: С использованием reduce

function findMinMax(arr: number[]): MinMax {
  if (arr.length === 0) {
    throw new Error("Array must not be empty");
  }
  
  const result = arr.reduce(
    (acc, current) => {
      return {
        min: current < acc.min ? current : acc.min,
        max: current > acc.max ? current : acc.max
      };
    },
    { min: arr[0], max: arr[0] }
  );
  
  return result;
}

Преимущества:

• Функциональный стиль
• Более декларативно
• Аккумулятор содержит оба значения

Подход 3: Более компактный reduce

function findMinMax(arr: number[]): MinMax {
  if (arr.length === 0) {
    throw new Error("Array must not be empty");
  }
  
  return arr.reduce(
    ({ min, max }, current) => ({
      min: Math.min(min, current),
      max: Math.max(max, current)
    }),
    { min: Infinity, max: -Infinity }
  );
}

Особенность: здесь всё же используются Math.min/max (хотя это противоречит заданию). Используйте предыдущий вариант, если это запрещено.

Подход 4: С обработкой пустого массива (возврат null)

type MinMaxResult = MinMax | null;

function findMinMax(arr: number[]): MinMaxResult {
  if (arr.length === 0) {
    return null;
  }
  
  let min = arr[0];
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }
  
  return { min, max };
}

// Использование
const result = findMinMax([3, 1, 4, 1, 5]);
if (result) {
  console.log(result.min, result.max); // 1, 5
}

Подход 5: Для TypeScript с дженериками

interface MinMax<T> {
  min: T;
  max: T;
}

function findMinMax<T extends Comparable>(arr: T[]): MinMax<T> {
  if (arr.length === 0) {
    throw new Error("Array must not be empty");
  }
  
  let min = arr[0];
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i].compareTo(min) < 0) {
      min = arr[i];
    }
    if (arr[i].compareTo(max) > 0) {
      max = arr[i];
    }
  }
  
  return { min, max };
}

interface Comparable {
  compareTo(other: any): number;
}

Подход 6: Оптимизация для больших массивов (сравнение в тройках)

function findMinMax(arr: number[]): MinMax {
  if (arr.length === 0) {
    throw new Error("Array must not be empty");
  }
  
  let min = arr[0];
  let max = arr[0];
  
  // Обрабатываем по два элемента за раз (экономим сравнения)
  let i = 1;
  while (i < arr.length) {
    // Сравниваем два элемента между собой
    if (arr[i] < arr[i + 1]) {
      if (arr[i] < min) min = arr[i];
      if (arr[i + 1] > max) max = arr[i + 1];
    } else {
      if (arr[i + 1] < min) min = arr[i + 1];
      if (arr[i] > max) max = arr[i];
    }
    i += 2;
  }
  
  // Если нечётное количество элементов
  if (i === arr.length) {
    const last = arr[arr.length - 1];
    if (last < min) min = last;
    if (last > max) max = last;
  }
  
  return { min, max };
}

Оптимизация: этот метод требует примерно 1.5n сравнений вместо 2n.

Тестирование всех случаев

// Базовые случаи
console.log(findMinMax([3, 1, 4, 1, 5, 9, 2, 6]));
// { min: 1, max: 9 }

console.log(findMinMax([-5, 0, 5, 10, -10]));
// { min: -10, max: 10 }

// Граничные случаи
console.log(findMinMax([42]));
// { min: 42, max: 42 }

console.log(findMinMax([1, 1, 1, 1]));
// { min: 1, max: 1 }

console.log(findMinMax([-100, 100]));
// { min: -100, max: 100 }

console.log(findMinMax([0, -0]));
// { min: 0, max: 0 }

// Пустой массив
try {
  findMinMax([]);
} catch (e) {
  console.log("Error: Array must not be empty");
}

Сравнение подходов

Рекомендация для интервью

Начните с простого цикла — это наиболее понятный и эффективный подход. Обязательно обработайте пустой массив через исключение или null. Если спросят про reduce, покажите функциональный вариант.

Ключевые моменты:

• Инициализируем min и max первым элементом
• Начинаем цикл с индекса 1
• Проверяем пустой массив в начале
• Временная сложность O(n), память O(1)
• Оба сравнения независимы (не используем else)