Leetcode task. finding the maximum distance to the nearest neighbor in the cinema | JS

[@evgeniychip]

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

[@bbkit]

Спасибо за видео. Как по мне, так выглядит проще: var maxDistToClosest = function(seats) { let max = 0; let count = 0; let first = true; for (let i = 0; i < seats.length; i++ ) { if (seats[i] === 1) { if(first) { max = count; } count = 0; first = false; } else { count += 1; max = Math.max(max, Math.ceil(count/2)) } } return Math.max(max, count); };

[@frontendscience]

Классный вариант! Действительно вышло очень компактно!

[@08flashake]

вместо верхнего ифа(по поиску мест в начале), проще инициализацию сделать как let max = input1.indexOf(1); и цикл рабочий запускать от max соответственно

[@kirillzlobin7135]

Весь день сегодня пвтался решить, а оказалось все намного проще

[@kirillzlobin7135]

Интересное решение связать два цикла...👍

[@aboba86468]

Скину и свою писанину, основная идея была такая: найти индекс начала и длину самой большой последовательности нулей. Ну и вышло как-то многовато кода, плюс немного запутанно и неоправданно сложно, у вас попроще явно, а в комментах ещё лаконичнее нашёлся код) Ну, как говорится, зато сам. И кстати в моём решении можно было б сразу выдавать индекс нужного места) const maxDistToClosest = function (seats) { const seatsLen = seats.length; let maxFreeLen = -1, maxFreeIndex = -1, maxFreeLastIndex = -1; for (let i = 0, freeLen = 0, freeIndex = 0; i < seatsLen; i++) { if (seats[i] === 0) { if (freeLen === 0) { freeIndex = i; } freeLen++; } else { if (freeLen !== 0) { if (maxFreeLen < freeLen) { maxFreeLen = freeLen; maxFreeIndex = freeIndex; } freeLen = 0; } } if (i === seatsLen - 1) { if (maxFreeLen < freeLen) { maxFreeLen = freeLen; maxFreeIndex = freeIndex; } } } maxFreeLastIndex = maxFreeIndex + maxFreeLen - 1; if (maxFreeLen === -1) { return -1; } else { if (maxFreeIndex !== 0 && maxFreeLastIndex !== seatsLen - 1) { return Math.round(maxFreeLen/2); } else { return maxFreeLen; } } }

[@frontendscience]

Благодарю за решение! Классно что сам попробовал решить! Где-то у тебя закралась ошибка связанная с последними сидениями: Input [0,1,1,1,0,0,1,0,0] Output 1 Expected 2

[@aboba86468]

@@frontendscience Спасибо! Исправил) Во втором ифе в цикле во вложенном ифе вместо < надо было написать

[@frontendscience]

Хмммм.... все равно что-то не то Input [1,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0] Output 3 Expected 5

[@mykolastrashok9986]

За lengTh плюсую))) Сам так говорю, когда пишу)))

[@ittalker]

спасибо за Вашу работу 🔥😎

[@frontendscience]

И Вам спасибо за поддержку!

[@dmitryyegorov7792]

мне кажется splice работает за O(n) (поправьте, если не так), поэтому сложность будет в худшем случае O(n^2). Вот моё решение: function removeDuplicates(nums: number[]): number { let j = 1; for (let i = 1; i < nums.length; i++) { if (nums[i] !== nums[i - 1]) { nums[j] = nums[i]; j++; } } return j; };

[@МаксимЛибер-ф2н]

У меня получилось во так. Отличие от вашего решения: для проверки идет ли отсчет свободных мест с начала ряда создал переменную isStart, которая по началу true, при нахождении первой 1 менял isStart на false. А для проверки, нужно ли делить на 2, воспользовался тернарником, где проверял состояние переменной isStart и является ли arr[i] концом массива. Получилось короче, но не могу понять как тут с производительностью. Что скажите? function findMaxDistance(arr) { let max = 0; let countFree = 0; let isStart = true; for (let i = 0; i < arr.length; i++) { if(arr[i] == 1) { countFree = 0; isStart = false; } else { countFree++ max = Math.max(max, (i == arr.length - 1 || isStart) ? countFree : Math.ceil(countFree/2)) } } return max }

[@frontendscience]

Благодарю за решение! Эта часть получилась короче в записи. По производительности она такая же как и в видео. Но вот чего тут нет - так это учета сидений в конце ряда. Они должны считаться также как и вначале (без деления на 2). И вот из-за этого и выходит много кода, так как мы не знаем когда наступит конец и сколько сидений перед окончанием рядя свободны.

[@vadavur]

Добрый день! Классная задача, спасибо! У меня в ходе решения вроде как удалось уйти от магической двойки. Как вам такой вариант? function maxDistToClosest(seats) { let maxDist = 0; let currentDist = 0; let sittersOnSides = 0; for (let place of seats) { if (place) { sittersOnSides++; maxDist = Math.max(Math.ceil(currentDist / sittersOnSides), maxDist); currentDist = 0; sittersOnSides = 1; } else { currentDist++; } } return Math.max(currentDist, maxDist); }

[@frontendscience]

Классное решение вышло! Долго пытался понять как же оно работает. А потом как понял.... )) Магическая двойка все равно есть - но она настолько магическая что умеет превращаться в единицу по краям.

[@vadavur]

@@frontendscience Да, согласен, эта единица мозолила глаз, вроде хотелось и ее как-нибудь эдак обыграть, сохранив в осмысленно названной константе, но в итоге, видимо, не дожал)

[@alexforw5545]

Это просто идеально!

[@МаксимФёдоров-ы9ц]

Добрый день! Сколько Вам потребвалось времени на её решение? За сколько по Вашему мнению должна быть решена быть эта задача?

[@frontendscience]

За сколько я ее решил я уже не помню. А на собеседованиях (например в FAANG) на кодинг интервью дают 45 минут: за это время необходимо разобраться с условием, задать уточняющие вопросы, продумать алгоритм, еще задать вопросов, чтобы убедиться что алгоритм будет работать, написать код, озвучивая постоянно что пишешь, проверить что эта программа будет работать как задумано (без запуска в консоли), и разобрать сложность алгоритма по времени и по памяти. Еще один момент что вы можете изначально не знать самого оптимального алгоритма решения, но важно с чего-то начать а потом успеть оптимизировать свой код. Как-то так.

[@НазарВеличайший]

я попробовал через регулярные выражения, тож норм вроде

[@frontendscience]

А решение покажешь?

[@НазарВеличайший]

Front-end Science c Сергеем Пузанковым , блин, стыдно говорить, поторопился, сейчас начал проверять, чтобы отправить - есть ошибки

[@frontendscience]

Ниче, бывает. Как решишь - кидай! Сама идея интересная вообще.

[@gladfilm]

У меня вот что получилось ``` function maxDistToClosest(seats) { let max = 0; const seatsString = seats.join(''); const re = /[0]+/g; const matches = seatsString.matchAll(re); for (let match of matches) { if (match.index === 0 || match.index + match[0].length === seatsString.length) { max = Math.max(max, match[0].length); } else { max = Math.max(max, Math.ceil(match[0].length / 2)); } } return max; } ``` matchAll - это вообще легально?

[@НазарВеличайший]

@@gladfilm не могли бы дать комментарий к строке с условием if..??

[@ВероникаСампетова-ц8ж]

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

[@ВероникаСампетова-ц8ж]

решение let maxDistToClosest = (arr) => { let maxDist = 0; let currentDist = 0; arr.forEach((seat, index) => { if (seat) { currentDist = Math.ceil(currentDist / 2); if (maxDist < currentDist) { maxDist = currentDist } currentDist = 0 } else { currentDist += 1; } if(index === arr.length-1 && !seat) { if (maxDist < currentDist) { maxDist = currentDist } } }) return maxDist; }

[@frontendscience]

прикрепил в описание leetcode.com/problems/maximize-distance-to-closest-person/

[@frontendscience]

Благодарю за решение. Надо доработать: [0,0,0,0,0,1,0,0,0] - вот на таком тест кейсе падает.

[@LastDreamer]

while в начале функции - хорошее решения, даже не сразу понял как это должно работать (на практике такого приема не встречал). а вот дополнительный if внутри for - не очень. можно было после for написать условие if (count !== 0) {...} - решение получилось бы еще лучше

[@frontendscience]

Дело вкуса и кодстайла

[@LastDreamer]

@@frontendscience лишнее условие внутри цикла - это не «дело вкуса и кодстайла», если вы хотите показать производительный код (который подразумевается на задачах подобного рода). вы по сути производите избыточные вычисления в своём примере - и этому учите. не хорошо

[@LastDreamer]

ну и да, решение: var maxDistToClosest = function (seats) { let count = 0; let current = seats.indexOf(1); let end = seats.lastIndexOf(1); let max = Math.max(current, seats.length - end - 1); while (current < end) { current += 1; if (!seats[current]) { count += 1; } else { max = Math.max(max, Math.ceil(count / 2)); count = 0; } } return max; }

[@frontendscience]

@@LastDreamer Посмотри мои все остальные задачи на канале - они все в избыточных переменных в угоду читаемости. Эта избыточность не добавляет сложности к самому алгоритму, но зато легко понять можно что происходит. Именно это и нужно тут. В алгоритмических задачах на собеседовании не нужен продакшен реди код - нужен чистый и легко читаемый код. Как-то так! PS: В том числе и этот if :)

[@frontendscience]

@@LastDreamer Хорошее решение получилось.Благодарю! Хоть тут и 3 прохода по массиву - все равно сложность O(n) при этом выглядит очень лаконично!

[@ВиталийМорозов-в5ъ]

Если в ряду все места будут пустыми (то есть все элементы массива равны 0), то получим indexOutOfBound в первом цикле while

[@frontendscience]

Вы вероятно до этого писали не на js :) В js такого не будет - просто у нас вместо значения 0/1 будет undefined и while прервется

[@ВиталийМорозов-в5ъ]

@@frontendscience а, ну тогда ок. Просто я джавист))

[@jonsmusev]

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

[@frontendscience]

Отличная идея!

[@denisoleksyuk5346]

Перед просмотром видео моё решение)) Если я правильно вычисляю сложность алгоритма то тут должно быть O(n) ```js const input = [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]; // 4 const maxDistToClosest = (input) => { let farPlace = null; let start = null; for (let i = 0; i < input.length; i++) { const lastIdx = input.length - 1; if (input[i] === 0 && start === null) { start = i; } if ((input[i] > 0 || i === lastIdx) && start !== null) { if (i === lastIdx && input[lastIdx] === 0) { const diff = input.length - start; if (diff > farPlace) { return diff; } } if (farPlace < i / (start + 1)) { farPlace = i / (start + 1); start = null; } } } return farPlace; }; console.log(maxDistToClosest(input)); ```

[@frontendscience]

Благодарю за решение! Классно, что стараешься сам до видео решать! Отлично работает когда места в середине ряда, и в конце. Но вот если ряд начинается с пустых мест то лезут баги. [ 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0] вернул 7 вместо 3.

[@denisoleksyuk5346]

@@frontendscience да действительно я там перепутал start = null в конце надо на 1 строку вниз спустить. Вот так работает вроде норм. ```js const maxDistToClosest = (input) => { let farPlace = null; let start = null; const lastIdx = input.length - 1; for (let i = 0; i < input.length; i++) { if (input[i] === 0 && start === null) { start = i; } if ((input[i] === 1 || i === lastIdx) && start !== null) { if (i === lastIdx && input[lastIdx] === 0) { const distance = input.length - start; if (distance > farPlace) { return distance; } } const distance = i / (start + 1); if (farPlace < distance) { farPlace = distance; } start = null; } } return farPlace; };```

[@matsievichsasha]

Решил по другому. Ваше решение гараздо лаконичнее. Не судите строго, я учусь const maxDistToClosest = function (seats) { let max = []; let seatTaken = []; let n = seats.length - 1; for (let i = 0; i 0)) { //0....1 max.push(current); } else if ((i === k - 1) && (current !== n)) { //1....0 max.push(n - current); } else { let dist = Math.ceil((current - seatTaken[i - 1])/2); //...10001... max.push(dist); } } return Math.max(...max); } console.log(maxDistToClosest(input1));

[@frontendscience]

Класс!! Идея очень прикольная вышла - собрать список занятых, а потом работать с числами(позициями занятых мест - чтобы искать промежутки свободные). Не самый оптимальный вариант по памяти вышел, но идея клёвая. 💪

[@ИванДмитриев-ь7ц]

У меня получилось такое решение: const maxDistToClosest = (seats) => { if (!seats.includes(0)) { return 0 } let currResult = 1 let result = 0 for (let i = 0; i < seats.length; i++) { let prev = seats[i - 1] let curr = seats[i] let next = seats[i + 1] if (curr === 0) { if (prev === undefined && next === 0) { currResult++ } else if (prev === 0 && next === undefined) { currResult++ } else if (prev === 0 && next === 0) { currResult++ } } else { result = Math.max(currResult, result) } } return Math.max(currResult, result) }

[@aleksd286]

Const fn = arr => { const value = arr.toString().replace(“,”,””) if(value===“1000101”) return 2 if(value===“1000”) return 3 throw new Error(“Invalid input”) }

[@frontendscience]

🤣 искусственный интеллект прямо!

[@Декопитатор321]

моё решение) function maxDistToClosest1(seats){ let max = 0 let mas = [] let count = 0 let flag = true for(let i = 0; i < seats.length; i++){ if(seats[i] === 1){ flag = false mas.push(max) max = 0 } else if (seats[i] === 0) { max += 1 } if(seats[0] === 0 && seats[i] === 0 && flag) { count += 1 } } if(max < count){ max = count } let maxNew = Math.max.apply(null, mas) return max > Math.ceil(maxNew/2) ? max : Math.ceil(maxNew/2) }

[@andriiyatsenko1519]

function stayAway(arr){ arr=arr.join('').match(/0*/g); arr.pop() let max=0; for (let i = 0; i < arr.length; i++){ (i===0 || i===arr.length-1) ? max=Math.max(max, arr[i].length) : max=Math.max(max, Math.ceil(arr[i].length/2)) } return max } Имеет ли право на жизнь? Дайте знать