Задача из Собеседования в Amazon за 5 минут

Разбираем небольшую задачку, которую спросили на собеседовании в Amazon. Такие задачи надо уметь решать за 10-15 минут, но без опыта решения подобных задач найти самое быстрое решение может быть не просто.
Задача на литкоде: leetcode.com/p...
Пост на литкоде: leetcode.com/d...
Дисклеймер:
И задача, и пост на литкоде находятся в открытом доступе. Я к посту никакого отношения не имею и не могу гарантировать его правдивость.

[@sashalukin]

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

[@АлексРоман-й9ю]

На собеседовании в амазон: -Вы умеете не ходить в туалет 12 часов? -Да -Вы приняты.

[@and7770999]

На собеседовании в ЕА Games - Вы радикальная феминистка? - Да - Вы приняты.

[@lockstock5357]

После того когда находишь более менее краткий путь к нужному результату всегда так на душе приятно становится. Внутренний перфекционист удовлетворен.

[@igor_yanovich]

Неприятно только одно, чтобы найти этот краткий путь, пришлось перебрать все пути не краткие 🤣

[@СаняДоцент]

И всегда найдётся азиат, который сделает это быстрее и лучше)

[@and7770999]

Только под массовость такое решение не подойдет. А значит придется писать отдельный код под разные матрицы

[@and7770999]

Самый лучший путь решения - отдать любому индусу на аутсорс))

[@philipp4631]

5:10 ну как так-то хоть бы на словах надо было метод золотого сечения упомянуть да и вообще можно тупо делить пополам.

[@igor_yanovich]

Все эти задачки мне почему-то напомнили как один парень у нас в универе сдавал зачёты, подходил к одному спрашивал что спрашивает препод, потом к другому, потом к третьему, в общем так он перебирал абсолютно все варианты что спрашивал препод по конкретной лабе и потом сдавал её. Но стоило преподу однажды перед ним поставить новую задачу, которую он никогда ни у одного студента не спрашивал, как всё хорошее и закончилось.

[@andrewmurruvyov4359]

Вероятность появления такой пары оригинальных (преподаватель;вопрос) мала, поэтому метод опроса надежен

[@igor_yanovich]

@@andrewmurruvyov4359 Это я к тому, что нафига вообще рассматривать методы решения задач, ну вот знаете вы как решить эту конкретную задачу в гугл на миллион долларов в год, а дай вам новую как всё хорошее и закончится, и нифига вы её уже не решите, потому что вы как этот парень из универа, вместо того чтобы учиться решать самому, тупо спрашивал у всех и перебирал все возможные варианты, а сам решать так и не научился, надо учится самому решать, а не смотреть на решения других людей и думать что теперь я мега умный и сам смогу решить такую задачу. Как говорится: всё просто когда знаешь как, а если не знаешь, то и таблица умножения кажется мега сложной задачей.

[@andrewmurruvyov4359]

Экзамен сдаёт не тот кто умеет решать, а кто умеет сдавать, и на работу устраивается не тот кто может работать, а кто может проходить интервью

[@igor_yanovich]

@@andrewmurruvyov4359 как правило такие говноработники которые не умеют работать, а умеют устраиваться, потом долго не работают. потому что потом уже НАДО РАБОТАТЬ, а не сдавать 🤣🤣🤣

[@СтаниславВокеутов-ю2э]

@@andrewmurruvyov4359 а как этому научиться, если ты бездарь?

[@kirillschcerbinin7068]

как всегда кайф смотреть, хорошо сделано! подача отличная, даже я всё понял, не зная ничего об этом! давай еще и побольше лайв контента!)

[@baksonyan4ik]

Офигеть, до твоих видео вообще не решал алгоритмы и оказывается они намного легче чем я думал. Да и это видео просто change my mind

[@freedomtv2295]

Когда объяснение под рукой то кажется легче, чем есть на самом деле На самом деле самому решать не так легко

[@Hello-g5b3p]

А что забавнее, что эти задачи мало кто решает так изящно сам по себе, фактически все учат только принципы и шаблоны, которых не так много. Это большой труд, но как это помогает определить хорошего программиста - вопрос :)

[@baksonyan4ik]

@@Hello-g5b3p не программисту будет лень

[@Монологиожелезках]

@@Hello-g5b3p, всё зависит от того, для решения каких задач нужен программист. Хороший программист для одних, ужасен для других. Скажем, задача та же, только у в распоряжении лишь три регистра и только один из них имеет ёмкость достаточную для указания на ячейку в матрице, при этом никто не лимитирует алгоритм по времени. Практическое применение: микроконтроллер без ОЗУ, все прочие регистры заняты другими данными всей микропрограммы, а её частью является алгоритм, микроконтроллер может 16 MIPS, а управляет дверным замком (то есть, даже если на сравнение уйдёт 30000 выполненных операций для матрицы 6*7, то это всего лишь задержка 0,001875 секунды, что человек в принципе не в состоянии заметить, да и замок открываться в следствии наличия инерции засова всё равно будет открываться дольше). И написать надо всё естественно на ассемблере. Так что, да, очень актуальен вопрос - как определить хорошего программиста?

[@andreyradostny]

Такая чистая, приятная и понятная подача, спасибо!

[@sunrizz]

Удивительно, но почему то сразу пришел к такому решения 😮 Задача крута! Спасибо!

[@yjrus1807]

Блин, это так просто и так гениально... мне стыдно, что я не додумался до такого решения сам

[@noki1614]

жиза

[@alexanders8928]

ты просто всю жизь не курил и не бухал и мухоморы не жевал. А Бог - есть!

[@AwakenDrow]

@@alexanders8928 Обычно, когда вспоминаешь все мухоморные дела, ты уже сеньор))

[@and7770999]

Еще проще решение - копируешь цифры в чат gpt и просишь его найти нужное))

[@opusmode]

Это вообще не гениально. Это очень даже тупо.

[@progressiveaccount3270]

Отличный формат!

[@Nikolas_Z]

Я в целом решил таким же образом, только начинал с левого верхнего угла и не считаю, что этот метод менее эффективен. Просто в данном случае, у нас 4 столбца с числами меньше 14 и 2 с числами больше 14,но возможна и обратная ситуация

[@The14Some1]

опиши алгоритм

[@РоманБондарь-м3е]

При k=5 выгоднее начинать с левого верхнего угла, а при k=24 выгоднее начинать с правого нижнего угла. Поэтому начинают с середины, как в обычном бинарном поиске: либо с правого верхнего угла, либо с левого нижнего угла.

[@Magicrafter]

@@РоманБондарь-м3е Мне показалось правильными начинать с правого нижнего. Ну то есть если бы мне дали 5 минут подумать, то мой вариант был бы таким. Хоть и не оптимальный.

[@Монологиожелезках]

Левый верхний менее эффективен, нужно откатываться назад на 1 столбец упираясь в большее в следующем. Двигаться будем не по прямой (приближенной к прямой "траектории"), а "зигзагами". Представьте, что это не просто матрица, а пиксели на дисплее и каждая ваша выборка данных из матрицы закрашивает пиксель, увидите траекторию.

[@AHTOHMAK]

Я тоже не понял разницы начинать именно справа

[@goldstein1]

С возвращением, Саша. Так мало качественных разборов нынче!

[@whitesteel2909]

проблема взялась из ниоткуда и мужественно решена ... браво

[@SDesuu]

Так суть программирования в том что всегда появляются "проблемы" которые нужно "мужественно" решать)

[@martintopchyan4399]

we can do 2 binary searches, firstly we can go through the rows and find the right row(if the target is greater than the midRow's last element then startRow=midRow+1), and then do a binary search only for that row, in that case we will have O(logn + logm).

[@DavidPotskhishvili-gp1km]

This won't work. Try to find 8 using your algorithm in the example provided in the video.

[@dmitryzhuk220]

Однако решить с такой сложностью всё таки можно если заметить, что для произвольного элемента m[i][j]

[@mrseeker9075]

@@dmitryzhuk220 Не скажу что быстрее чем в видео нельзя решить, я как раз сейчас думаю над этим, но если элемент m[i][j] < k, то можно сказать лишь что наш элемент находится НЕ выше и левее, а иначе НЕ ниже и правее, то есть мы можем отрезать прямоугольную подматрицу в которой элемент не находится, но не выделить онную

[@dmitryzhuk220]

@@mrseeker9075 о, действительно, спасибо за уточнение

[@kiryl5476]

​@@mrseeker9075по идее матрицу можно нарезать на 4 меньшие матрицы (относительно ключевого элемента в центре) а потом рекурсивно повторять алгоритм до размера в 1 элемент и просто проверять этот 1 элемент на равенство. Единственное что есть риск переполнения стека на огромных матрицах

[@rumstas1381]

Вот честно поставил на паузу на 2:24: я бы использовал что-то типа волнового алгоритма. Начинаем с элемента (0;0) и смотрим всех его соседей (по 8 направлениям, где это возможно), если среди соседей нет числа К, то перемещаемся на позицию максимального числа; в нашем случае (1;1) со значением 5 и так до тех пор пока у текущего элемента не будет соседа со значением 5, ну плюс ещё условие выхода из цикла со значением false, если вдруг текущее значение стало больше К. Теперь по честному нажимаю play и смотрю дальше 😀

[@zemamba]

Александр, крутые видео, записывай ещё ) интересно было бы про все этапы собеседования услышать в одном ролике

[@ОлегКуликов-ж7щ]

Чувак, я ничего не понял что ты сказал. Но когда ты стал говорить, ты достучался до моего сердца

[@47clere]

Сразу подумал что нужно идти по диагонали. Вот только не объяснил почему с правого верхнего угла пошли. Без разницы с какого угла идти, числом может быть как ближе к наименьшему так и ближе к на большему, соответственно если искомое число например 2 то поиск будет максимально долгим. Решение этой задачи можно немного оптимизировать так: mid = (max + min) / 2 Если n < mid то идём по диагонали с верхнего левого угла, если n > mid то с правого верхнего угла. Дальше действуем без изменений.

[@lironblank6204]

если постараться можно уменьшить до O(log(n)+log(m)) для этого надо заменить нахождение спомощю шагов на два бинарных поиска

[@desmosmech7037]

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

[@smarthedgehog3185]

@@desmosmech7037 Признак конца поиска по строкам это два соседа один меньше другой больше бери меньший и ищи в этой строке

[@roket132]

@@smarthedgehog3185 "бери меньший и ищи в этой строке" Если я правильно понял, то из примера на доске, вы найдете стоблец (11, 12, 16...) Но в нем нет 14)

[@nano_investor]

Мне кажется человек не понял задачу. Но чтоб получить такую асимптотику надо сделать мёрдж, в один массив, но без пред обработки удачи.

[@smarthedgehog3185]

@@roket132 Мы ищем сначало строку а потом в строке нужное поле. В строке между 10 и 18 есть 14. 14 какраза в строе с 10

[@MasterSergius]

Пфф, нашел за секунду: вот оно число, на четвёртой строчке, в третьем столбце

[@ildarfattahov6441]

Спасибо за задачу. Кажется, что если на каждой строке или столбце, по которым мы передвигались из верхнего правого угла до 14, сделать бинарный поиск, то можно получить что-то около logN + logM

[@denisgluk431]

помойму можно матрицу намутить, в который ты больше одного шага по прямой не сможешь сделать

[@nester7315]

А зачем бинарный поиск? Мы по порядку идём. Он на больших массивах только замедлит.

[@and7770999]

А если матрица с рандомными числами будет? Придется переделывать

[@oleksiikolotylenko1004]

Ага)

[@dmytrozazulin1858]

Тоже возникла такая мысль. По сути, он для каждой строки ищет число, которое было бы меньше N, чтобы по этому столбцу далее найти число, котоое было бы больше N. И снова по строке, по столбцу и т.д.

[@danila_firstt]

отличное объяснение, надо больше таких накидать Александр)

[@TheAstralopitek]

оптимальное решение быстрее. основная логика та же, но начинать надо не с левого верхнего угла, а с "середины"матрицы. правда надо будет немного заморочиться с обработкой вариантов. зато средняя скорость решения примерно в 2 раза выше получится.

[@oleksandr2234]

Во-первых - 2 раза быстрее не получится, тк мы теряем возможность двигаться по диагонали в одном направлении - тк если число, которое мы ищем, например, больше "серединного" - то оно может быть как правее, так и ниже. А во-вторых O(n/2+m/2) = O(n+m). Так что усложняя себе жизнь, вы не получаете никаких бонусов.

[@TheAstralopitek]

@@oleksandr2234 да, я тоже об этом подумал, но в целом ожидаю что ускорение до 2 раз реально

[@mactepmactepctba3853]

Я конечно не эксперт, но я сразу нашел число 14. Было трудно, просто включил монитор на котором смотрел это увлекательное видео.

[@vasiliypupkin6311]

❤ хоть у тебя и мало разборов, но они очень информативные, может будет хотя бы по 3 задачи в неделю - контент мега полезный, особенно для джунов. В Яндексе дают похожие.

[@ILikeActions]

эх, не удалось решить самому так элегантно, не додумался до возможности начать справа сверху, только левый верх и правый низ рассматривал) отличный разбор!

[@diplodogs]

Примерно такое же решение с поиском таргетного числа вокруг текущего в голову пришло, Только мне пришло в голову стартовой точкой задать не верхний правый угол а середину (по аналогии с бинарным поиском). В результате при прогоне данной матрицы от 0 до 36, разница в шагах внутри цикла составила 214 (твое решение со стартовой точкой в углу) против 127 со стартовой точкой в центре. Центр находил абсолютно банально через Math.floor(arr.length / 2) и Math.floor((arr[0].length - 1) / 2); Вроде как шустрее почти в два раза получается :) Спасибо за задачу!

[@ТёмикГоловин-й8ц]

Тоже самое подумал, про центр сразу. Да и к тому же можно внести ещё одну оптимизацию, тем более если известен характер чисел (насколько случайные числа были отсортированы и какая случайность использовалась) Можно брать не крайний верхний угол, а относительный порядковый номер диагонали беря во внимание крайние значения таблицы. К примеру видим что таблица начинается с 1 и заканчивается 36. А надо найти число 14, тогда делим искомое число, на разницу начального числа таблицы и конечного. Получаем 0.4. Далее умножаем 0.4 на размерность таблицы и далее округляем числа. И получаем координату оптимального старта поиска, чем линейнее распределение, тем точнее будет координата старта.

[@The14Some1]

@@ТёмикГоловин-й8ц Никто не обещал линейного распределения. А где такие задания на собеседования даются?

[@ТёмикГоловин-й8ц]

@@The14Some1 Понятное дело не обещал. Просто так алгоритм будет работать быстрее на больших размерностях и при разных функциях распределениях и незначительно медленнее на малых размерностях и не линейных функциях распределения

[@bel8504]

Круто. А главное красиво.Лично мне первое пришедшее в голову решение было: 1) берем среднее по номеру число в средней строке. Если такого нет - ближайшее (к примеру 7 если всего 15. Или 8. Без разницы). Мысленно мы разделили по строке и столбцу на 4 секции. Если К меньше числа, то мы отсекаем все большие числа по строке и столбцу. И повторяем это всё. В программировании я совершенно не разбираюсь, думала с точки зрения математики скорее.

[@hod-pj]

была детская задачка отгадать число от 1 до 1024 за 10 попыток. тебе говорят больше или меньше задуманного то что ты назвал. лень проверять, но думаю такой способ более эффективен чем предложенный.

[@QuarkWasp]

Да, этот способ является самым эффективным и называется двоичным поиском.

[@OstapP]

​@@QuarkWasp, двоичный поиск работает с линейными массивами. Такую матрицу к линейному массиву свести очень дорого.

[@ybsnow]

Поставил на паузу, подумал недолго: кроме бинпоиска мыслей не возникло)

[@_Kio_]

Самое быстрое решение, которое я смог найти, вот такое: Находим центральную строку, бинарным поиском делим её на две части - до и после искомого числа. Проводим от этой точки мысленную горизонтальную и вертикальную линию, тем самым разделив таблицу на 4 части. Левый верхний угол выкидываем, там все числа меньше искомого. Правый нижний тоже выкидываем, там все числа больше. А в левом нижнем и в правом верхнем углах запускаем этот алгоритм рекурсивно. Получаем логарифмическое время посика. P.S. видос ещё не смотрел.

[@astashch]

мне тоже кажется делить на квадраты интересная идея, первое что пришло на ум, до просмотра решения)

[@diplodogs]

Отличное решение, масштабируемое! Тоже думаю надо отталкиваться от центра в этой задаче, путь из одного конца матрицы в другой может быть слишком долгим

[@yuvis_cr]

квадраты получаются только не квадратные в данной матрице

[@allex-all]

Как я и думал, можно за log(m+n)

[@lotgon911]

Ты можешь исключить только один квадрат за шаг

[@IlyaBoltaev]

можно еще бинарным поиском попрбовать. Делим на 4 квадранта, смотрим в каждом из них левое верхнее и правое нижнее, и сравниваем с искомым. Например, если первоначальным разбиением взять за центр 16, то правый нижний квадрант можно отсечь и левый верхний квадрант можно отсечь. Далее рекурсивно ищем в правом верхнем и в левом нижнем.

[@VishnevskyMike]

Тоже об этом подумал. Тогда сложно сложность О(log_2(m+n)). Еще быстрее выходит.

[@denisgluk431]

@@VishnevskyMike в две подматрицы залядывать часто придётся.. а это всё равно на начальную оценку похоже.. O(n)

[@IlyaBoltaev]

@@denisgluk431 нет. Даже если в 3 подматрицы придется заглядывать, оценка будет логарифмической, так как на каждой итерации пространство поиска сужается на множитель, а не на константу. А в более чем 3 подматрицы смотреть гарантированно будет не нужно.

[@АлександрКраснов-н5ж]

Друг, есть более быстрый способ. Первое, проверяем число в ячейке 1,1 и m,n убеждаемся что число К в середине и переборку начинаем с середины в таком случае получаем O((m+n)/2). Можно конечно и не проверять начало с концом тогда, тогда, если брать худший сценарий будет еще быстрее, однако если брать лучший сценарий то можно и без переборки сказать что нет числа в матрице

[@Rofelka]

Что есть середина матрицы 2х10? Мы должны курсор поставить в 1,5? А, может, в 2,6? Но мысль красивая с проверкой 1,1 и m,n. Если искомое число не в матрице (меньше наименьшего элемента или больше наибольшего), то выполним за 1 или 2 операции)

[@АлександрКраснов-н5ж]

@@Rofelka в предложенной Вами матрице 1,5 1,6 2,5 2,6 равнозначны

[@SayXaNow]

@@АлександрКраснов-н5ж Допустим дана матрица 100х200, надо найти число К=14. Вы начали с середины, там число 50. Все что вы теперь знаете, это то, что правую нижнюю часть можно отбросить. Но куда теперь вам дальше двигаться? Число К может быть в любой из трёх оставшихся областей. Причем оно может быть как левее середины, так и правее, как ниже середины, так и выше.

[@АлександрКраснов-н5ж]

@@SayXaNow точно, мой способ получается О(1.5 (m+n))

[@leofender5753]

@@SayXaNow а если дальше опять повторить ход в середину оставшейся области? то есть по сути всегда делим на 2 и сверяем....и того вместо 7 будет 5 ходов

[@anatolyshkerin3569]

Кажется, что задачу можно решить за О(log(m+n)). Надо в упорядоченной линии, которая похожа на диагональ матрицы( длина m+n) найти наибольшее число меньше искомого( это называется правосторонний поиск ). Следующее число будет больше искомого. Вместе они образуют матрицу 2х2. Осталось проверить оставшиеся два элемента матрицы на совпадение с искомым.

[@alexnedelin7646]

с левого верхнего угла на каждом шаге выбирать элемент правее и элемент ниже. сравнивать эти 2 соседних элемента и двигаться по пути наименьшего из выбранных пока не пересечемся с искомым или не превысим его значение. подход аналогичен описанному но только более понятен

[@Hello-g5b3p]

Найди по этому алгоритму число 7 или 11

[@The14Some1]

не работает. Тебя может увести слишком далеко вправо, или слишком далеко вниз.

[@Vitek_23]

До такого решения не додумался бы сам, по крайней мере за 10 минут. Спасибо за пример!

[@artemspiridovich2695]

но моя идея состояла в том чтобы идти исключительно по диагонали допустим слева направо... тобишь arr[0][0] далее arr[1][1] и так далее на перекрестии будет цифра либо отсекающая сектор точно меньше либо точно больше и потом нужно будет только вернуться от этой цифры вверх или вниз

[@Meafel]

проблема идти по диагонали в том, что ты не знаешь куда поворачивать как только найдешь значение больше искомого, а значит придется запоминать в какой момент ты повернул и в какую сторону, если же идти по вертикали/горизонтали и влево-вправо/вверх-вниз, то ничего запоминать не придется

[@leomysky]

Спасибо за видео Всё очень доступно

[@RedBallOfLove]

Жаль только, что на собесах не обеспокоены качеством кода, а только задачками. Каждый раз, когда приходится обновлять сервисы гугла: firebase, admob, playgames - молишься, как бы хуже не стало. Ошибки без исправлений годами висят. Примерчик: подключаешь любой самый ссаный рекламный провайдер и ANR в норме, подключаешь admob и ANR в космос летит.

[@The14Some1]

Странно, меня вот в одном из собеседований на трейни отшили именно по причине, что я не пользовался модулями и недостаточно явно поделил логику и вывод. А в другом отшили за то, что я это сделал, а они выбрали кандидатов, предпочёвших более простые решения.

[@ИванПетров-й3г6ъ]

Решил так же! Почти ) Понял, что надо идти лесенкой. Сперва в 1-й строке найти число большее к, сдвинуться к предыдущему индексу в строке, увеличить индекс по вертикали. Все, как вы описали. Единственное отличие - я пошел слева направо. Вам хорошо, вы видите все значения в массиве, а программа их не видит. Первое же левое число в строке может быть к! Или другое, достаточно "левое" число. Нет никаких преимуществ у больших чисел справа перед меньшими числами слева - к может стоять ближе как к левому, так и к правому краю. Неплохо было бы еще двоичный поиск min числа > к в 1-й строке добавить! Потому, как можно почти всю строку пропахать в поисках такого числа, а оно окажется ближе к краю, противоположной началу поиска. Спасибо за задачу! Понравилась.

[@Anton_K15]

Я так же подумал, но понял что делается одно лишнее движение каретки с лева на право. А потом в итоге каретка движется с права на лево и в низ.

[@inanimatorum]

Отлично, первая же идея была довольно близка. Осталось самую малость, научиться кодить 😅

[@VasyaFF]

Жара! Нравится мне программирование.

[@niqr7800]

Можно так же с левого нижнего угла начинать. Там работают теже правила, только в другом направлении

[@kaxan1407]

С левого верхнего угла тоже можно.

[@niqr7800]

@@kaxan1407 Вообще-то нет)) У тебя с обоих сторон числа больше в таком случае. Ты просто не можешь определить, куда идти

[@kaxan1407]

@@niqr7800 да, я понел что в общем случае это не сработает минут через 5 после написания коммента

[@MrJloa]

Видимо мы думаем по-разному. Двигаемся с 0,0 по главной диагонали пока значение ячейки не станет больше искомого (17) Далее просто проверяем все значения строки, столбца (17).

[@ПетроМетро-я6г]

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

[@denisgluk431]

Пойму тут O(n) получается, т.е. максимальный путь 2n.. меньше не придумаешь

[@АлГрин-з2ш]

@@denisgluk431 В этом алгоритме. Если начинать не с правого верхнего, а n/2 в первой строке и также потом, при спуске. Пример, n=1000, m=2

[@poster-bot]

а можно ведь и за 2*log(N). В начале бинарный поиск по колонке, проверяем верхнюю и нижнюю колонку. Если два последних числа в верхней и нижней колонке больше искомого идем внизу, если оба меньше вверх. Если в верхней колонке число меньше искомого, а в нижней нет - мы нашли нужную колонку за O(n) А дальше уже стандартный бинарный поиск по столбцу

[@Proezdom-zx2tl]

В принципе всё правильно. Но исходя из того-же бинарного принципа начинать надо не с краёв а с середины. То есть с числа 16. Ну и идти придётся не в одну сторону, а в зависимости от сравнения. В данном конкретном случае дойдём до 14 за 2 хода 🙂

[@Mustitz]

Ну да, первое желание всё-таки получить $O(\ln n + \ln m)$, а не $O(n+m)$...

[@SayXaNow]

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

[@dmitry7464]

@@SayXaNowтоже подумал о бинарном поиске

[@Proezdom-zx2tl]

@@SayXaNow Я вот как думаю: - В принципе даже условие задачи не совсем строгое - что такое самый быстрый (или оптимальный) алгоритм поиска? - В общем случае я вижу как минимум 2 интерпретации. - 1 - Минимальное количество шагов в среднем. - 2 - Минимизировать количество шагов для самого плохого случая. Очевидно, что алгиритмы получатся разные. Для второго алгоритма, особенно для большого количества рядов (например 1 000 000 000) не оптимально двигаться последовательно по лесенке. Надо целый массив разбивать на кучки (на 2, а лучше на 3), проверять граничные условия прыгая из одной в другую и убирать целые кучки (суб массивы). Когда осталась кучка небольшого размера (надо считать какого), тогда уже можно идти по лесенке от верхнего правого угла... Ну может я и не прав???

[@SayXaNow]

@@Proezdom-zx2tl Ну задача с подвохом. я всегда топил и топлю за бинарный алгоритм. В матрице случайных упорядоченных значений размером 2500х10000 он показывает скорость нахождения любого элемента в среднем за 67 шагов. Казалось бы - фантастика, ну что за лохи вообще топят за этот линейный аутизм, ведь налицо логарифмическая скорость. Но надо учесть один нюанс. могут попадаться квадратные блоки данных, в которых числа расположены особым образом и полностью удовлетворяют условию задачи (правее всегда числа больше, снизу от любого числа тоже всегда больше), но для которых не существует в принципе алгоритма быстрее, чем линейный ступеньками. И если вдруг в моей матрице мне попался именно такой блок размером 2500х2500 то максимально неудачный расклад для бинарного поиска составит 50000 шагов и примерно 15000 в среднем для любого числа такого блока. Не трудно посчитать что неторопливый линейный тут покажет лучший результат. И т.к. никаким способом нельзя быстро проверить попался нам такой блок или нет, я бы не рискнул использовать быструю бинарку для слишком больших квадратных матриц. Сначала бы убедился что большая сторона M превосходит меньшую N хотя бы в 5 раз. А если ярко выраженная прямоугольная длинная типа 1000х17000 - тут даже обсуждать нечего - только бинарный поиск. Страшилка конечно это все, да и вероятность мала нарваться на такое, поэтому юзаю бинарки и не заморачиваюсь. Но как минимум надо помнить теперь об этом. Такие вот любопытные подробности всплыли, когда занимался тестами.

[@natielsanti407]

Спасибо. С нетерпением жду следующего разбора.

[@gameflamedev]

То, что сразу полезло в голову: 1) Проходимся по каждому элементу первой строки и ищём первое число, которое будет больше k 2) Делаем то же, но для первого столбца 3) Ограничиваем область поиска k найденными ранее элементами массива 4) Используем любой поиск. В худшем случае ограничение у нас займёт O(n+m), а поиск - O(n1 * m1), где n1 и m1 - элементы-ограничители (при прохождении по каждому элементу).

[@ДаниилЧерных-к1б]

Ух-ты, тоже это в голову пришло

[@realvaniog]

Можно еще ограничивать область если найти число которое меньше k (не рассматривать левую верхнюю область). И тогда такое решение может быть даже быстрее чем то которое рассказали.

[@OstapP]

​@@realvaniog, объясните пошагово. Звучит как бред.

[@OstapP]

В худшем случае (k>18), а это почти половина возможных k, размер матрицы не уменьшается. Но ваше решение натолкнуло меня на другое. Нужно, чтобы опытный алгоритмист проверил, может я тоже не прав. Решение: 1) в первой строке доходим до последнего =к. Зачеркиваем для себя все, что ниже. 3) в уже ограниченой матрице идем по первому столбцу до последнего =к. Зачеркиваем для себя, все что левее. Проходки логично делать бинарным поиском. Если я все правильно понимаю по крайней мере в этой таблице за эти 4 этапа находим наше число. Если таблица больше надо пример, чтобы понять что дальше делать, но так мы гарантированно сильно уменьшаем зону поиска. Получается 2log(m) + 2log(n)

[@realvaniog]

@@OstapP Если нашли число меньшее k, то нам не подходят все числа которые (одновременно) левее и выше этого найденного числа (там все числа меньше k). Аналогично с числом большим k. Т.о любое число неравное k ограничивает нашу область поиска.

[@ПавелМельников-х8м]

Ваше решение занимает, на данном примере, 7 шагов. Мое 5-6. Именно с угла, откуда, по Вашим словам, нет смысла начинать. А именно. Смотрим первую цифру. Если =14, то тру. Если больше - фолз. Если меньше - делаем шаг n+1 и m+1. Т.е. по диагонали. Те же условия, за исключением того, что если больше 14, то проверяем 2 числа по краям диагонали. Итого, в конкретном примере, Ваше решение идет по числам 16-15-11-12-16-9-14, выдавая "тру" с седьмой проверки. Мое идет по 1-5-9-17-16-14 (или 1-5-9-17-14) выдавая результат с 5-6 раза. Всего, максимум шагов, для проверки всех чисел матрицы, у Вас может быть 10 (кратчайший прямой путь от верхнего правого до нижнего левого угла). В моем случае - 7. 5 на диагональ - 2 на проверку рядом с диагональю. (в данном примере, после числа 30 проверяется 36 и 27, если они были бы меньше или равны 14). Отсюда вывод - Ваше решение не оптимально. Могу кодом, если так проще воспринимать.

[@SayXaNow]

k = 18. Алгоритм за 7 шагов сказал, что такого числа нет. Двигатель шаттла №18 не запустился, ракета упала.

[@ПавелМельников-х8м]

@@SayXaNow примерно так, да. Проглючило. Даже не задумался, что оно не на диагонали может быть) Сам потом понял, но уже не стал ничего удалять)

[@core2mind]

Кажется, что ходить до границы матрицы из верхнего правого угла может быть расточительно. При какой-нибудь матрице 1e12 x 1e12 (абстрактная большая цифра). Может стоить добавить в код условие про то, что если k < верхнего левого угла || k > нижнего правого угла, то искать нет смысла (false).

[@VasillaRobocraft]

Ну как раз на этом этапе можно использовать бинарный поиск

[@dmytrozazulin1858]

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

[@core2mind]

@@dmytrozazulin1858 , по-моему вы либо не так интерпретируете мое сообщение, или не так интерпретируете условие. Простой вопрос: Если в правом нижнем углу матрицы значение, равное 500, может ли в матрице быть значение, например, 501? Если да, составьте пример такой матрицы, я посмотрю, как вы это сделаете, не нарушая условий

[@dmytrozazulin1858]

@@core2mind Ясно, я думал вы хотите внести коррективы в сам процесс поиска. А это просто проверка вырожденного случая.

[@core2mind]

@@dmytrozazulin1858 , ну это по сути внесение изменений в алгоритм поиска, но не в алгоритм скана матрицы самой. Если у нас матрица триллион x триллион, есть ли смысл долго по ней ходить, если за константное время можно сразу сделать вывод, что ходить по ней нет смысла. Я это хотел донести, если что. В алгоритме, представленном в видео, уже есть предварительные проверки перед сканированием матрицы, мой поинт был лишь в том, что возможно стоит расширить эти проверки.

[@yoptaman9000]

Хороший результат, линейный алгоритм оптимизированный для двумерного случая. Для еще более быстрого поиска можно бинарный поиском найти строку и далее найти столбец также бинарным поиском. Сложность будет еще меньше.

[@OstapP]

Ваш алгоритм даст быстрый неправильный овет для 11, 12, 15, 16, ....

[@yoptaman9000]

@@OstapP я написал не то что подумал, бинарным поиском искать и столбец и строку. Ответ будет правильным так как и там и там отсортированные множества

[@OstapP]

@@yoptaman9000 , можно этапно? Я не понял ваш алгоритм.

[@fallerviktor]

А если взять 1 число - середину матрицы, и смотреть если число меньше 14 смотреть правое и снизу; дальше выбирать то, которое больше 14 и меньше второго? И двигаться таким полукрестом. Как скорость оценить?

[@chalex2k]

А идея хорошая, если это правильный алгоритм, сложность будет log(n+m). По сути бинпоиск по диагонали

[@vb7038]

@@chalex2k Я проверил, правильный и работает

[@Azverin911]

Приходит такой чувак устраиваться грузчиком на склад амазон, а ему: реши -ка сначала задачу.

[@ПростоЧеловек-н7э]

Изменено: не работает( Мне кажется есть не менее эффективный способ, хотя хз насколько он будет лучше в коде. 1) делим количество строк на 2 (округляя) и начинаем с этой цифры. (В данном случае 3) 2) если число меньше то идем вверх, больше вниз. (В данном случае вниз, доходя до 10) 3) теперь также делим уже столбцы (и округляем, в данном случае это не нужно, но при изменении условий пригодилось бы), то есть мы на числе 14. 4) Если число меньше то идем в лево, если больше в право. Но в данной ситуации это не пригодилось. В чем же преимущество этого метода? Если считать именно колличество ходов их будет максимум 7. (Если ищем число 36) В случае описанном в видео 10. (Если ищем число 18)

[@desmosmech7037]

Найди число 11 по даному алгоритму

[@smarthedgehog3185]

@@desmosmech7037 Это просто крайний случай для бинарного поиска по строкам. Ничего не меняет. Бинарный поиск это метод сходящихся интервалов. Ты просто ускоряешь их сходимость деля на два длину. В Численных методах этот метод ещё называли поиском льва в пустыне :) Грубо говоря там можно и площади делить отрезком. Т.е. сначала делить матрицу по столбцам потом по строкам в зависимости от того какая часть длиннее.

[@ПростоЧеловек-н7э]

@@desmosmech7037 верно, спасибо что сказал.

[@DragonsLord76]

Можно ещё быстрее, если начинать проверку с любой цифры в центре матрицы. Тогда ты найдёшь ответ в среднем В ДВА РАЗА БЫСТРЕЕ, чем ты показал. Это вааще очевидно.

[@lalkaveka4417]

Первая (и последняя идея) 1)Проверить первый столбец и первую строку на наличие цифр больше 14 и отсечь их. В нашем случае матрица станет 4 на 4. 2) проверить в обратном порядке последний столбец и строку новой матрицы (4 на 4) и отсечь все, что меньше 14. (Осталось 2 на 2) 3) оставшуюся маленькую матрицу просто перебрать А потом я досмотрел видео и в очередной раз понял, что я тупой

[@vtemv]

Ловко ты мне в рекомендациях попался, не зря в гугле работаешь)

[@kpa3uk]

а если число столбцов очень большее? а К находится ближе в первой половине или еще ближе к левой части? ( не будет ли разумно сравнить число К с количеством столбцов так как данные в матрице натуральные числа и начать с самого максимального в котором столбце она может быть?)

[@Morideca]

Ну, прописать 4 алгоритма для старта с каждого угла. И выбирать угол в зависимости от этого числа. Но это лишний гемор) ТЕм более что условие задачи поставило конкретное число, а не рандомное

[@chto_to_ne_tak.]

все круто , он видео почаще бы )

[@SentoxV]

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

[@GlebNite]

Классное решение! Побольше таких видео :)

[@nikoland]

Блин, а я думал мы умные ) когда 20 лет назад в олимпиаде по матеше участвовал)) Спасибо за видос

[@thayornwarrior2785]

хочу быть таким же умным парнем как ты✊

[@k083r]

Можно сделать функцию, которая ищет в упорядоченном массиве заданное число, если не находит, то возвращает следующее по убыванию и его индекс. Тогда алгоритм выглядел бы так: делаем поиск в первой строчке [1..16] находим 11 и его индекс 3 делаем поиск в первом столбце [1..18] находим 10 и индекс 3 останется сделать поиск заданного числа в подстолбце (0, 3)-(3, 3) это числа [11, 12, 16, 17] и в подстрочке (3, 0)-(3, 3), где значения [10, 13, 14, 17] сложность не умею точно считать, но вроде должно быть в среднем 1.5*O(log n) + 1.5*O(log m), о том что можно идти змейкой как-то не догадался)

[@Евгений-ч9х3н]

Класс, я бы никогда так не догадался сделать, хотя очень правильный шаг

[@kirpayti]

Лять... То чувство, когда начал расписывать решение в комментариях, написал, смотришь видос - а тут то же самое решение, и если оставить коммент, то ты будешь выглядеть дурачком каким-то, который зачем-то переписал из видоса, а если удалить, то спрашивается: нафига писал тогда.. хахаха

[@alexanderspeshilov839]

Бинарным поиском можно, только их не 1, а 4 нужно написать (за 10 минут можно не успеть). Пусть сначала область поиска - весь массив. 1. Находим (бин. поиск) последний элемент в первой строке, не превосходящий искомого. Выкидываем область правее данного элемента (там все элементы больше искомого). 2. Находим (бин. поиск) последний элемент в первом столбце, не превосходящий искомого. Выкидываем область ниже данного элемента (там все элементы больше искомого). 3. Находим (опять бин. поиск) первый элемент в последней строке, который больше или равен искомому. Выкидываем область левее данного элемента (там все меньше). 4. Находим (и опять бин. поиск) первый элемент в последнем столбце, который больше или равен искомому. Выкидываем область выше данного элемента (и там все меньше). Повторяем для полученной меньшей области, пока она не схлопнется до 0 или 1 элемента.

[@KanalReal]

Красавец, решил задачи, прошел собес и сидишь карточки товаров верстаешь😂

[@artemspiridovich2695]

а вообще можно совместить и сделать тройное решение тобишь находить быстро точку входа допустим цифру 17 потом от нее идти влево вниз и одновременно вверх вправо

[@AlexeyMihaylovBSS]

Задача понятна. Возникает вопрос, а почему идём с правого верхнего угла? Чисто логически можно идти с любого угла. Принцип одинаковый. С другой стороны если вопрос стоит в скорости то можно попробовать идти с центра. Это если требуется среднюю скорость поиска уменьшить.

[@nikolayvavilin583]

Если идти допустим с левого верхнего. Видим 1, а надо найти 14. Куда идти? Вправо или вниз?

[@oleksandr2234]

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

[@MrYuriyP]

Если на то пошло, то оптимальней сначала найти угол с наиболее близким числом и плясать от него. Код увеличится, зато выпоняться будет быстрее всего для любого числа.

[@dmytrozazulin1858]

бред

[@chalex2k]

Вау! Красивое решение! Сразу придумал бинпоиск. И еще бинпоиском по первому и последнему столбцу можно убрать часть строк, в которых точно нет искомого числа. Но это асимптотику не улучшит.

[@kostyajan]

Правый верхний угол можно найти дихотомией, что даст еще меньшую оценку, О(logn + m). Далее идти по "диогоналям" можно не поэлементно а также дихотомией, что в общем случае даст O(log n + log m). Такое конечно за 15 минут не написать, но устно я бы обязательно упомянул про более оптимальные пути поиска.

[@АнтонДанильченко-е6н]

А зачем нужно первое отсечение? Есть инсайдерская информация, что мы так большую часть матрицы выкинем? Дихотомия по диагоналям мне то же пришла в голову, но сложность такого алгоритма останется прежней - O(n+m). Однако ожидаемая сложность такого подхода будет меньше, но не O(log(n)+log(m)), а O(log(n)*log(m)).

[@kostyajan]

@@АнтонДанильченко-е6н, первым отсечением мы сразу уменьшим прямоугольник с m * n до (m-k) * n. В примере на видео - верхний правый элемент с которого можно начинать это 11 (первый элемент меньше 14). Но да, точно, согласен, в случае дихатомаии , оценка будет O(log(m) * log(n)).

[@SayXaNow]

Совершено все верно. Использование дихотомии есть самый эффективный метод. Сам решил дихотомией через диагонали, не так сложно как кажется на первый взгляд, ибо алгоритм дихотомии всем известен наизусть. Диагональная дихотомия - эффективность log(n)^2, где n - наименьшая сторона. Но алгоритм требует рекурсии, т.к. матрица разбивается на каждом шаге на две валидных области, в которых снова применяем алгоритм. Чередующаяся дихотомия по строкам и столбцам - эффективность log(n)*log(m). Код чуть длиннее, но пишется по факту быстрее и понимается лучше. Не требует рекурсии - что огромнейший плюс. Окончательный вариант из видео - это фиаско. Применять последовательный поиск в упорядоченной последовательности - это провал собеседования.

[@АнтонДанильченко-е6н]

@@kostyajan Если по диагоналям отсекать оказывается эффективней, то зачем нужен первый шаг, который может отрезать неопределённое кол-во столбцов (в том числе и 0)?

[@ivanovserg8795]

Аналогично можно начинать с левого нижнего угла, только движемся наверх и вправо

[@alexanderegoroff]

поставив на паузу мне в голову пришло такое решение - идем сначала по первому столбцу и находим строку первый элемент которой БОЛЬШЕ искомого числа , найдя ее мы получаем строку в которой ищем (это предыдущая строка). Далее идем по первой строке и ищем столбец, первый элемент которого БОЛЬШЕ искомого значения, так мы получаем предельный номер столбца (он будет равен найденному минус один), до которого делать поиск в строке найденной на первом шаге. Далее идем по строке определенной на шаге один до столбца найденного на шаге 2 и ищем нужное значение

[@gobpblueex]

Красиво! Спасибо за разбор, все четко и по делу.

[@VasillaRobocraft]

Классная задача, спасибо

[@EvilYou]

я придумал решение только за m * log n. Ищу в каждой строке нужное число методом бинарного поиска. В общем-то самое элементарное решение если нужна временная сложность меньше, чем O(n * m) function isK(arr, num) { for (let i = 0; i < arr.length; i++) { let left = 0; let right = arr[i].length - 1; let center; while (left num) { right = center - 1; } else { left = center + 1; } } } return false; }

[@SkyHaven-si4lv]

ЛЕГЕНДА

[@Oleg-kw8wl]

Я вообще не программист, ничего в этом не понимаю и ни одного кода в жизни не написал, но, первое, что мне на ум пришло: проверить число с координатами n/2 и m/2 (округление не важно, можно в любую сторону). Если оно больше искомого, то это отсекает 1/4 массива. Дальше снова ищем некую середину и повторяем процесс. Если же оно меньше искомого, то это отсекает 3/4 массива. В любом случае, это на каждой итерации сильно сокращает объём поиска. Не судите строго. Возможно, вообще бред написал ) Не специалист )

[@2TenOClock2]

нет. ты все верно написал. просто тут маленькая матрица очень. а вот если там миллион строк на миллион столбцов то ой.

[@timur2887]

тут можно еще ускорить алгоритм, если выбор первой точки сделать на основе бинарного поиска, а не просто от правого верхнего значения

[@Qwerty-fn3rf]

Оч классно , спасибо 🔥

[@panfilovandrey]

Красивое решение, класс!

[@by_Fredijkeeeeeee]

Как увидел, сразу начал по диагонали, но не с того угла. Немного недодумал)) Тем не менее, внутренний "я" доволен собой xD

[@Apisinus]

Решил меньше чем за минуту, сначала доперев что анализ нужно диагональный проводить и потом уже, что начинать лучше справа налево)

[@Alexander_M61]

Как я (не программист) решал примерно такую задачу, не зная наверняка широко известных в узких кругах методов решения подобных задач. Думаю, что такой метод имеет название, но я назвал его для себя методом сжимающихся границ. Исходно, считаем, что искомое находится между 1-й (нижняя граница) и последней (верхняя граница) строкой. проверяем на средней (понятно, что округляем, промежуток нечётный). После проверки средняя строка становится или новый нижней границей или новой верхней и интервал уменьшается вдвое. И так, пока верхняя не станет равной нижней. После этого аналогичный поиск в этой строке, но уже по столбцам. Единственное, мне нужен был поиск в массиве из сотен или тысяч строк и столбцов и я делил интервал не пополам, а на 10 частей и, хотя сравнений было больше, сужал интервал в 10 раз. Думаю, что программисты знают более стандартные и быстрый способы, но мой работал, хотя я писал его на VisualBasic (самоучка). Основной проблемой было, что значения в матрице были дробные и нужно было найти значение "примерно" равное. Пришлось придумывать "примерное" сравнение (с заданной точностью), т.к просто округление могло происходить в разные стороны и последняя цифра отличалась. Но это уже другая история)))))

[@iqfunru]

А мне показалось, что надо начинать с середины матрицы по типу двоичного поиска: 16 > 14, поэтому примерно четверть матрицы вправо и вниз от 16-ти не подходит. И т.д....

[@DiHASTRO]

Ускорил видео в 2 раза, узнал за 2.5 минуты

[@khalaiattan7184]

Создать цикл for и сказать ему "Выстрой числа в ряд. До тех пор, пока он не будет равен 14" Он выстраивает числа по порядку до числа 14 и после закрывает цикл.

[@gNikro]

1. вариант смотрим строку начальное и конечное значение так понимаем есть ли в этой строке искомое число, далее когда поняли какая строка тем же бинарным поиском воспользуемся что бы найти число. 2. Взять самое левое число, самое правое, и так же самое нижнее левое, самое нижнее правое. На основе этого прикинуть в каком примерно месте распологается искомое число. На основе этого нужен хитрый рандомизатор который из получившегося множества будет выдавать индекс, и там уже сомтреть подходит ли этот индекс. Ну либо в получившемся регионе использовать вариант 1

[@ES-ng3el]

Красавчик. Подскажите, а вы менторством занимаетесь ?

[@Magomed-r]

Было интересно

[@Poli.Pavlovich]

Классная задача :)

[@Anton_K15]

Придумал такое же решение, но начинал с левой стороны, а когда прослушал решение, понял что я сделал лишнее действие - переводил каретку в правую сторону, а потом решал так же как и нужно в лево и в низ.

[@Selavy82]

Можно ещё сократить действий, идя бинарным поиском по верхнему столбцу, а не перебором - в общем случае это уменьшит кол-во шагов

[@ДимаРубин-т6с]

В худшем случае нет. В худшем следующий левый/нижний будет подходящим, а это уже выйдет в O(mlogm + nlogn)

[@namelessboar]

​@@ДимаРубин-т6с omnomnomnomnom

[@spirridd]

Верхний столбец... Интересно, надо записать.

[@leonidalexeev4098]

Для любого числа можно уменьшить фактическое время вычисления. Если определить с верхнего правого угла или с нижнего левого угла начать выполнение представленного алгоритма. Путем сравнения в два шага. Да, добавляется несколько действий. Но статистически это ухудшит время только для чисел, находящихся по центру. А фактически это увеличит скорость для всех остальных случаев, когда искомое находится дальше центра при отсчете с верхнего угла (начала пути алгоритма).

[@leofender5753]

тогда можно и вовсе чекать ячейки рандомно. Да не самый оптимальный вариант, будет стремится к середине, но зато подойдет для любой не отсортированной матрицы)

[@leonidalexeev4098]

@@leofender5753 это алгоритм поиска кратчайшего пути. Более оптимизированный чем в видео.

[@leofender5753]

@@leonidalexeev4098 да, но при рандоме есть шанс найти нужное число вообще за 1 ход)))

[@leonidalexeev4098]

@@leofender5753 так я предложил вариант не по рандому, а по алгоритму. За 10000 проходов матрицы размером больше 5 будет более быстрое выполнение.

[@nirnaeth3824]

Моё решение: В какой-то мере, перебор позиций матрицы будет необходим, хотя бы внутри единственной строки или столбца. Но, поле поиска можно сократить: Сверху: выбираются первые номера строк и столбцов, где первое число в них больше K Снизу: выбираются последние номера строк и столбцов, где первое число меньше K

[@nirnaeth3824]

Ладно, как и предполагал, не лучшее.

[@ЕвгенийПлясецкий-ч2т]

Я бы прошëлся по диагонали с левого верхнего угла вниз (1, 5, 9, 17), остановился бы, как только наткнулся на число, больше К, и в этой строке начал отстëгивать числа влево, до тех пор, пока не добрался бы до числа К (вернул бы тру), или пока не добрался бы до числа меньше К или до начала строки. Тогда бы я взял предыдущую строку и от числа по диагонали стал бы отстëгивать направо числа. Попалось бы число К - вернул тру, добрался бы до числа больше К или до конца строки - вернул фолс. Как-то так 🙃

[@SergSamixonGD]

Решение пришедшее на ум в первые 30сек. Ищем по диагонали с top left to bottom right. Находим искомое число на диагонали. Если его нет и следующее больше: проверяем только 2 числа: справа от меньшего и слева от большего. И все. Может где-то и протупил, но по идее должно работать.

[@DenisLyamets]

Просто и при этом очень круто! Спасибо!