LeetCode task about collecting rainwater | JavaScript interview

[@gatrianL]

о, что то новое уже на просторах ютуба, с графическим объяснениям это просто бомба!

[@frontendscience]

Благодарим за поддержку! Рады, что понравилось!

[@anazkomult]

Прикольно что на литкоде есть тесты с огромными массивами. Типа решил задачу, а оказывается еще решать и решать. :) Спасибо за видео, очень крутой формат!

[@anton-vr5xw]

задача классная, ну а ваше графическое объяснение просто топ! спасибо)))

[@frontendscience]

Благодарю) Рад, что понравилось!

[@denis_ken]

Решил по-другому. Всю эту гористую местность разбил на уровни снизу вверх. И на каждом уровне просчитал количество воды. А те крайние выемки для воды, которые не ограждены стеной слева и справа - вычитаем. Такое решение мне кажется проще в понимании :) const input1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; // 6 const input2 = [4, 2, 0, 3, 2, 5]; // 9 function trap(height) { const max = Math.max(...height); let total = 0; for (let i = 0; i < max; i++) { let startWall = -1; let endWall = -1; height.forEach((el, idx) => { if (i >= el) total++; if (el > i) { if (startWall < 0) startWall = idx; endWall = idx; } }); total -= startWall + (height.length - (endWall + 1)); } return total; } console.log(trap(input1)); console.log(trap(input2));

[@SergeyMironenko-b5h]

Привет, спасибо за качественный контент) Вот мой варик : const calcWater = (intervals) => { let result = 0; let highest = 0; let currentIndex = 0; for (let i = 0; i < intervals.length; i++) { if ((intervals[i] >= intervals[currentIndex]) || intervals[i] === highest) { currentIndex = i; highest = 0; for (let k = currentIndex + 1; k < intervals.length; k++) { highest = Math.max(highest, intervals[k]) } } const min = Math.min(intervals[currentIndex], highest); if (intervals[i] < min) { result += min - intervals[i]; } } return result || 0; }

[@SerzhNesteruk]

Спасибо за интересную задачу! Моё решение получилось далеко не оптимальным (почему-то не учитывал, что массив heigth может содержать большие числа). Оформил его через создание матрицы рельефа (земля - true, пустота - false), потом вычислил сколько воды поместится в каждой строке матрицы и суммировал. Вот, делюсь: const trap = heigth => { const reliefMatrix = [], maxHeigth = Math.max(...heigth); for (let i = 0; i < maxHeigth; i++) { reliefMatrix[i] = heigth.map(v => i < v); } let water = 0; for (let row of reliefMatrix) { let leftSide = row.indexOf(true), rightSide = row.lastIndexOf(true), container = row.slice(leftSide, rightSide); water += container.filter(v => !v).length; } return water; }; P.S.:// Можно записать в одну строчку: const trap = heigth => Array.from(Array(Math.max(...heigth)), (_, i) => heigth.map(v => i < v)).reduce((water, row) => water + row.slice(row.indexOf(true), row.lastIndexOf(true)).filter(v => !v).length, 0);

[@SerzhNesteruk]

Это решение можно чуток сократить: const trap = heigth => { const maxHeigth = Math.max(...heigth); let water = 0; for (let i = 0; i < maxHeigth; i++) { let row = heigth.map(v => i < v), leftSide = row.indexOf(true), rightSide = row.lastIndexOf(true), container = row.slice(leftSide, rightSide); water += container.filter(v => !v).length; } return water; };

[@user-paint-alexandra]

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

[@alicenNorwood]

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

[@frontendscience]

Класс! Пусть так и будет! :)

[@GreenGotty]

Спасибо, задачка супер -- проста в условиях, сложна в решении! Денёк пришлось помозговать.. теперь пойду смотреть Ваше решение, наверняка оно легче!) А мой первый сабмишн таков: Runtime: 84 ms, faster than 64.22% of JavaScript online submissions for Trapping Rain Water. Memory Usage: 40.8 MB, less than 39.66% of JavaScript online submissions for Trapping Rain Water. var trap = function (height) { // total amount of water & city length var total = 0; var len = height.length; // less than 3 buildings cannot hold water if (len < 3) return 0; // find the first & last peaks as the preceeding/following water is discarded var firstPeak = findEdgePeak(); var lastPeak = findEdgePeak('last'); // one peak cannot hold water if (firstPeak == lastPeak) return 0; // calculate trapped water based on the map obj of the highest peaks return calcWater(mapAllPeaks()); function calcWater(map) { // loop map regions one by one for (let [p1, p2] of Object.entries(map)) { // calculate water lvl for region let waterLvl = height[p1] < height[p2] ? height[p1] : height[p2]; // coerce str prop to Number // add to total if below water lvl for (let i = (p1 | 0) + 1; i < p2; i++) { if (waterLvl > height[i]) { total += waterLvl - height[i]; } } } return total; } // can optionally be provided with "last" flag function findEdgePeak(position) { var peak = position == 'last' ? len - 1 : 0; for (let i = peak; height[next(i)] >= height[i]; i = next(i)) { peak = next(i); } return peak; function next(i) { if (position == 'last') return i - 1; return i + 1; } } // finds the next peak index (returns the last index of flat surfaces) function findNextPeak(start) { var peak; var rising = false; var i = start | 0; while (peak == undefined && i height[i]) { rising = true; } } else if (height[i + 1] < height[i] || i == lastPeak) { peak = i; } ++i; } return peak; } // TCO-friendly recursive fn // returns a map of {[peak index]: index of the largest following peak } function mapAllPeaks() { // pure data object to map to var map = Object.create(null); function mapPeaks(curPeak) { var maxPeak; map[curPeak] = findNextHighest(curPeak); curPeak = map[curPeak]; if (curPeak >= lastPeak) return map; function findNextHighest(prevPeak) { var nextPeak = findNextPeak(prevPeak); if (height[nextPeak] >= height[curPeak]) return nextPeak; if (!maxPeak || height[maxPeak] < height[nextPeak]) { maxPeak = nextPeak; } if (nextPeak >= lastPeak) return maxPeak; return findNextHighest(nextPeak); } return mapPeaks(curPeak); } return mapPeaks(firstPeak); } };

[@frontendscience]

ВОУ!!! Круто, что сам дошел до решения!!!

[@ВладПашковский-ц2э]

Всегда смотрю как вы решаете и понимаю, что в лоб лучше не решать, а подумать о сложности ахах, но всё же может кому-то будет интересно. While + for. Я перебирал каждый уровень графика снизу вверх и смотрел "послойно" на каком уровне где сколько воды лежит. let arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]//6 let arr1 = [4,2,0,3,2,5]//9 function trap(arr) { let result = 0 let arrIsEmty = false; while(!arrIsEmty){ let weDontHaveLeftNotZeroElementNow = true let lastDontZeroElementIndex; let countZeroElementsInRow = 0 for(let i=0; i

[@EvilYou]

Эту задачу уровня hard решил быстрее, чем большинство уровня middle. Решение методом двух указателей. Выбираю наименьший из двух краев и считаю, сколько воды поместится в близлежащий блок. Сложность O(n). По памяти O(1). function trap(arr) { let left = 0; let right = arr.length - 1; let maxLeft = arr[left]; let maxRight = arr[right]; let result = 0; while (left + 1 < right) { if (arr[left] < arr[right]) { left++; let current = arr[left]; if (current < maxLeft) { result += maxLeft - current; } else { maxLeft = current; } } else { right--; let current = arr[right]; if (current < maxRight) { result += maxRight - current; } else { maxRight = current; } } } return result; } Результат на leetcode: Runtime 49ms Beats 99.33%

[@Dimidrol14]

Годнота! Однозначно лайк и подписка!)

[@frontendscience]

Благодарю за поддержку! ;) приветствую!

[@aarovas]

Однозначно подписка. Спасибо автору❤️

[@frontendscience]

Благодарим! Рады Вам! :)

[@АлександрБагмут-т8я]

Очень интересно, благодарю! Моё решение получилось раза в 2-3 длиннее, а самое интересное, сколько разных вариантов решения предлагают люди!

[@Flamel001100]

Очень качественный контент, спасибо, готовлюсь к собеседованию по твоим видосам😎

[@frontendscience]

Рад, что полезно! Успехов!

[@a.osethkin55]

Какая интересная задача, хоть и простая. Спасибо! Я почему-то про интегрирование (дискретное) сразу подумал, т.е.площадь удава, который съел слона и похож на шляпу, посчитать, а потом вычесть..

[@talivel118]

Как идея для видео, можете запилить ролик, план развития js разработчика, ну или фронт енд, ну или что-то в этом роде, хотя думаю у вас там и так куча идей:)

[@egorpobylets6597]

Супер, спасибо!!!!

[@frontendscience]

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

[@viktorbrunza4880]

Лайк, однозначно

[@frontendscience]

Благодарим за поддержку!

[@IvanMenshenin]

Можно ещё так :) function trap (arr) { let sum = 0 const str = arr.join('') for( i = 0; i < arr.length+1; i++ ){ const left = Math.max.apply(null, str.substring( 0, i ).split('') ) const right = Math.max.apply(null, str.substring( i ).split('') ) const res = Math.min( left, right ) - arr[i] if ( res > 0 ) sum += res } return sum }

[@frontendscience]

Благодарю за решение! на литкод несколько тест кейсов не проходит - надо задебажить

[@IvanMenshenin]

​@@frontendscience Да, перепроверил своё решение. Во-первых сам себе трудностей создал по переводу массива в строку и обратно (хоть так тоже работает с входными данными из видео). Во-вторых, такой подход (с делением массива на два и проверке максимального числа в каждом) не пройдёт при большой длине массива. Поторопился, в общем :)

[@maximusprime2798]

Супер. Спасибо

[@wisarty]

Дякую

[@st.golubets3836]

Есть ещё один способ решить эту задачу за линейное время и константную память. Нужно найти самый большой элемент и его индекс (любой наибольший эл-т если их больше одного) и пройтись циклом слева, на каждой итерации обновляя максимальную высоту слева и высчитывая объем в клетке(так как мы уже знаем максимум с обоих сторон). Потом сделать то же самое, только справа. Мне это решение показалось проще, чем с указателями let trap = function(height) { let vol = 0 const glMax = Math.max(...height) const glMaxIndex = height.indexOf(glMax) let leftMax = 0 for (let i = 0; i < glMaxIndex; i++) { leftMax = Math.max(leftMax, height[i]) vol += Math.min(leftMax, glMax) - height[i] } let rightMax = 0 for (let i = height.length - 1; i > glMaxIndex; i--) { rightMax = Math.max(rightMax, height[i]) vol += Math.min(rightMax, glMax) - height[i] } return vol };

[@frontendscience]

Благодарю за решение! Интересно вышло! Алгоритм очень похож - но мы добавили еще один проход для поиска максимума. PS: с указателями на самом деле мы тоже одним из указателей найдем этот максимальный пик - и этот указатель на нем и останется до конца работы алгоритма.

[@s.i.9988]

точно, это уже не линейная сложность а двулинейная)

[@st.golubets3836]

@@s.i.9988 а по памяти пятиконстантная как минимум)

[@ramzin1109]

like

[@mtb-love-belarus]

while (left

[@frontendscience]

Как раз таки эта реализация требует

[@АрсенАрсанукаев-и5н]

Здравствуйте Сергей, очень нужна ваша помощь, дело в том что я уже в комментах написал проблему, но ютуб удалил коммент.Может мне на инст прислать проблему?или какой либо другой мессенджер

[@frontendscience]

Не вопрос, конечно, пиши в инст или на почту

[@vitliyscripter2802]

Будет видео о проектах для обучения?

[@frontendscience]

Будет!

[@frontendscience]

Приятного просмотра: kzbin.info/www/bejne/ZqbIZY1pjJWrbJI

[@devWave1]

я не посмотрел еще решение, но я решил просто нарезать данный массив на двухмерный и найти сумму всех нулей, расположенных между единицами :D arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; function trap(height){ arrFloors = []; maxValue = 0; sum = 0; height.forEach(item => { (item > maxValue) ? maxValue = item: false; }); for(i = 0; i < maxValue; i++){ arrFloors.push([]); for(j = 0; j < height.length; j++){ if(height[j] > 0){ arrFloors[i].push(1); height[j]--; }else{ arrFloors[i].push(0); } } } arrFloors.forEach(item => { for(i = item.indexOf(1); i < item.lastIndexOf(1); i++){ (item[i] == 0) ? sum++ : false; } }) return sum; } console.log(trap(arr));

[@vasiajulia4173]

Как открыть терминал как у вас,внизу,что бы можна было проверять работу кода?

[@frontendscience]

В вебшторме при клике на файл второй кнопкой есть команда run - это запустить выполнение этого js-файла с помощью node js. Откроется соответствующая вкладка внизу.

[@vasiajulia4173]

@@frontendscience Можна ли при помощи Vs code это зделать?

[@frontendscience]

@@vasiajulia4173 уверен, что можно, но не подскажу как, т.к. с VScode не работал

[@vasiajulia4173]

@@frontendscience Спасибо , я постараюсь разобраться,пока просто пишу код как у вас и пытаюсь вникать в суть)

[@frontendscience]

@@vasiajulia4173 успехов! Это хорошо, что Вы тренируетесь.

[@ІльченкоАртем]

Оба варианта очень крутые, но второй все таки круче даже просто потому что он короче) JS Frontend Backend Задачи Собеседование React

[@frontendscience]

Ценю твою поддержку)

[@Nikita-gn4bg]

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

[@st.golubets3836]

Вообще нет, но в яндекс нужно знать например, у меня были задачи на stack и указатели. В faang тоже нужно

[@frontendscience]

Благодарю, очень рад. Про алгоритмы и структуры данных, как уже написали, все зависит от компании. В основном джунов такое не спрашиваю, начинают примерно от миддла. Но компании по типу Google, Яндекс и пр. даже на уровне джунов требуют такие знания.

[@Nikita-gn4bg]

@@frontendscience Спасибо за ответ, просто недавно созрел для поиска первой работы, на первых двух собесах меня спросили про это hr, тут я и удивился и не был готов к такому, т.к. алгоритмами пользовался только на учебе в вузе на с++ несколько лет назад )

[@frontendscience]

@@Nikita-gn4bg странно что hr такое спрашивал. А что за город?

[@Nikita-gn4bg]

@@frontendscience спб upd: довольно странно собеситься по телефону с hr, она задавала вопросы по реакту, а я не понимал, что она хочет, как оказалось мне нужно было объяснить как из дочернего элемента изменять стейт родительского (ее формулировку я, к сожалению, не запомнил) Кстати отправил вам заявку на паблик интервью, буду надеяться, что услышимся когда-нибудь!

[@KaHcTpykTap]

Что за графический редактор?

[@frontendscience]

Это online сервис excalidraw

[@KuBa-tkm]

У меня только 1 вопрос почему здесь дизлайк? Всё понятно и ясно.

[@ОлексійУкраїна-й7г]

моща. спс

[@frontendscience]

))))) нзчт

[@SlavaTechnology]

Кто вообще придумал спрашивать задачи с Leetcode на собеседованиях. Вопрос конечно риторический.

[@nosokcinema1823]

function collectWater(integers: number[]) { let volume = 0; let currentMax = 0; let currentVolume = 0; integers.forEach(integer => { if (integer > currentMax) { currentMax = integer; volume += currentVolume; } if (currentMax > integer) { currentVolume += currentMax - integer; } }); return volume; } console.log(collectWater([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6 console.log(collectWater([4, 2, 0, 3, 2, 5])); // 9

[@blgarOk]

Задача красивая, спору нет. Алгоритмы решения и реализацию сам придумал? Или немножко где-то подсмотрел, видел похожее? Как то с трудом верится, что такое решение можно найти самому, даже имея приличный опыт)

[@EvilYou]

Как раз-таки опыт решает, особенно, если подобные задачи уже были решены до этого. А на этом канале они есть.

[@bipiwnik]

23:55 получаю почему-то 0 и 2 гугл вырезает коммент, не могу скинуть в codepen const input1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; // 6 const input2 = [4, 2, 0, 3, 2, 5]; // 9 function trap(height) { let maxLeft = height[0]; let maxRight = height[height.length - 1]; let left = 1; let right = height.length - 2; let total = 0; while (left

[@frontendscience]

привет! ютюб удаляет все комменты со ссылками. По твоему вопросу - у тебя ошибка в коде - ты поставил return total; внутри while - получилось что на первой же итерации ты вернул ответ из функции и не пошел дальше. return total должен быть после того как while отработает

[@bipiwnik]

@@frontendscience большое спасибо за разъяснение, прошу извинить за невнимательность) Приятно видеть оперативный ответ, на codepene тоже увидел ответ.

[@bipiwnik]

@@frontendscience а как можно попасть на собеседование к вам?

[@xxxxrat]

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

[@frontendscience]

Присылайте решение!

[@xxxxrat]

@@frontendscience const input1 = [0,1,0,2,1,0,1,3,2,1,2,1]; const input2 = [4,2,0,3,2,5]; function trap(input){ let waterCount = 0; for ( let i = 0; i < Math.max( ...input ); i++ ){ waterCount = waterCount + rowCount( input.map( item => { return (item - i > 0) ? 1 : 0 }) ); } function rowCount(row){ let result = 0; let minLeft = row.indexOf(1); let maxRight = row.lastIndexOf(1); for ( let i = minLeft; i < maxRight; i++ ){ if ( row[i] == 0 ) result ++; } return result; } return waterCount; } console.log(trap(input1)); console.log(trap(input2));

[@ahmadumarov2845]

const trap =(mount)=>{ if (mount.length === 1) { return 0 } let openCarier = false; let result = 0; for (let position of mount2) { if (position > 0){ openCarier = !openCarier } else { if (openCarier) { result += 1; } } } return result + trap(mount.filter(pos=>pos > 0).map(pos=>pos-1)) } сразу об этом решение подумал и сложность равна O(n)

[@maksymmitin4576]

function trap(height) { let result = 0; let left = 0; let right = height.length - 1; const max = Math.max(...height); const maxIndex = height.indexOf(max); let currentMax = 0; while (left < maxIndex) { currentMax = Math.max(currentMax, height[left]); result += currentMax - height[left]; left++; } currentMax = 0; while (right > maxIndex) { currentMax = Math.max(currentMax, height[right]); result += currentMax - height[right]; right--; } return result; }

[@ВоваКоренев-м8ж]

Привет, решил попробовать сделать задачу по твоем первому алгоритму решения, по тестам которые в видео вроде как прошло, но хотелось бы услышать твой фидбэк)) const trap = (height) => { let sum = 0; let maxLeftArr = []; let maxRightArr = []; let maxleftNum = 0; let maxRightNum = 0; let volume = []; for (let i = 0; i < height.length; i++) { if (height[i] < height[i - 1] && height[i - 1] > maxleftNum) { maxleftNum = height[i - 1]; maxLeftArr.push(maxleftNum); } else { maxLeftArr.push(maxleftNum); } } for (let i = height.length - 1; i >= 0; i--) { if (height[i + 1] > maxRightNum) { maxRightNum = height[i + 1]; maxRightArr.push(maxRightNum); } else { maxRightArr.push(maxRightNum); } } maxRightArr.reverse(); for (let i = 0; i < maxLeftArr.length; i++) { volume.push(Math.min(maxLeftArr[i], maxRightArr[i])); } for (let i = 0; i < height.length; i++) { if (volume[i] - height[i] > 0) { sum += volume[i] - height[i]; } } return sum; }; trap(arr1);

[@Neravarinn]

Осмелюсь выложить не оптимальное, но всё же МОЁ решение, как обычно... в лоб )) function trap(height) { var maxLine = Math.max.apply(null, height) var waterBlockCount = 0 for (let i = 1; i < maxLine + 1; i++) { entireUnit: for (let j = 1; j < height.length - 1; j++) { var nominal = height[j] if (nominal >= i) continue entireUnit else nominal = i - 1 leftUnit: for (let k = j - 1; k > -1; k--) { var leftValue = height[k] var countLeft = 0 if (leftValue > nominal) { countLeft = j - k break leftUnit } } if (countLeft === 0) continue entireUnit RightUnit: for (let l = j + 1; l < height.length + 1; l++) { var rightValue = height[l] var countRight = 0 if (rightValue > nominal) { countRight = l - j j = l - 1 break RightUnit } } if (countRight === 0) continue entireUnit waterBlockCount += countLeft + countRight - 1 } } return waterBlockCount }

[@vzrivgavna5092]

Давай больше разборов задач! Очень интересно и полезно!

[@frontendscience]

👍

[@KananAliyev-e8e]

const trap = (heights) => { let result = 0; for(let i = 1; i < heights.length - 2; i++) { let maxLeft = Math.max(...heights.slice(0,i)) let maxRight = Math.max(...heights.slice(i + 1)) let minHeight = Math.min(maxLeft,maxRight) let quantity = minHeight - heights[i]; if(quantity > 0){ result += quantity } } return result }

[@eygenedanilkov9260]

const input1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; // 6 const input2 = [4, 2, 0, 3, 2, 5]; // 9 function trap(height) { let result = 0; for (let i = 1; i < height.length-1; i++) { const maxLeft = Math.max(...height.slice(0, i)) const maxRight = Math.max(...height.slice(i, height.length)) const water = Math.min(maxLeft, maxRight) result += water > height[i] ? water - height[i] : 0 } return result } console.log(trap(input1)) console.log(trap(input2))

[@baggikjeka4999]

Уверен что решение не очень (да и навело на меня решение другой задачи, про сушу), но на всякий случай прикреплю, интересно) const input1 = [0,1,0,2,1,0,1,3,2,1,2,1]; //6 const input2 = [4,2,0,3,2,5]; //9 function trap(height){ let rows = Math.max(...height); let cols = height.length; let counter = 0; if(rows === 0){ return 0; } let matrix = []; let positiveIndexesArray = []; for(let r = 0; r < rows;r++){ matrix.push([]); positiveIndexesArray.push([]); for(let c = 0; c < cols;c++){ if(height[c] > 0){ positiveIndexesArray[r].push(c); matrix[r][c] = 1; height[c] = height[c]-1; }else{ matrix[r][c] = 0 ; } } } for(let r = 0; r < matrix.length;r++){ for(let c = 0; c < cols;c++){ if(matrix[r][c] === 0 && c > Math.min(...positiveIndexesArray[r]) && c < Math.max(...positiveIndexesArray[r])){ counter ++; } } } return counter } console.log(trap(input1)); console.log(trap(input2));

[@antiga1000]

Я только до такого додумался function trap(height) { while(height[1] >= height[0]) { height.shift() } while(height[height.length - 2] >= height[height.length - 1]) { height.pop() } if(height[0] < height[height.length - 1]) height.reverse() let total = 0 let max = height.pop() while(height[height.length-1] < max) { let value = height.pop() total = total + (max - value) } if(height.length < 3) return total return total + trap(height) }

[@frontendscience]

Отлично вышло! Благодарю за решение

[@donybrorahmanov8068]

let input1 = [0,1,0,2,1,0,1,3,2,1,2,1] // 6 let input2 = [4,2,0,3,2,5] // 9 let input3 = [1,0,0,1,2,3,2,1,0] // 2 function getWaterAmount (arrayOfNumbers){ let height = Math.max(...arrayOfNumbers) let valuesPerRow = {} let result = 0 for (let row = 1; row= row){ valuesPerRow[row].push(1) }else{ valuesPerRow[row].push(0) } } } Object.values(valuesPerRow).forEach((arr)=>{ result += calculateBlocks(arr) }) console.log(result) } function calculateBlocks(arr){ let count = [] let startCounting = false let previousWasZero = false let result = 0 for (const elem of arr) { if(elem === 0 && startCounting){ count.push(1) previousWasZero=true } if(elem === 1){ startCounting = true } if(elem ===1 && startCounting && previousWasZero){ result = count.length } } return result } // getWaterAmount(input2)

[@АлександрГрайс]

Не могу понять откуда он эти цифры берёт. Дааа. Вторым способом намного легче и быстрее

[@frontendscience]

Потому что он знает, как рассчитывают сложность алгоритмов по BigO.) kzbin.info/www/bejne/fKaXc62Hg7Njh9U

[@АндрейНикифоров-ц8й]

1, 5 дня трудов let rain = [0, 1, 0, 3, 1, 0, 2, 0, 4] let resultate = {} console.log(edel(rain)) function edel(arr){ const max = Math.max(...arr) colb(max, arr) push (resultate) let res = counter(resultate) return res } function colb (max, arr) { let j=0 while (j !== max){ j++ resultate[j] = [] for (i=0; i

[@balambasik]

ссылки на jsfiddle режет я решил посчитать рядами let input = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; // 6 let input2 = [4, 2, 0, 3, 2, 5]; // 9 let map = []; /** * переводим в карту * * 0 | 0 1 0 0 0 * 1 | 1 1 0 0 1 * 2 | 1 1 0 1 1 * 3 | 1 1 1 1 1 * * для наглядности * - есть кирпич, . - нет кирпича * * 0 | . * . . . * 1 | * * . . * * 2 | * * . * * * 3 | * * * * * */ for (let i = 0; i < Math.max(...input); i++) { let tmp = []; for (let j = 0; j < input.length; j++) { let isFill = input[j] > i && input[j] !== 0 ? 1 : 0; tmp.push(isFill); } map[i] = tmp; } const calculateRow = (array) => { let out = array.join(""); // джойним массив (ряд) в строку out = out.replace(/0/g, " ").trim(); // заменяем нули на пробелы и обрезаем крайние пробелы (пустые места куда вода не наберется) return out.split(" ").length - 1; // осталось посчитать количество пробелов (пустых мест для воды) } // сумма let sum = map.reduce((acc, row) => { return acc + calculateRow(row); }, 0)

[@frontendscience]

Благодарю за решение! Необычный подход, такого еще не видел. ЗЫ: К сожалению на литкод он не прошел по времени: Time Limit Exceeded

[@andreytarasenko1914]

Вот моё решение: function trap(height) { const max = Math.max(...height); let result = 0; for (let i = 0; i < max; i++) { let container = { width: 0, // количество нулей leftBorder: 0, // позиция не нулевого элемента rightBorder: 0 // позиция не нулевого элемента } height.forEach((el, i, arr) => { if (!container.leftBorder) { if (el > 0) { container.leftBorder = 1; } } if (container.leftBorder) { if (el 0) { container.rightBorder = 1; result += container.width container = { width: 0, // количество нулей leftBorder: 0, // позиция не нулевого элемента rightBorder: 0 // позиция не нулевого элемента } container.leftBorder = 1 } } arr[i] = el - 1; // убираем нижний уровень (как в тетрисе) }) } return result; }

[@andreytarasenko1914]

И подскажите пожалуйста, правильно ли я посчитал сложность по скорости? У меня получилось O(n) = n * m + n; где m - максимальная высота столбца

[@frontendscience]

Благодарю за решение. Сложность вышла квадратичная O(n^2). Так как есть внешний цикл for который идет по всем элементам (в худшем случае максимум будет на самом последнем элементе), а потом внутри есть еще один цикл forEach. Поэтому это решение на литкод выдает: Time Limit Exceeded. Он хочет более оптимальный вариант по времени.

[@andreytarasenko1914]

@@frontendscience Благодарю за ответ.

[@user-bro]

320 / 320 test cases passed, but took too long. Пичаль.

[@user-bro]

Кое-что поправил и прошло. Runtime: 316 ms, faster than 5.05% of JavaScript online submissions for Trapping Rain Water. Memory Usage: 41.3 MB, less than 14.56% of JavaScript online submissions for Trapping Rain Water.

[@frontendscience]

@@user-bro прикольно! Присылай решение!

[@user-bro]

@@frontendscience var trap = function(height) { if (!Array.isArray(height) || height.length < 3) return 0 const secondHeight = (height.map(i => i).sort((a, b) => b-a))[1] const tempArray = Array(...height) let maxLeft = 0; for (let k = 1; k < height.length-1; k++){ maxLeft = maxLeft < height[k-1] ? height[k-1] : maxLeft; tempArray[k] = getHeight(k, height, secondHeight, maxLeft) } let a = height.reduce((prev, curent) => prev + curent) let b = tempArray.reduce((prev, curent) => prev + curent) return b-a; }; const getHeight = (index, array, heightLimit, maxLeft) => { let leftWallHeight = maxLeft; let rightWallHeight = 0; for (let r = index+1; r < array.length ; r++) { if (array[r] > rightWallHeight) rightWallHeight = array[r]; if (rightWallHeight >= heightLimit) break; } return Math.max(Math.min(leftWallHeight, rightWallHeight), array[index]) }

[@frontendscience]

Классно! Благодарю что поделился!

[@андрейгорничар]

уж лучше собирать дождевую воду чем собираться на пенсию в 20

[@Computermind11]

Куда исчезают мои комментарии? Модерация какая-то или что?

[@frontendscience]

Андрей, я вижу нотификации, но самих комментариев нет и не могу посмотреть до конца даже сообщения. Ютуб удаляет все комменты сл ссылками. Но я так понимаю, что вы просто решение уже высылаете. И его я тоже не вижу. Почему-то ютуб трет эти комменты. Может, увидел большую активность, чем всегда, не знаю… попробуйте выслать номер id пользователя на кодпене и id самого пена. Без полной ссылки

[@Computermind11]

@@frontendscience В прошлый раз мое решение в комментариях нормально прошло. Странно. Ладно, попробуем другим путем.

[@o-white-748dA]

Уфф, це була потна катка)) const getSumRain = (isArray) => { const input = [...isArray] const maxLeftArray = [...isArray]; const maxRightArray = [...isArray]; // Створюю пусті масиви для комфортної роботи в подальшому let sumFirstArray = [], maxLeft = [], sumSecondArray = [], maxRight = [], minLR = [], isValueRain = [] maxLeftArray.map((element, index) => { // сортуємо масив із ліва направо (maxLeft) sumFirstArray.push(maxLeftArray[index]) maxLeft.push(Math.max(...sumFirstArray)) return maxLeft }) maxLeft.pop() // Вирівнюємо лівий край скали першого масива maxLeft.unshift(0) // Вирівнюємо правий край скали першого масива maxRightArray.reverse().map((element, index) => { // Створюємо такий самий масив тільки з права наліво (maxRight) за допомогою reverse() sumSecondArray.push(maxRightArray[index]) maxRight.push(Math.max(...sumSecondArray)) return maxRight }) maxRight.unshift(0) // Вирівнюємо лівий край скали другого масива maxRight.reverse() // Розвертаємо, щоб коретно пройшли наступні операціїї for (let i = 0; i < maxLeft.length; i++) { // Рахуємо мінімум в який може набратися вода minLR.push(Math.min(maxLeft[i], maxRight[i])); } for (let i = 0; i < input.length; i++) { // Знаходимо заповнені водою клітинки if (minLR[i] >= input[i]) { const result = minLR[i] - input[i] isValueRain.push(result) } } return isValueRain.reduce((accumulator, total) => accumulator + total, 0); // Рахуємо клітинки з водою }