Всем привет! Возможно, кто-то из читающих подумает: «Валидация Судоку? Легкотня!» Только на первый взгляд. Интересная задача с LeetCode, Top Interview 150, где важно не запутаться в трёх измерениях сразу. И так, не будем тянуть, поихали.

Условие. Оригинальное условие (с примером инпута) прикрепил к посту. Опишу на русском: Дана матрица 9*9, заполненная цифрами (кроме 0) и пустотами (по условию в инпуте будут точки вместо пустоты). Условие, которому должна соответствовать матрица: -Если в ячейке есть цифра, то она должна быть уникальная и в строке и в колонке и в боксе. При этом мы не решаем судоку, а только валидируем уже частично заполненную доску.

Суть. На вход дается двумерный массив. 1. У каждой цифры есть три измерения валидности (снизу картинка, где можно увидеть, что за измер-я имеются в виду):

• строка (row)
• колонка (col)
• 3×3-блок (box) 2. Мы можем проходить по массиву, а в процессе каким-то образом проверять все измерения для определения уникальности текущей цифры. Но как проходить все измерения? 3. Проход по измерениям в каж-й ячейке (в ручную, по всему массиву) очень сильно увеличивает время исполнения нашего кода (минимум 3 прохода по доске в разных измерениях). Вероятнее всего, такой подход вызовет отвал по таймауту на LС. Этот исход нам неинтересен. Есть очень хороший выход в таком случае: провести валидацию за 1 проход двум-ого массива. 4. Нам нужно “запоминать” все цифры, которые мы уже прошли. Но “запоминание” одних цифр недостаточно, так как нам это мало что дает. Необходимо также фиксировать индексы строк, колонок и box-ев, чтобы по ним уже проводить проверки. Таким образом, мы всегда сможем узнать, например: “А есть в данной колонке/строке/box-е подобная цифра?”. 5. Мы с легкостью можем определить к какой строке и колонке относится цифра, но для определения, к какому box она относится есть разные способы. Я использовал формулу: (номер_строки / 3) * 3 + номер_колонки / 3 .

Решение. Я определил в итоге для себя 2 решения: Первое и самое очевидное - использовать Map (3 шт. - для каждого выделенного ранее измерения). Ключ - это номер чего-либо (строки, колонки, бокса), а значение - определенная структура данных для хранения цифр. В результате - не слишком эффективно, поэтому скип. Второе - использовать массивы структур данных. Индекс элемента массива - это номер строки/колонки/бокса. Почему именно массивы, а не, например, ArrayList? Ну ответ прост - не хочется лишних действий. Использование массивов для меня показалось удобнее. В List пришлось бы вручную заполнить каждый элемент списка новым HashSet, иначе при обращении по индексу, которого нет, получили бы IndexOutOfBoundsException. В массиве же в этом случае получим null, а потом просто заполним пустой коллекцией, чтобы в следующий раз у нас был возврат уже созданный коллекции с определенным наполнением.

Из каких типов коллекций будут состоять массивы измерений? Я думаю, что ответ очевиден, ведь коллекция, которая выдает константное время для получения элемента + имеет метод сontains (который нам позволит проверять наличие той или иной цифры в измерении) - это HashSet. Алгоритм в итоге такой: 1. Создаем множества для каждого измерения: Set[] rowsValues = new Set[9]; Set[] colsValues = new Set[9]; Set[] boxes = new Set[9];

2. Начинаем классический проход по двумерному массиву. a. Пропускаем точки. b. Высчитываем номер текущего box по формуле, представленной ранее. c. Для текущей ячейки делаем проверки на то, что ни в 1 из измерений проверяемой цифры нет (если множество измерения еще не заполнено, то используем метод, который по индексу возвращает множество, либо создает его и заполняет в массиве, если оно еще null). Если так, то добавляем в них цифру из текущей ячейки. Ну а если хоть где-то нашлась такая же цифра → false.

Вот так мы и разобрались с этой задачей. Как мне кажется, оно довольна интересная. Пиши в комментах, попадалось ли что-то подобное на собесах👇🏽. Ссылка на мое решение на LeetCode. Сорри, если заметны траблы с форматированием. Большие посты в этой сырой версии сервиса писать не очень удобно.