Как найти минимальную длину подмассива содержащего все уникальные элементы массива?

Question

[Arturchick]

Например функция принимает массив цифр [1,1,1,3,2,1,3,2,2,2,1] и должна вернуть минимальную длину под массива содержащего [1,2,3], в этом случае [1,3,2] либо [3,2,1] то есть функция должна вернуть 3
Еще пример [1,2,2,2,3,4,2,2,2] тут ответ будет 6 => [1,2,2,2,3,4]

Comments

[Сергей Соколов]

Как не лучший вариант – перебрать все возможные варианты подмассивов. Хотя бы его вы сделали?

[Arturchick]

Сергей Соколов, сделал, но как раз проблема в том что это не наилучший вариант

[Сергей Соколов]

Arturchick, хорошо бы ссылку на codewars и код вашей попытки.

[Stalker_RED]

Arturchick, почему в третьем примере 6? Там двойки повторяются.

[Arturchick]

Stalker_RED, функция не должна возвращать количество уникальных элементов, а искать минимальную длину подмассива содержащего все элементы

Answer 1

[Rsa97]

Оптимальнее не делать полный перебор, а работать с двумя указателями.
Пусть в массиве N уникальных чисел.
1. Ставим первый указатель на первый элемент массива, второй на N-й элемент.
2. Проверяем подмассив от первого до второго указателя.
3. Если он не содержит всех чисел, то передвигаем второй указатель на один элемент. Если вышли за пределы массива, то возвращаем найденный минимум, иначе переходим к 2.
4. Обновляем минимум длины.
5. Если минимум равен N, то завершаем работу функции.
6. Передвигаем первый указатель на один элемент.
7. Переходим к 2.

Ещё можно попробовать оптимизировать проверку вхождения всех уникальных чисел с помощью ассоциативного массива и счётчика.
При перемещении второго указателя увеличиваем соответствующее значение в массиве, если оно было ноль, то увеличиваем счётчик уникальных.
При перемещении первого указателя уменьшаем соответствующее значение в массиве, если оно стало ноль, то уменьшаем счётчик уникальных.

Вариант на JS

function minUniqueSubarrayLength(arr) {
  const N = arr.filter((v, i, a) => i === a.indexOf(v)).length;
  let begin = 0;
  let end = -1;
  let uniques = {};
  let uniqCount = 0;
  let subLength = arr.length;
  let len = 0;
  while (true) {
    if (uniqCount < N) {
      end += 1;
      len += 1;
      if (end === arr.length) {
        return subLength;
      }
      uniques[arr[end]] = (uniques[arr[end]] ?? 0) + 1;
      if (uniques[arr[end]] === 1) {
        uniqCount += 1;
      }
      continue;
    }
    if (subLength > len) {
      subLength = len;
      if (subLength === N) {
        return subLength;
      }
    }
    uniques[arr[begin]] -= 1;
    if (uniques[arr[begin]] === 0) {
      uniqCount -= 1;
    }
    begin += 1;
    len -= 1;
  }
}

console.log(minUniqueSubarrayLength([1,1,1,3,2,1,3,2,2,2,1])); // 3
console.log(minUniqueSubarrayLength([1,2,2,2,3,4,2,2,2])); // 6
console.log(minUniqueSubarrayLength([1,1,1,2,3,3,4,1,1,1,1,1,1,4,3,3,3,2,1,1,1,2])); // 5

Comments

[Сергей Соколов]

в поиске возможно ветвление: 111233411111143332111 левая и правая изолированные друг от друга группы.

[Сергей Соколов]

minUniqueSubarrayLength([1,1,2,3,3,4,1,1,1,1,2,3,4,1,1,1,1,1,4,3,3,3,2,1,1])
//  5, а должно 4

[Rsa97]

Сергей Соколов, Да, я уже нашёл ошибку. Теперь правильно работает.

Answer 2

[profesor08]

Сама идея состоит в том, чтоб брать подмассивы включающие уникальные числа из основного массива, постепенно набирая все возможные варианты. Потом фильтруем в поиске наименьшего. Возвращаем его длину.
Алгоритм простой. Допустим число уникальных цифр 4, тогда берем с первого по 4е число и смотрим, если есть все уникальные, если да, то переходим к следующему этапу, если нет, то берем с первого по 5й элементы, проверяем и тд. Далее повторяем процедуру заново, но уже берем от второго элемента.

function minUniqueSubarrayLength(arr) {
  const uniqueCount = new Set(arr).size;
  const subArrays = [];

  for (let sliceStart = 0; sliceStart < arr.length - uniqueCount; sliceStart++) {
    for (let sliceEnd = sliceStart + uniqueCount; sliceEnd < arr.length; sliceEnd++) {
      const subArray = arr.slice(sliceStart, sliceEnd);
      const set = new Set(subArray);

      if (set.size === uniqueCount) {
        subArrays.push(subArray);
        break;
      }
    }
  }

  return subArrays.reduce((minSize, subArray) => {
    if (subArray.length < minSize) {
      return subArray.length;
    }

    return minSize;
  }, arr.length);
}

minUniqueSubarrayLength([1,1,2,3,3,4,1,1,1,1,2,3,4,1,1,1,1,1,4,3,3,3,2,1,1]); // 4
minUniqueSubarrayLength([1,1,1,2,3,3,4,1,1,1,1,1,1,4,3,3,3,2,1,1,1,2]); // 5
minUniqueSubarrayLength([1,2,2,2,3,4,2,2,2]); // 6
minUniqueSubarrayLength([1,1,1,3,2,1,3,2,2,2,1]); // 3