Скачать или смотреть # 07.10.2025 [1488. Avoid Flood in The City]

07.10.2025
[1488. Avoid Flood in The City](https://leetcode.com/problems/avoid-f...) medium
[blog post](https://leetcode.com/problems/avoid-f...)
[substack](https://open.substack.com/pub/dmitrii...)
[youtube](   • # 07.10.2025 [1488. Avoid Flood in The City]  )





#### Join me on Telegram

https://t.me/leetcode_daily_unstoppab...

#### Problem TLDR

Replace zeros with numbers to avoid duplicates #medium #binary_search #greedy

#### Intuition

```j
// 0 1 2 3 4 5 6 7 8 9 1011
// 1 2 0 0 3 4 0 0 3 4 1 2
// i - first filled, use zero at index 2

// 0 1 1 - corner case
// i -- can't use zero, because no zero before previous 1

// 0 0 0 0 0 0 2 1 2

// 0 0 0 0 0 0 2 0 0 1 2 1
// ^
// can i use any of these? - no

// 1 2 0 0 3 4 0 0 3 4 1 2
// * * i
// * * * * i i can use zeros between duplicates
// or, zero can be used for any element before it
//
// which one to choose? closest

// 1 2 0 0 2 1
// 1 2 0 2 0 1
// 1 0 2 0 2 1

// 1 2 0 1 0 2
// 1 0 2 0 1 2

// 0 1 1
// i zi = [0]
// i fi[1] = 1

// 0 1 2 3 4 5 6
// 1 0 2 3 0 1 2
// i . fi[1] = 0
// i . zi = [1]
// i . fi[2]=2
// i . fi[3]=3
// i . zi=[1,4]
// i prev=fi[1]=0, 4 vs 1, res[4]=1, ok so this breaks 2
// closest is not optimal
// "smallest after"

```

remember zero days
when seeing a duplicate, pick the first zero after the previous duplicate instance

#### Approach

use the BinarySearch or TreeSet .higher(x)

#### Complexity

Time complexity:
$$O(nlog(n))$$

Space complexity:
$$O(n)$$

#### Code
https://dmitrysamoylenko.com/2023/07/...