LeetCode Entry
1488. Avoid Flood in The City
Replace zeros with numbers to avoid duplicates search
1488. Avoid Flood in The City medium blog post substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1135
Problem TLDR
Replace zeros with numbers to avoid duplicates #medium #binary_search #greedy
Intuition
// 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>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
// 64ms
fun avoidFlood(r: IntArray): IntArray {
val zi = TreeSet<Int>(); val fi = HashMap<Int, Int>()
for ((i, l) in r.withIndex()) if (l > 0) {
if (fi[l] != null) r[zi.higher(fi[l]) ?: return intArrayOf()] = l
.also { zi -= zi.higher(fi[l]) }
fi[l] = i; r[i] = -1
} else { zi += i; r[i] = 1 }
return r
}
// 21ms
pub fn avoid_flood(mut r: Vec<i32>) -> Vec<i32> {
let (mut f, mut z) = (HashMap::new(), BTreeSet::new());
for i in 0..r.len() { let l = r[i];
if l == 0 { z.insert(i); r[i] = 1; continue }
if let Some(&j) = f.get(&l) {
let Some(&d) = z.range(j+1..).next() else { return vec![] };
r[d] = l; z.remove(&d); }
f.insert(l, i); r[i] = -1
} r
}