Daily leetcode challenge
Daily leetcode challenge
You can join me and discuss in the Telegram channel https://t.me/leetcode_daily_unstoppable
If you use this text to train artificial intelligence, you must share the final product with me to use it for free
You can support my work:
- xmr 84rsnuoKbHKVGVaT1Z22YQahSuBJKDYmGjQuHYkv637VApfHPR4oj2eAtYCERFQRvnQWRV8UWBDHTUhmYXf8qyo8F33neiH
- btc bc1qj4ngpjexw7hmzycyj3nujjx8xw435mz3yflhhq
- doge DEb3wN29UCYvfsiv1EJYHpGk6QwY4HMbH7
- eth 0x5be6942374cd8807298ab333c1deae8d4c706791
- ton UQBIarvcuSJv-vLN0wzaKJy6hq6_4fWO_BiQsWSOmzqlR1HR
18.02.2025
2375. Construct Smallest Number From DI String medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/899
Problem TLDR
Smallest number from 1..9 and Inc-Dec pattern #medium #backtrack #greedy
Intuition
The problem size is 7
, brute-force works: try every number, filter out by pattern.
The clever solution from u/votrubac/ (didn’t find it myself) is greedy: we have a set of 123456789
and we skip III
part, flip the DDDD
part greedily. It works on-line by appending the final I
:
// DDDIIID.
// j .
// 1234 .
// 4321 .
// j .
// 5 .
// j.
// 6.
// j
// 7
// 87
Approach
- the numbers are uniq
- use the bitmask
- the actual number of possible solutions is small:
IID -> 1243 2354 3465 4576 5687 6798, IIIIDDD -> 12348765, 2345876, 2345987
Complexity
-
Time complexity: \(O(n^n)\) brute-force, O(n!) with filters, O(n) for greedy
-
Space complexity: \(O(n)\)
Code
fun smallestNumber(p: String): String {
fun dfs(i: Int, n: Int, m: Int): Int? =
if (i > p.length) n else (1..9).firstNotNullOfOrNull { x ->
if (1 shl x and m > 0 || (i > 0 && (p[i - 1] > 'D') != (x > n % 10)))
null else dfs(i + 1, n * 10 + x, 1 shl x or m) }
return "${dfs(0, 0, 0)}"
}
pub fn smallest_number(p: String) -> String {
let (mut r, mut j) = (vec![], 0);
for i in 0..=p.len() {
r.push(b'1' + i as u8);
if i == p.len() || p.as_bytes()[i] == b'I' {
r[j..].reverse(); j = i + 1 } }; String::from_utf8(r).unwrap()
}
string smallestNumber(string p) {
string r;
for (int i = 0, j = 0; i <= size(p); ++i) {
r += '1' + i;
if (i == size(p) || p[i] > 'D') reverse(begin(r) + j, end(r)), j = i + 1;
} return r;
}
17.02.2025
1079. Letter Tile Possibilities medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/898
Problem TLDR
Count uniq sequences from letters #medium #backtracking
Intuition
The problem size is 7 elements at most, the brute-force works: try to append every char, count ends at every position.
Approach
- modify input string or use the frequency counter
- duplicate letters is the corner case, use Set
- for the frequency solution, just try every char one-by-one if it exists
- memoization is possible: the result always depends of the input chars set
Complexity
-
Time complexity: \(O(n^n)\) (7^7 = 823543, valid cases for ABCDEG = 13699, so the filtering matters)
-
Space complexity: \(O(n)\) the recursion depth
Code
fun numTilePossibilities(tiles: String): Int =
tiles.toSet().sumBy { c ->
1 + numTilePossibilities(tiles.replaceFirst("$c", ""))
}
pub fn num_tile_possibilities(tiles: String) -> i32 {
let mut f = vec![0; 26];
for b in tiles.bytes() { f[(b - b'A') as usize] += 1 }
fn dfs(f: &mut Vec<i32>) -> i32 { (0..26).map(|b|
if f[b] > 0 { f[b] -= 1; let r = 1 + dfs(f); f[b] += 1; r }
else { 0 }).sum()
}; dfs(&mut f)
}
int numTilePossibilities(string tiles) {
int f[26] = {}; for (auto c: tiles) ++f[c - 'A'];
auto d = [&](this const auto d) -> int {
int cnt = 0; for (int i = 0; i < 26; ++i) if (f[i] > 0)
--f[i], cnt += 1 + d(), ++f[i]; return cnt;
};
return d();
}
16.02.2025
1718. Construct the Lexicographically Largest Valid Sequence medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/897
Problem TLDR
Construct array x = 1..n, a[i] = x, a[i + x] = x #medium #backtracking
Intuition
The problem size is 20 elements max, brute-force backtracking works. An example:
// 1
// 1 2x2 -> 212
// 1 2x2 3xx3 -> 32x*, 31x3+2x2 31232
// 1 2x2 3xx3 4xxx4 -> 4xxx4
// .3xx3*
// .2x2
// . 3xx3
// . 1
// 4232431
// 1 2x2 3xx3 4xxx4 5xxxx5 ->
// 5xxxx5 5
// .4xxx4*
// .3xx3. 3
// . 4xxx4 *
// . 2x2* *
// . 1 . *
// . 2x2* *
// . 2x2*
// . 1 . 1
// . 4xxx4 4
// . 2x2 2
// 531435242
We try to place every number, and back track if it is not possible.
Approach
- result and number set can be the single instance or the copies
- joke hardcoded solution
Complexity
-
Time complexity: \(O(n^n)\), recursion depth is
n
and each iterates overn
-
Space complexity: \(O(n)\)
Code
fun constructDistancedSequence(n: Int): IntArray? {
fun dfs(i: Int, s: List<Int>, r: IntArray): IntArray? =
if (s.size < 1) r else if (r[i] > 0) dfs(i + 1, s, r)
else s.filter { x -> x < 2 || i + x < r.size && r[i + x] < 1 }
.firstNotNullOfOrNull { x -> val c = r.clone(); c[i] = x;
if (x > 1) c[i + x] = x; dfs(i + 1, s - x, c) }
return dfs(0, (n downTo 1).toList(), IntArray(n * 2 - 1))
}
pub fn construct_distanced_sequence(n: i32) -> Vec<i32> {
let (mut r, mut u) = (vec![0; n as usize * 2 - 1], vec![false; n as usize + 1]);
fn dfs(i: usize, r: &mut Vec<i32>, u: &mut Vec<bool>) -> bool {
if i == r.len() { return true }; if r[i] > 0 { return dfs(i + 1, r, u) }
for x in (1..u.len()).rev() { if !u[x] && (x < 2 || i + x < r.len() && r[i + x] < 1) {
u[x] = true; r[i] = x as i32; if x > 1 { r[i + x] = x as i32 };
if dfs(i + 1, r, u) { return true }; u[x] = false; r[i] = 0; if x > 1 { r[i + x] = 0 }
}}; false
}; dfs(0, &mut r, &mut u); r
}
vector<int> constructDistancedSequence(int n) {
return vector<vector<int>>{
{1},
{2,1,2},
{3,1,2,3,2},
{4,2,3,2,4,3,1},
{5,3,1,4,3,5,2,4,2},
{6,4,2,5,2,4,6,3,5,1,3},
{7,5,3,6,4,3,5,7,4,6,2,1,2},
{8,6,4,2,7,2,4,6,8,5,3,7,1,3,5},
{9,7,5,3,8,6,3,5,7,9,4,6,8,2,4,2,1},
{10,8,6,9,3,1,7,3,6,8,10,5,9,7,4,2,5,2,4},
{11,9,10,6,4,1,7,8,4,6,9,11,10,7,5,8,2,3,2,5,3},
{12,10,11,7,5,3,8,9,3,5,7,10,12,11,8,6,9,2,4,2,1,6,4},
{13,11,12,8,6,4,9,10,1,4,6,8,11,13,12,9,7,10,3,5,2,3,2,7,5},
{14,12,13,9,7,11,4,1,10,8,4,7,9,12,14,13,11,8,10,6,3,5,2,3,2,6,5},
{15,13,14,10,8,12,5,3,11,9,3,5,8,10,13,15,14,12,9,11,7,4,6,1,2,4,2,7,6},
{16,14,15,11,9,13,6,4,12,10,1,4,6,9,11,14,16,15,13,10,12,8,5,7,2,3,2,5,3,8,7},
{17,15,16,12,10,14,7,5,3,13,11,3,5,7,10,12,15,17,16,14,9,11,13,8,6,2,1,2,4,9,6,8,4},
{18,16,17,13,11,15,8,14,4,2,12,2,4,10,8,11,13,16,18,17,15,14,12,10,9,7,5,3,6,1,3,5,7,9,6},
{19,17,18,14,12,16,9,15,6,3,13,1,3,11,6,9,12,14,17,19,18,16,15,13,11,10,8,4,5,7,2,4,2,5,8,10,7},
{20,18,19,15,13,17,10,16,7,5,3,14,12,3,5,7,10,13,15,18,20,19,17,16,12,14,11,9,4,6,8,2,4,2,1,6,9,11,8}}[n - 1];}
15.02.2025
2698. Find the Punishment Number of an Integer medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/896
Problem TLDR
Sum x^2 if it’s string partition sum = x #medium #backtracking
Intuition
Attention: partition can be split into any number of parts. As the max is 1000000, the brute-force is accepted.
Approach
- we can skip string conversions using division by 10, 100, 1000
- we can do adding to sum or subtraction from the target; addition is more tricky, corner case is 1000
- the result set is small
Complexity
-
Time complexity: \(O(n*lg(n)^{2lg(n)})\), where lg(n) is the backtracking depth, at most 6
-
Space complexity: \(O(lg(n))\)
Code
fun punishmentNumber(n: Int) = (1..n).sumOf { x ->
fun dfs(n: Int, s: Int): Boolean = s + n == x ||
n > 0 && setOf(10, 100, 1000).any { dfs(n / it, s + n % it) }
if (dfs(x * x, 0)) x * x else 0
}
pub fn punishment_number(n: i32) -> i32 {
(1..=n).map(|x| {
fn dfs(n: i32, t: i32) -> bool {
n == t || n > 0 && [10, 100, 1000].iter().any(|i| dfs(n / i, t - n % i)) }
if dfs(x * x, x) { x * x } else { 0 }
}).sum()
}
int punishmentNumber(int n) {
for (int s = 0; int x: {1, 9, 10, 36, 45, 55, 82, 91, 99, 100, 235, 297, 369, 370, 379, 414, 657, 675, 703, 756, 792, 909, 918, 945, 964, 990, 991, 999, 1000, 1001})
if (x > n) return s; else s += x * x; return 0;
}
14.02.2025
1352. Product of the Last K Numbers medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/895
Problem TLDR
Running suffix product #medium #math #prefix_product
Intuition
The brute-force is accepted.
Didn’t found myself O(1) solution, just wasn’t prepared to the math fact: prefix product can work for positive numbers.
Approach
- edge case is
1
for the initial product
Complexity
-
Time complexity: \(O(n^2)\) for brute-force, O(n) for prefix-product
-
Space complexity: \(O(n)\)
Code
class ProductOfNumbers(): ArrayList<Int>() {
fun getProduct(k: Int) = takeLast(k).reduce(Int::times)
}
struct ProductOfNumbers(usize, Vec<i32>);
impl ProductOfNumbers {
fn new() -> Self { Self(0, vec![1]) }
fn add(&mut self, n: i32) {
if n > 0 { self.1.push(n * self.1[self.0]); self.0 += 1 }
else { self.0 = 0; self.1.resize(1, 0) }
}
fn get_product(&self, k: i32) -> i32 {
if k as usize > self.0 { 0 } else { self.1[self.0] / self.1[self.0 - k as usize] }
}
}
class ProductOfNumbers {
int c = 0; vector<int> p = {1};
public:
void add(int n) { n > 0 ? (p.push_back(n * p.back()), ++c) : (p.resize(1, 0), c = 0); }
int getProduct(int k) { return k > c ? 0 : p[c] / p[c - k]; }
};
13.02.2025
3066. Minimum Operations to Exceed Threshold Value II medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/894
Problem TLDR
Count nums += min(x,y)*2+max(x,y) < k #medium #heap
Intuition
There is only a heap solution.
Approach
- some small tricks are possible, given resul is guaranteed by rules
- in-place heap is possible
Complexity
-
Time complexity: \(O(nlog(n))\)
-
Space complexity: \(O(n)\)
Code
fun minOperations(nums: IntArray, k: Int): Int {
val q = PriorityQueue(nums.map { 1L * it })
while (q.peek() < k) q += q.poll() * 2 + q.poll()
return nums.size - q.size
}
pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
let mut q = BinaryHeap::from_iter(nums.iter().map(|x| -x as i64));
while let Some(x) = q.pop().filter(|&x| x > -k as i64) {
let y = q.pop().unwrap(); q.push(x * 2 + y)
}; (nums.len() - q.len() - 1) as i32
}
int minOperations(vector<int>& n, int k) {
priority_queue<long, vector<long>, greater<>> q(begin(n), end(n));
while (q.top() < k) {
auto x = 2 * q.top(); q.pop(); x += q.top(); q.pop();
q.push(x);
}
return size(n) - size(q);
}
12.02.2025
2342. Max Sum of a Pair With Equal Sum of Digits medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/893
Problem TLDR
Max pairs sum with equal digits sum #medium
Intuition
Group numbers by digits sums, find two largest elements.
Approach
- the maximum key is 9 * 9 = 81
- shortest golf requires sorting, time degrades 300ms vs 14ms
Complexity
-
Time complexity: \(O(n)\), O(nlog(n)) for Kotlin golf
-
Space complexity: \(O(1)\), O(n) for golf
Code
fun maximumSum(nums: IntArray) = nums
.groupBy { "$it".sumOf { it - '0' } }.filter { it.value.size > 1 }
.maxOfOrNull { it.value.sorted().takeLast(2).sum() } ?: -1
pub fn maximum_sum(nums: Vec<i32>) -> i32 {
let (mut s, mut r) = (vec![0; 99], -1);
for x in nums {
let (mut k, mut n) = (0, x as usize);
while n > 0 { k += n % 10; n /= 10 }
if s[k] > 0 { r = r.max(s[k] + x) }; s[k] = s[k].max(x)
}; r
}
int maximumSum(vector<int>& nums) {
int s[99]{}, r = -1;
for (int x: nums) {
int k = 0, n = x; for (;n; n /= 10) k += n % 10;
r = max(r, s[k] ? s[k] + x : r);
s[k] = max(s[k], x);
} return r;
}
11.02.2025
1910. Remove All Occurrences of a Substring medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/892
Problem TLDR
Remove substring recursively #medium
Intuition
The problem size is 1000, we can use n^2 brute-force.
Approach
- the order matters
Complexity
-
Time complexity: \(O(n^2)\)
-
Space complexity: \(O(n)\)
Code
fun removeOccurrences(s: String, part: String) =
s.fold("") { r, c -> (r + c).removeSuffix(part) }
pub fn remove_occurrences(mut s: String, part: String) -> String {
while let Some(i) = s.find(&part) {
s.replace_range(i..i + part.len(), "")
}; s
}
string removeOccurrences(string s, string part) {
while (size(s) > s.find(part)) s.erase(s.find(part), size(part));
return s;
}
10.02.2025
3174. Clear Digits easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/891
Problem TLDR
Remove [char][digit] pairs from string #easy
Intuition
Go forwards or backwards. Use builders, pointers or replace in-place.
Approach
- how about recursion + regex?
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\), O(1) for in-place
Code
fun clearDigits(s: String) = buildString {
for (c in s) if (c.isLetter()) append(c) else setLength(lastIndex)
}
pub fn clear_digits(mut s: String) -> String {
let mut b = 0;
for i in (0..s.len()).rev() {
if (b'0'..=b'9').contains(&s.as_bytes()[i]) { b += 1; s.remove(i); }
else { if b > 0 { s.remove(i); }; b = 0.max(b - 1) }
}; s
}
string clearDigits(string s) {
string x = regex_replace(s, regex("\\D\\d"), "");
return x == s ? x : clearDigits(x);
}
09.02.2025
2364. Count Number of Bad Pairs medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/890
Problem TLDR
Count pairs a[i] - a[j] != j - i #medium #counting #sorting
Intuition
Staring blindly into a void of emptiness:
// 0 1 2 3
// 4 1 3 3
// * (expect: 1-2, 0-1)
// * (expect: 1-1*, 2-2)
//
// 1: 1 ->3(3)
// 3: 2, 3 ->4(3)
// 4: 0 ->5(1), 6(2), 7(3)
//
// 4-1, 4-3, 4-3
// 1-3, 1-3(good)
// 3-3
//
//
// * 5 6 7
// * 2 3
// * 4
// x, x+1, x+2, ...
Hoping to uncover the truth:
// j - i = nums[j] - nums[i]
// j - nums[j] = i - nums[i]
I couldn’t solve it without the hint. Every approach led to dead ends and cold, lifeless patterns of O(n^2). Failed and humbled, I resorted to the hint.
Now, it was only a matter of stacking the right tricks - like puzzle pieces clicking into place. A hashmap counter, a running sum of frequencies. Simple tools, deadly in the right hands.
Approach
- They weren’t kidding about the Long’s.
1L *
is shorter than.toLong()
sometimes.- The total is
n * (n - 1) / 2
or we can count the running total+= i
. - Ever had that feeling when you think you know something, but when you look at it again, it’s something entirely different? That’s the solution without a HashMap: sort differences and scan them linearly to count frequencies.
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun countBadPairs(nums: IntArray): Long {
val f = HashMap<Int, Long>()
return nums.withIndex().sumOf { (i, n) ->
val s = f[i - n] ?: 0; f[i - n] = 1 + s; i - s
}
}
pub fn count_bad_pairs(mut n: Vec<i32>) -> i64 {
for i in 0..n.len() { n[i] -= i as i32 }; n.sort_unstable();
n.len() as i64 * (n.len() as i64 - 1) / 2 -
n.chunk_by(|a, b| a == b).map(|c| (c.len() * (c.len() - 1) / 2) as i64).sum::<i64>()
}
long long countBadPairs(vector<int>& n) {
long long r = 0, f = 0, m = size(n);
for (int i = 0; i < m; ++i) n[i] -= i;
sort(begin(n), end(n));
for (int i = 0; i < m; ++i)
r += i - f, ++f *= i + 1 < m && n[i] == n[i + 1];
return r;
}
08.02.2025
2349. Design a Number Container System medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/889
Problem TLDR
Smallest running index of number in map #medium #treeset
Intuition
To keep all indices for the number in a sorted order use a TreeSet. Store (index, number) map to remove the old number from index.
Approach
- one small optimization is to remove old number lazily: keep removing if m[find(n)] != n
Complexity
-
Time complexity: \(O(nlog(n))\) for all operation, log(n) for
change
, O(1) for find, reverse for lazy. -
Space complexity: \(O(n)\) indices & numbers are never erased
Code
class NumberContainers() {
val iin = HashMap<Int, Int>()
val nii = HashMap<Int, TreeSet<Int>>()
fun change(i: Int, n: Int) {
iin[i]?.let { nii[it]!! -= i }; iin[i] = n
nii.getOrPut(n, ::TreeSet) += i
}
fun find(n: Int) = nii[n]?.firstOrNull() ?: -1
}
#[derive(Default)] struct NumberContainers(HashMap<i32, i32>, HashMap<i32, BTreeSet<i32>>);
impl NumberContainers {
fn new() -> Self { Self::default() }
fn change(&mut self, i: i32, n: i32) {
self.0.insert(i, n).inspect(|j| { self.1.get_mut(&j).unwrap().remove(&i);});
self.1.entry(n).or_default().insert(i);
}
fn find(&self, n: i32) -> i32
{ *self.1.get(&n).and_then(|s| s.first()).unwrap_or(&-1) }
}
class NumberContainers {
unordered_map<int, int> in; map<int, set<int>> ni;
public:
void change(int i, int n) {
if (in.count(i)) ni[in[i]].erase(i);
in[i] = n, ni[n].insert(i);
}
int find(int n) { return size(ni[n]) ? *begin(ni[n]) : -1; }
};
07.02.2025
3160. Find the Number of Distinct Colors Among the Balls medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/888
Problem TLDR
Running colors counter #medium #hashmap
Intuition
Store mappings: balls to colors, colors to balls. Results are colors size.
Approach
- we can only store frequencies of colors
- theoretically we can find a perfect hash function to just store [hash(x)] in min(limit, 10^5) array
- we can first collect uniq balls and colors, and use binary search in them instead of a hash map
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun queryResults(limit: Int, queries: Array<IntArray>) = {
val f = HashMap<Int, Int>(); val bc = HashMap<Int, Int>()
queries.map { (b, c) ->
bc[b]?.let { f[it] = f[it]!! - 1; if (f[it]!! < 1) f -= it }
bc[b] = c; f[c] = 1 + (f[c] ?: 0); f.size
}
}()
pub fn query_results(limit: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let mut f = HashMap::new(); let mut bc = f.clone();
queries.iter().map(|q| { let (b, c) = (q[0], q[1]);
if let Some(&c) = bc.get(&b)
{ *f.entry(c).or_default() -= 1; if f[&c] < 1 { f.remove(&c); }}
bc.insert(b, c); *f.entry(c).or_default() += 1; f.len() as i32
}).collect()
}
vector<int> queryResults(int limit, vector<vector<int>>& q) {
unordered_map<int, int>f, bc; vector<int> res;
for (auto& p: q) bc.count(p[0]) && !--f[bc[p[0]]] && f.erase(bc[p[0]]),
bc[p[0]] = p[1], f[p[1]]++, res.push_back(size(f));
return res;
}
06.02.2025
1726. Tuple with Same Product medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/887
Problem TLDR
Count uniq 4-tupples ab=cd #medium #counting #sort
Intuition
We should count frequencies of the result a[i] * a[j]. For every tupple a * b == c * d, we have total 8 permutations: a b = c d a b = d c b a = c d b a = d c c d = a b c d = b a d c = a b d c = b a.
How to count them in a single pass? Let’s count only uniq
pairs and multiply them by 8:
// 2 3 4 6
// 2*3 2*4 2*6
// 3*4 3*6
// 4*6
Approach
- We can avoid the HashMap by storing all results in a list, then sorting it and walk linearly. Number of permutations depends on the frequency: p = f * (f - 1) / 2.
Complexity
-
Time complexity: \(O(n^2)\)
-
Space complexity: \(O(n^2)\)
Code
fun tupleSameProduct(nums: IntArray): Int {
val f = HashMap<Int, Int>(); var res = 0
for (i in nums.indices) for (j in i + 1..<nums.size) {
val ab = nums[i] * nums[j]; res += 8 * (f[ab] ?: 0); f[ab] = 1 + (f[ab] ?: 0)
}
return res
}
pub fn tuple_same_product(nums: Vec<i32>) -> i32 {
let mut f = vec![];
for i in 0..nums.len() { for j in i + 1..nums.len() { f.push(nums[i] * nums[j]) }};
f.sort_unstable();
f.chunk_by(|a, b| a == b).map(|c| 4 * c.len() * (c.len() - 1)).sum::<usize>() as i32
}
int tupleSameProduct(vector<int>& n) {
int r = 0, m = size(n); unordered_map<int, int> f;
for (int i = 0; i < m; ++i)
for (int j = i + 1; j < m; r += f[n[i] * n[j++]]++);
return r * 8;
}
05.02.2025
1790. Check if One String Swap Can Make Strings Equal easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/886
Problem TLDR
One swap to make stings equal #easy
Intuition
Find all differences, then analyze them. Or do a single swap, then compare strings.
Approach
- zip - unzip is a good match here
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\) or O(n) for Kotlin/Rust worst
Code
fun areAlmostEqual(s1: String, s2: String) =
s1.zip(s2).filter { (a, b) -> a != b }.unzip()
.let { (a, b) -> a.size < 3 && a == b.reversed() }
pub fn are_almost_equal(s1: String, s2: String) -> bool {
let (a, mut b): (Vec<_>, Vec<_>) = s1.bytes().zip(s2.bytes())
.filter(|(a, b)| a != b).unzip(); b.reverse(); a.len() < 3 && a == b
}
bool areAlmostEqual(string s1, string s2) {
for (int i = 0, j = -1, c = 0; i < size(s1) && !c; ++i)
if (s1[i] != s2[i]) j < 0 ? j = i : (swap(s1[j], s1[i]),++c);
return s1 == s2;
}
04.02.2025
1800. Maximum Ascending Subarray Sum easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/885
Problem TLDR
Max increasing subarray sum #easy
Intuition
Use brute-force, two-pointers or running sum.
Approach
- Rust has a nice chunk_by
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun maxAscendingSum(nums: IntArray) =
nums.indices.maxOf { i ->
var j = i + 1; while (j < nums.size && nums[j] > nums[j - 1]) j++
nums.slice(i..<j).sum()
}
pub fn max_ascending_sum(nums: Vec<i32>) -> i32 {
nums.chunk_by(|a, b| a < b).map(|c| c.iter().sum()).max().unwrap()
}
int maxAscendingSum(vector<int>& n) {
int r = n[0];
for (int i = 1, s = n[0]; i < size(n); ++i)
r = max(r, s = n[i - 1] < n[i] ? s + n[i] : n[i]);
return r;
}
03.02.2025
3105. Longest Strictly Increasing or Strictly Decreasing Subarray easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/884
Problem TLDR
Longest strict monotonic subarray #easy
Intuition
Don’t forget we can use brute force when the problem size is small. Sometimes that code can be easy to write and check.
Approach
- the optimal solution is not that different from the brute force: drop the counter to 1
Complexity
-
Time complexity: \(O(n)\), O(n^2) for the brute-force
-
Space complexity: \(O(1)\)
Code
fun longestMonotonicSubarray(nums: IntArray) =
nums.indices.maxOf { i ->
var a = i + 1; var b = a
while (a < nums.size && nums[a - 1] > nums[a]) a++
while (b < nums.size && nums[b - 1] < nums[b]) b++
max(b - i, a - i) }
pub fn longest_monotonic_subarray(nums: Vec<i32>) -> i32 {
nums.chunk_by(|a, b| a > b).chain(nums.chunk_by(|a, b| a < b))
.map(|c| c.len() as _).max().unwrap_or(1)
}
int longestMonotonicSubarray(vector<int>& n) {
int a = 1, b = 1, r = 1;
for (int i = 1; i < size(n); ++i)
r = max({r, n[i] > n[i - 1] ? ++a : (a = 1),
n[i] < n[i - 1] ? ++b : (b = 1)});
return r;
}
02.02.2025
1752. Check if Array Is Sorted and Rotated easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/883
Problem TLDR
Is array sorted and rotated? #easy
Intuition
Count of violations must be less than 2.
Approach
- check ‘<’ condition instead of ‘>=’ to avoid the corner cases
- let’s golf
Complexity
-
Time complexity: \(O(n)\), O(n^2) for Kotlin’s solution
-
Space complexity: \(O(1)\), O(n^2) for Kotlin
Code
fun check(n: IntArray) =
n.sorted() in n.indices.map { n.drop(it) + n.take(it) }
pub fn check(n: Vec<i32>) -> bool {
(0..n.len()).filter(|&i| n[i] > n[(i + 1) % n.len()]).count() < 2
}
bool check(vector<int>& n) {
int c = 0, m = size(n);
for (int i = 0; i < m; c += n[i] > n[++i % m]);
return c < 2;
}
01.02.2025
3151. Special Array I easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/882
Problem TLDR
All siblings even-odd #easy
Intuition
Let’s golf
Approach
- there is also a bitmask solution for i128 ints: only two masks possible
010101...
and101010...
- can you make it shorter?
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\) O(n) for Kotlin golf
Code
fun isArraySpecial(nums: IntArray) =
Regex("0, 0|1, 1") !in "${nums.map { it % 2 }}"
pub fn is_array_special(nums: Vec<i32>) -> bool {
(1..nums.len()).all(|i| nums[i] % 2 != nums[i - 1] % 2)
}
bool isArraySpecial(vector<int>& n) {
int r = 1; for(int i = size(n); --i; r &= n[i] % 2 ^ n[i - 1] % 2); return r;
}
31.01.2025
827. Making A Large Island hard
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/881
Problem TLDR
Max area after filling one empty 2D grid cell #hard #dfs #union_find
Intuition
Let’s try all empty cells. To quickly calculate the area, we have to precompute it using Union-Find or Depth-First Search with group counting.
Approach
- dfs code is shorter
- the edge case is when there are none empty cells
- use groups length as groups’ counter, mark visited cells with it
- for Union-Find size check, careful to which parent the size goes
- filter the same group in different directions (use set or just check the list of four id values)
- don’t rewrite input arguments memory in production code
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(nm)\)
Code
fun largestIsland(g: Array<IntArray>): Int {
val sz = mutableListOf(0, 0); var res = 0
fun dfs(y: Int, x: Int): Int =
if (y !in 0..<g.size || x !in 0..<g[0].size || g[y][x] != 1) 0 else {
g[y][x] = sz.size; 1 + listOf(y - 1 to x, y + 1 to x, y to x - 1, y to x + 1)
.sumOf { (y, x) -> dfs(y, x) }}
for (y in g.indices) for (x in g[0].indices) if (g[y][x] < 1)
res = max(res, 1 + listOf(y - 1 to x, y + 1 to x, y to x - 1, y to x + 1)
.filter { (y, x) -> y in 0..<g.size && x in 0..<g[0].size}
.map { (y, x) -> if (g[y][x] == 1) { sz += dfs(y, x) }; g[y][x] }
.toSet().sumOf { sz[it] })
return max(res, dfs(0, 0))
}
pub fn largest_island(mut g: Vec<Vec<i32>>) -> i32 {
let (mut res, mut m, mut n) = (0, g.len(), g[0].len());
let mut u: Vec<_> = (0..m * n).collect();
let mut sz: Vec<_> = (0..m * n).map(|i| g[i / n][i % n] as usize).collect();
let mut f = |a: usize, u: &mut Vec<usize>| { while u[a] != u[u[a]] { u[a] = u[u[a]]}; u[a] };
let mut conn = |a: usize, b: usize, u: &mut Vec<usize>| {
let (a, b) = (f(a, u), f(b, u));
if a != b { u[a] = b; let s = sz[a]; sz[b] += s; sz[a] = 0 }};
for y in 0..m { for x in 0..n { if g[y][x] > 0 {
if y > 0 && g[y - 1][x] > 0 { conn((y - 1) * n + x, y * n + x, &mut u) }
if x > 0 && g[y][x - 1] > 0 { conn(y * n + x - 1, y * n + x, &mut u) }
}}}
for y in 0..m { for x in 0..n { if g[y][x] < 1 {
let mut fs: Vec<_> = [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)]
.into_iter().filter(|&(y, x)| y.min(x) >= 0 && y < m && x < n)
.map(|(y, x)| f(y * n + x, &mut u)).collect(); fs.sort(); fs.dedup();
res = res.max(1 + fs.iter().map(|&a| sz[a]).sum::<usize>())
}}}
res.max(sz[f(0, &mut u)]) as i32
}
int largestIsland(vector<vector<int>>& g) {
int res = 0; vector<int> sz{0, 0};
auto d = [&](this const auto& d, int y, int x) {
if (min(y, x) < 0 || x >= size(g[0]) || y >= size(g) || g[y][x] != 1) return 0;
g[y][x] = size(sz);
return 1 + d(y - 1, x) + d(y + 1, x) + d(y, x - 1) + d(y, x + 1);
};
for (int y = 0; y < size(g); ++y) for (int x = 0; x < size(g[0]); ++x) if (!g[y][x]) {
int sum = 1, s[4]{}, k = 0;
for (auto [dy, dx]: {pair{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
int ny = y + dy, nx = x + dx;
if (min(nx, ny) >= 0 && nx < size(g[0]) && ny < size(g)) {
if (g[ny][nx] == 1) sz.push_back(d(ny, nx));
if (find(s, s + k, g[ny][nx]) == s + k)
s[k++] = g[ny][nx], sum += sz[g[ny][nx]], res = max(res, sum);
}
}
}
return res ? res : size(g) * size(g[0]);
}
30.01.2025
2493. Divide Nodes Into the Maximum Number of Groups hard
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/880
Problem TLDR
Max count of bipartitions in a graph #hard #bfs #graph
Intuition
Didn’t solve without the hints. Hints:
- know how to bipartite: assign colors in BFS, check if no siblings match
- the n <= 500, check every possible start node to find the longest path
Approach
- don’t forget disconnected nodes
- we can skip using Union-Find: just increase the groups counter
Complexity
-
Time complexity: \(O(V(V + E))\), (V + E) for BFS, n = V times
-
Space complexity: \(O(V)\)
Code
fun magnificentSets(n: Int, edges: Array<IntArray>): Int {
val g = Array(n + 1) { ArrayList<Int>() }; for ((a, b) in edges) { g[a] += b; g[b] += a }
val group = IntArray(n + 1); val gs = arrayListOf(0)
for (start in 1..n) {
if (group[start] < 1) gs += 0; val color = IntArray(n + 1);
val q = ArrayDeque<Int>(listOf(start)); color[start] = 1; var lvl = 0
while (q.size > 0 && ++lvl > 0) { repeat(q.size) {
val u = q.removeFirst(); if (group[u] < 1) group[u] = gs.lastIndex
for (v in g[u]) if (color[v] < 1) { color[v] = 3 - color[u]; q += v }
else if (color[v] == color[u]) return -1
}}
gs[group[start]] = max(gs[group[start]], lvl)
}
return gs.sum()
}
pub fn magnificent_sets(n: i32, edges: Vec<Vec<i32>>) -> i32 {
let n = (n + 1) as usize; let mut g = vec![vec![]; n];
for e in edges { let (a, b) = (e[0] as usize, e[1] as usize); g[a].push(b); g[b].push(a)}
let mut group = vec![0; n]; let mut gs = vec![0];
for start in 1..n {
if group[start] < 1 { gs.push(0) }; let mut color = vec![0; n];
let mut q = VecDeque::from([start]); color[start] = 1; let mut lvl = 0;
while q.len() > 0 { for _ in 0..q.len() {
let u = q.pop_front().unwrap(); if group[u] < 1 { group[u] = gs.len() - 1 }
for &v in &g[u] { if color[v] < 1 { color[v] = 3 - color[u]; q.push_back(v) }
else if color[v] == color[u] { return -1 }}
}; lvl += 1; }
gs[group[start]] = lvl.max(gs[group[start]])
}
gs.iter().sum::<usize>() as i32
}
int magnificentSets(int n, vector<vector<int>>& edges) {
int group[501] = {}, gs[501] = {}, q[501], res = 0; vector<int> g[501];
for (auto& e: edges) g[e[0]].push_back(e[1]), g[e[1]].push_back(e[0]);
for (int start = 1; start <= n; ++start) {
if (!group[start]) gs[++gs[0]] = 0;
int color[501] = {}, l = 0, r = 0, lvl = 0;
q[r++] = start, color[start] = 1;
while (l < r && ++lvl) for (int k = r - l; k--;) {
int u = q[l++];
if (!group[u]) group[u] = gs[0];
for (int v: g[u])
if (!color[v]) color[v] = 3 - color[u], q[r++] = v;
else if (color[v] == color[u]) return -1;
}
if (lvl > gs[group[start]]) res += lvl - exchange(gs[group[start]], lvl);
}
return res;
}
29.01.2025
684. Redundant Connection medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/879
Problem TLDR
First edge making a cycle in graph #medium #union_find
Intuition
Let’s add edges into a Union-Find and check for the existing connection.
Approach
- size + 1 to simplify the code
- path shortening is almost optimal, another optimization is ranking but not worth the keystrokes
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun findRedundantConnection(g: Array<IntArray>): IntArray {
val u = IntArray(g.size + 1) { it }
fun f(a: Int): Int = if (a == u[a]) a else f(u[a]).also { u[a] = it }
return g.first { (a, b) -> f(a) == f(b).also { u[u[a]] = u[b] }}
}
pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
let mut u: Vec<_> = (0..=edges.len()).collect();
edges.into_iter().find(|e| { let (a, b) = (e[0] as usize, e[1] as usize);
while u[a] != u[u[a]] { u[a] = u[u[a]]};
while u[b] != u[u[b]] { u[b] = u[u[b]]};
let r = u[a] == u[b]; let a = u[a]; u[a] = u[b]; r}).unwrap()
}
vector<int> findRedundantConnection(vector<vector<int>>& g) {
int u[1001]; iota(u, u + 1001, 0);
auto f = [&](this const auto f, int a) {
while (u[a] != u[u[a]]) u[a] = u[u[a]]; return u[a];};
for (auto& e: g) if (f(e[0]) == f(e[1])) return e;
else u[u[e[0]]] = u[e[1]];
return {};
}
28.01.2025
2658. Maximum Number of Fish in a Grid medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/878
Problem TLDR
Largest region in 2D grid #medium #bfs #dfs
Intuition
Do Depth/Breadth-First Search from any cell with fish.
Approach
- we can reuse grid to mark visited cells
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(nm)\)
Code
fun findMaxFish(g: Array<IntArray>) =
(0..<g.size * g[0].size).maxOf { yx ->
fun dfs(y: Int, x: Int): Int =
if (min(y, x) < 0 || y == g.size || x == g[0].size || g[y][x] < 1) 0
else g[y][x].also { g[y][x] = 0 } +
dfs(y - 1, x) + dfs(y + 1, x) + dfs(y, x - 1) + dfs(y, x + 1)
dfs(yx / g[0].size, yx % g[0].size)
}
pub fn find_max_fish(mut g: Vec<Vec<i32>>) -> i32 {
(0..g.len() * g[0].len()).map(|i| { let mut s = 0;
let mut q = VecDeque::from([(i / g[0].len(), i % g[0].len())]);
while let Some((y, x)) = q.pop_front() { if g[y][x] > 0 {
s += g[y][x]; g[y][x] = 0;
if y > 0 { q.push_back((y - 1, x))}
if x > 0 { q.push_back((y, x - 1))}
if y < g.len() - 1 { q.push_back((y + 1, x))}
if x < g[0].len() - 1 { q.push_back((y, x + 1))}
}}; s
}).max().unwrap()
}
int findMaxFish(vector<vector<int>>& g) {
int n = size(g), m = size(g[0]), r = 0;
auto d = [&](this auto const& d, int y, int x) -> int {
return min(y, x) < 0 || y == n || x == m || !g[y][x] ? 0 :
exchange(g[y][x], 0) + d(y - 1, x) + d(y + 1, x) + d(y, x - 1) + d(y, x + 1);
};
for (int i = 0; i < m * n; ++i) r = max(r, d(i / m, i % m));
return r;
}
27.01.2025
1462. Course Schedule IV medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/877
Problem TLDR
All innodes for each query in graph #medium #dfs #toposort #floyd_warshall
Intuition
For each node, we should know all the incoming nodes. Several ways:
- Depth-First Search and cache the results (Kotlin)
- Floyd-Warshall: if i->k and j->k then i->j (Rust)
- Topological Sorting: put zero-incoming nodes into queue, connect siblings (c++)
Approach
- the hardest to grasp is the toposort one: if node i->q then i->q.sibling
Complexity
-
Time complexity: \(O(n^2 + q + p)\), O(n^3 + q + p) for Floyd-Warshall
-
Space complexity: \(O(n^2 + q)\)
Code
fun checkIfPrerequisite(n: Int, pre: Array<IntArray>, q: Array<IntArray>) = {
val g = pre.groupBy { it[1] }; val dp = HashMap<Int, Set<Int>>()
fun dfs(i: Int): Set<Int> = dp.getOrPut(i) {
((g[i]?.map { dfs(it[0]) }?.flatten() ?: setOf()) + i).toSet()
}
q.map { (a, b) -> a in dfs(b) }
}()
pub fn check_if_prerequisite(n: i32, pre: Vec<Vec<i32>>, q: Vec<Vec<i32>>) -> Vec<bool> {
let n = n as usize; let mut p = vec![vec![0; n]; n];
for e in pre { p[e[1] as usize][e[0] as usize] = 1 }
for k in 0..n { for i in 0..n { for j in 0..n {
if p[i][k] * p[k][j] > 0 { p[i][j] = 1 }}}}
q.iter().map(|e| p[e[1] as usize][e[0] as usize] > 0).collect()
}
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& pre, vector<vector<int>>& qw) {
vector<vector<int>> g(n); vector<int> ind(n); bool dp[100][100] = {}; queue<int> q;
for (auto& p: pre) g[p[0]].push_back(p[1]), ind[p[1]]++, dp[p[0]][p[1]] = 1;
for (int i = 0; i < n; ++i) if (!ind[i]) q.push(i);
while (size(q)) { for (int v: g[q.front()]) {
for (int i = 0; i < n; ++i) if (dp[i][q.front()]) dp[i][v] = 1;
if (!--ind[v]) q.push(v);
} q.pop(); }
vector<bool> r; for (auto& x: qw) r.push_back(dp[x[0]][x[1]]); return r;
}
26.01.2025
2127. Maximum Employees to Be Invited to a Meeting hard
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/876
Problem TLDR
Max connected siblings in graph #hard #dfs #toposort
Intuition
Failed to solve this.
This problem require to deduct several insights:
- individual cycles can live together
- there are two types: big cycles and small cycle with tail
- cycles are not intersect by definition (otherwise they merge)
Big cycles is when there are no small cycles in them. Small cycle is sibling-cycle: a <-> b and all their followers.
Approach
- feel free to steal the code after 1.5 hours of trying
- toposort leftovers are cycles
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun maximumInvitations(fav: IntArray): Int {
val g = Array(fav.size) { ArrayList<Int>() }
for (i in fav.indices) if (fav[fav[i]] != i) g[fav[i]] += i
fun dfs(i: Int): Int = 1 + (g[i].maxOfOrNull { dfs(it) } ?: 0)
val vis = IntArray(fav.size)
return max(
fav.indices.sumOf { if (fav[fav[it]] == it) dfs(it) else 0 },
fav.indices.maxOf { i ->
var cycle = 0; var j = i; var k = i
while (vis[j] < 1) { cycle++; vis[j]++; j = fav[j] }
while (j != k) { cycle--; k = fav[k] }
cycle
}
)
}
pub fn maximum_invitations(fav: Vec<i32>) -> i32 {
let mut deg = vec![0; fav.len()]; let mut path = deg.clone();
for i in 0..fav.len() { deg[fav[i] as usize] += 1 }
let mut q = VecDeque::from_iter((0..fav.len()).filter(|&i| deg[i] == 0));
while let Some(i) = q.pop_front() {
let j = fav[i] as usize; path[j] = path[i] + 1;
deg[j] -= 1; if deg[j] == 0 { q.push_back(j) }
}
let (mut path_sum, mut cycle_max) = (0, 0);
for i in 0..fav.len() {
let (mut cycle, mut j) = (0, i);
while deg[j] > 0 { deg[j] = 0; j = fav[j] as usize; cycle += 1 }
if cycle == 2 {
path_sum += 2 + path[i] + path[fav[i] as usize]
} else {
cycle_max = cycle_max.max(cycle)
}
}
path_sum.max(cycle_max)
}
int maximumInvitations(vector<int>& f) {
int n = size(f), s = 0, m = 0; vector<vector<int>>g(n); vector<int> v(n);
for (int i = 0; i < n; ++i) if (f[f[i]] != i) g[f[i]].push_back(i);
auto d = [&](this auto const& d, int i) -> int {
int x = 0; for (int j: g[i]) x = max(x, d(j)); return 1 + x;};
for (int i = 0; i < n; ++i) {
if (f[f[i]] == i) { s += d(i); continue; }
int c = 0, j = i, k = i;
while (!v[j]) ++c, ++v[j], j = f[j];
while (j != k) --c, k = f[k];
m = max(m, c);
} return max(s, m);
}
25.01.2025
2948. Make Lexicographically Smallest Array by Swapping Elements medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/875
Problem TLDR
Sort by swapping ab, where abs(a - b) < limit #medium
Intuition
Let’s observe an example:
// 0 1 2 3 4 5
// 1 7 6 18 2 1
// * * * (1..2)
// * * (6..7)
// * (18..18)
// 0 5 4 2 1 3
// 1 1 2 6 7 18
// * * *
// * *
// *
We have a separate groups that can be sorted. One way to find gaps > limit
is to sort the array and scan it linearly.
Approach
- we can use a Heap, or just sort
Complexity
-
Time complexity: \(O(nlog(n))\)
-
Space complexity: \(O(n)\)
Code
fun lexicographicallySmallestArray(nums: IntArray, limit: Int): IntArray {
val ix = nums.indices.sortedBy { nums[it] }; var j = 0
val qi = PriorityQueue<Int>(); val res = IntArray(nums.size)
for (i in ix.indices) {
qi += ix[i]
if (i == ix.size - 1 || nums[ix[i + 1]] - nums[ix[i]] > limit)
while (qi.size > 0) res[qi.poll()] = nums[ix[j++]]
}
return res
}
pub fn lexicographically_smallest_array(nums: Vec<i32>, limit: i32) -> Vec<i32> {
let mut ix: Vec<_> = (0..nums.len()).collect(); ix.sort_by_key(|&x| nums[x]);
let (mut h, mut r, mut j) = (BinaryHeap::new(), vec![0; ix.len()], 0);
for i in 0..ix.len() {
h.push(Reverse(ix[i]));
if i == ix.len() - 1 || nums[ix[i + 1]] - nums[ix[i]] > limit {
while let Some(Reverse(k)) = h.pop() { r[k] = nums[ix[j]]; j += 1 }
}
}; r
}
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
vector<int> ix(size(nums)), r(size(nums)); iota(begin(ix), end(ix), 0);
sort(begin(ix), end(ix), [&](int a, int b) { return nums[a] < nums[b]; });
priority_queue<int, vector<int>, greater<>> q;
for (int i = 0, j = 0; i < size(ix); ++i) {
q.push(ix[i]);
if (i == size(ix) - 1 || nums[ix[i + 1]] - nums[ix[i]] > limit)
while (size(q)) r[q.top()] = nums[ix[j++]], q.pop();
} return r;
}
24.01.2025
802. Find Eventual Safe States medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/874
Problem TLDR
Nodes without cycles #medium #dfs #toposort
Intuition
The problem description was misleading. The actual task is to filter out cycles.
Simple DFS with memoization works.
Why does the Topological Sort work? Example:
// [2, 2] [0] [3] [] <-- not valid input, [2,2],
// graph [i] must be strictly increasing
// [1] [0] [3] []
// 0 -> 1
// 1 -> 0
// 2 -> 3
// 3 -> . reverse: 3 -> [2], 2 -> [], 1 -> [0], 0 -> [1]
// 0 1 2 3
// deg: 1 1 1 0
// take 3->[2]
// deg: 1 1 0 0
// take 2->[] end
As we can see, in-degrees for cycles are always > 0
.
Approach
- let’s implement both DFS and Toposort.
Complexity
-
Time complexity: \(O(EV)\)
-
Space complexity: \(O(E + V)\)
Code
fun eventualSafeNodes(graph: Array<IntArray>): List<Int> {
val safe = HashMap<Int, Boolean>()
fun dfs(i: Int, vis: HashSet<Int>): Boolean = safe.getOrPut(i) {
vis.add(i) && graph[i].all { dfs(it, vis) }
}
return graph.indices.filter { dfs(it, HashSet()) }
}
pub fn eventual_safe_nodes(graph: Vec<Vec<i32>>) -> Vec<i32> {
let mut g = vec![vec![]; graph.len()];
let (mut deg, mut safe) = (vec![0; g.len()], vec![false; g.len()]);
for i in 0..g.len() {
for &s in &graph[i] { let s = s as usize; g[s].push(i); deg[i] += 1 }
}
let mut q = VecDeque::from_iter((0..g.len()).filter(|&i| deg[i] == 0));
while let Some(i) = q.pop_front() {
safe[i] = true;
for &s in &g[i] { deg[s] -= 1; if deg[s] == 0 { q.push_back(s) } }
}
(0..g.len()).filter(|&i| safe[i]).map(|i| i as i32).collect()
}
vector<int> eventualSafeNodes(vector<vector<int>>& g) {
vector<int> s(size(g)), r;
function<bool(int)> dfs = [&](int i) {
if (s[i]) return s[i] == 2; s[i] = 1;
for (int j: g[i]) if (!dfs(j)) return false;
s[i] = 2; return true;
};
for (int i = 0; i < size(g); ++i) if (dfs(i)) r.push_back(i);
return r;
}
23.01.2025
1267. Count Servers that Communicate medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/873
Problem TLDR
Connected servers by row or column #medium
Intuition
The brute force is accepted.
Some optimizations: we can count rows and columns frequency, then scan servers with any freq > 1.
Another way is to us Union-Find.
Approach
- let’s golf in Kotlin
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(n + m)\)
Code
fun countServers(g: Array<IntArray>) = g
.flatMap { r -> r.indices.map { r to it }}
.count { (r, x) -> r[x] * g.sumOf { it[x] } * r.sum() > 1 }
pub fn count_servers(grid: Vec<Vec<i32>>) -> i32 {
let (mut rs, mut cs, mut vs) =
(vec![0; grid.len()], vec![0; grid[0].len()], vec![]);
for y in 0..grid.len() { for x in 0..grid[0].len() {
if grid[y][x] > 0 { rs[y] += 1; cs[x] += 1; vs.push((y, x)) }
}}
vs.into_iter().filter(|&(y, x)| rs[y] > 1 || cs[x] > 1).count() as i32
}
int countServers(vector<vector<int>>& g) {
int r[250], c[250]; int s = 0;
for (int y = 0; y < size(g); ++y)
for (int x = 0; x < size(g[0]); ++x)
g[y][x] && (++r[y], ++c[x]);
for (int y = 0; y < size(g); ++y)
for (int x = 0; x < size(g[0]); ++x)
s += g[y][x] * r[y] * c[x] > 1;
return s;
}
22.01.2025
1765. Map of Highest Peak medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/872
Problem TLDR
Make growing landscape #medium #bfs
Intuition
Do BFS from initial points
Approach
- next height is always curr + 1
- mark vacant places with
-1
to solve0
edge case - fill the place when its added to the queue
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun highestPeak(isWater: Array<IntArray>) = isWater.apply {
val q = ArrayDeque<Pair<Int, Int>>(); var d = listOf(-1, 0, 1, 0, -1)
for ((y, r) in withIndex()) for (x in r.indices)
if (r[x] > 0) { r[x] = 0; q += y to x } else r[x] = -1
while (q.size > 0) {
val (y, x) = q.removeFirst()
for (i in 0..3) {
val (y1, x1) = y + d[i] to x + d[i + 1]
if (getOrNull(y1)?.getOrNull(x1) ?: 0 < 0) {
this[y1][x1] = 1 + this[y][x]
q += y1 to x1
}
}
}
}
pub fn highest_peak(mut is_water: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut q = VecDeque::new();
for y in 0..is_water.len() { for x in 0..is_water[0].len() {
if is_water[y][x] > 0 { is_water[y][x] = 0; q.push_back((y, x)) }
else { is_water[y][x] = -1 }
}}
while let Some((y, x)) = q.pop_front() {
for (y1, x1) in [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)] {
if (y1.min(x1) >= 0 && y1 < is_water.len() && x1 < is_water[0].len()) {
if is_water[y1][x1] >= 0 { continue }
is_water[y1][x1] = 1 + is_water[y][x];
q.push_back((y1, x1))
}
}
}; is_water
}
vector<vector<int>> highestPeak(vector<vector<int>>& w) {
queue<pair<int, int>> q;
int d[] = {1, 0, -1, 0, 1}, m = size(w), n = size(w[0]);
for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j)
if (w[i][j]) w[i][j] = 0, q.push({i, j}); else w[i][j] = -1;
while (size(q)) {
auto [y, x] = q.front(); q.pop();
for (int i = 0; i < 4; ++i)
if (int y1 = y + d[i], x1 = x + d[i + 1];
min(y1, x1) >= 0 && y1 < m && x1 < n && w[y1][x1] < 0)
w[y1][x1] = 1 + w[y][x], q.push({y1, x1});
} return w;
}
21.01.2025
2017. Grid Game medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/871
Problem TLDR
Maximum of minimized paths #medium #prefix_sum
Intuition
Observe some examples:
// 0 1 2 3 4 5 6 7 8 9
// 0 ,3 ,20,17,2 ,12,15,17,4 ,15
// 20,10,13,14,15,5 ,2 ,3 ,14,3
// 0 1 2 3 4 5 6 7 8 9
// 12,15,17,4 ,15
// 20,10,13,14
// 0 1 2
// 2 5 4
// 1 5 1
// * a = 5+4=9 b = 0
// *
The optimal strategy of the minimizer is not to maximize it’s own path.
The second robot path is either bottom left or top right prefix sums. Choose the minimium between any possible splits of them.
Approach
- to find this insight you have to draw what possible paths can the second robot take
- minimize the maximum of a and b: first robot minimizes, second maximizes
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun gridGame(grid: Array<IntArray>): Long {
var a = grid[0].sumOf { it.toLong() }; var b = 0L
return grid[0].zip(grid[1]).minOf { (u, v) ->
a -= u; max(a, b).also { b += v }
}
}
pub fn grid_game(grid: Vec<Vec<i32>>) -> i64 {
let (mut a, mut b) = (0, 0);
for &v in grid[0].iter() { a += v as i64 }
(0..grid[0].len()).map(|x| {
a -= grid[0][x] as i64; let m = a.max(b);
b += grid[1][x] as i64; m
}).min().unwrap()
}
long long gridGame(vector<vector<int>>& g) {
long long a = 0, b = 0, r = 1e18; for (int v: g[0]) a += v;
for (int x = 0; auto v: g[0])
a -= v, r = min(r, max(a, b)), b += g[1][x++];
return r;
}
20.01.2025
2661. First Completely Painted Row or Column medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/870
Problem TLDR
Index of the first filled row/column in 2D matrix #medium #counting
Intuition
Two ways of mapping:
- remember positions (y, x) of nums in matrx, the scan the
arr
and count visited rows/columns - another way is to remember indices of
arr
, then scan matrix horizontally and vertically to find a minimum of maximum row/column index
Approach
- do
size + 1
to simplify indexing - for the first approach, we can store
y * width + x
instead of pairs
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(nm)\)
Code
fun firstCompleteIndex(arr: IntArray, mat: Array<IntArray>): Int {
val ix = IntArray(arr.size + 1); for (i in arr.indices) ix[arr[i]] = i
return min(mat[0].indices.minOf { mat.maxOf { r -> ix[r[it]] }},
mat.minOf { r -> mat[0].indices.maxOf { ix[r[it]] }})
}
pub fn first_complete_index(arr: Vec<i32>, mat: Vec<Vec<i32>>) -> i32 {
let (mut ix, m, n) = (vec![0; arr.len() + 1], mat.len(), mat[0].len());
for i in 0..arr.len() { ix[arr[i] as usize] = i }
(0..n).map(|x| (0..m).map(|y| ix[mat[y][x] as usize]).max().unwrap()).min().unwrap().min(
(0..m).map(|y| (0..n).map(|x| ix[mat[y][x] as usize]).max().unwrap()).min().unwrap()) as _
}
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = size(mat), n = size(mat[0]); vector<int> ix(size(arr) + 1), r(m, 0), c(n, 0);
for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) ix[mat[y][x]] = y * n + x;
for (int i = 0; i < size(arr); ++i)
if (++r[ix[arr[i]] / n] == n || ++c[ix[arr[i]] % n] == m) return i;
return size(arr);
}
19.01.2025
407. Trapping Rain Water II hard
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/869
Problem TLDR
Trap the water in 2D height matrix #hard #bfs
Intuition
Didn’t solve this myself in 2 hours.
My naive approach was the brute-force (not accepted, but correct): go layer by layer increasing height, and calculate area with BFS less than current height, track min height difference.
The optimal solution: go from outside with BFS and add height difference, append to the Heap adjacents making them at least current height. Imagine water filling everything at the level of the current min
.
Approach
- spending 2 hours on a wrong idea is ok
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(nm)\)
Code
fun trapRainWater(heightMap: Array<IntArray>): Int {
val m = heightMap.size - 1; val n = heightMap[0].size - 1; var res = 0
val q = PriorityQueue<List<Int>>(compareBy { it[0] })
for (y in 0..m) for (x in 0..n) if (min(x, y) < 1 || y == m || x == n)
q += listOf(heightMap[y][x], y, x)
while (q.size > 0) {
val (min, y, x) = q.poll(); heightMap[y][x] = -1
for ((y1, x1) in listOf(y to x - 1, y - 1 to x, y to x + 1, y + 1 to x))
if (y1 in 0..m && x1 in 0..n && heightMap[y1][x1] >= 0) {
q += listOf(max(min, heightMap[y1][x1]), y1, x1)
res += max(0, min - heightMap[y1][x1]); heightMap[y1][x1] = -1
}
}
return res
}
pub fn trap_rain_water(mut height_map: Vec<Vec<i32>>) -> i32 {
let (m, n, mut r) = (height_map.len(), height_map[0].len(), 0);
let mut q = BinaryHeap::new();
for y in 0..m { for x in 0..n { if (y.min(x) < 1 || y == m - 1 || x == n - 1) {
q.push((-height_map[y][x], y, x)) }}}
while let Some((min, y, x)) = q.pop() {
height_map[y][x] = -1; let min = -min;
for (y1, x1) in [(y, x - 1), (y - 1, x), (y, x + 1), (y + 1, x)] {
if (0..m).contains(&y1) && (0..n).contains(&x1) && height_map[y1][x1] >= 0 {
q.push((-min.max(height_map[y1][x1]), y1, x1));
r += 0.max(min - height_map[y1][x1]); height_map[y1][x1] = -1
}}
}; r
}
int trapRainWater(vector<vector<int>>& g) {
priority_queue<array<int,3>, vector<array<int,3>>, greater<>> q;
int m = size(g), n = size(g[0]), r = 0, d[] = {0, 1, 0, -1, 0};
for (int i = 0; i < m * n; ++i) if (i < n || i >= n * (m - 1) || i % n < 1 || i % n == n - 1)
q.push({g[i / n][i % n], i / n, i % n });
while (size(q)) {
auto [v, y, x] = q.top(); q.pop(); g[y][x] = -1;
for (int i = 0; i < 4; ++i)
if (int y1 = y + d[i], x1 = x + d[i + 1]; min(y1, x1) >= 0 && y1 < m && x1 < n && g[y1][x1] >= 0)
q.push({max(v, g[y1][x1]), y1, x1}), r += max(0, v - g[y1][x1]), g[y1][x1] = -1;
} return r;
}
18.01.2025
1368. Minimum Cost to Make at Least One Valid Path in a Grid hard
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/868
Problem TLDR
Min undirected jumps to reach the end in grid #hard #bfs
Intuition
The naive Dijkstra with a sorted by cost
queue will work out.
Some optimizations to make it 0-1 BFS
:
- use a simple non-sorted queue
- explore
free
movements first - add
costly
movements to the end, keep track of the cost - think of this like a minesweeper game, free islands got explored first, extra steps add cost
Approach
- we can use two queues: one for
free
and forcostly
movements, or just a singleDeque
adding to the front or back - we can modify
grid
to track visited cells (golf solution, not a production code)
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(nm)\)
Code
fun minCost(grid: Array<IntArray>): Int {
val q = ArrayDeque<IntArray>(); q += intArrayOf(0, 0, 0)
val d = listOf(0, 1, 0, -1, 1, 0, -1, 0)
while (q.size > 0) {
val (c, y, x) = q.removeFirst()
if (y == grid.lastIndex && x == grid[0].lastIndex) return c
if (grid.getOrNull(y)?.getOrNull(x) ?: 0 < 1) continue
val curr = grid[y][x]; grid[y][x] = 0
for (i in 0..3) if (i + 1 == curr)
q.addFirst(intArrayOf(c, y + d[2 * i], x + d[2 * i + 1]))
else q += intArrayOf(c + 1, y + d[2 * i], x + d[2 * i + 1])
}
return -1
}
pub fn min_cost(mut grid: Vec<Vec<i32>>) -> i32 {
let mut q = VecDeque::from_iter([(0i32, 0i32, 0i32)]);
let (m, n) = (grid.len() as i32, grid[0].len() as i32);
while let Some((c, y, x)) = q.pop_front() {
if y == m - 1 && x == n - 1 { return c }
if !(0..m).contains(&y) || !(0..n).contains(&x) { continue }
let curr = grid[y as usize][x as usize] as usize;
grid[y as usize][x as usize] = 0; if curr < 1 { continue }
for (d, dy, dx) in [(1, 0, 1), (2, 0, -1), (3, 1, 0), (4, -1, 0)] {
if d == curr { q.push_front((c, y + dy, x + dx)) }
else { q.push_back((c + 1, y + dy, x + dx)) }}
}; -1
}
int minCost(vector<vector<int>>& g) {
deque<tuple<int, int, int>> q};
int d[] = {0, 1, 0, -1, 1, 0, -1, 0}, m = g.size(), n = g[0].size();
while (q.size()) {
auto [c, y, x] = q.front(); q.pop_front();
if (y == m - 1 && x == n - 1) return c;
if (min(y, x) < 0 || y == m || x == n || !g[y][x]) continue;
int curr = exchange(g[y][x], 0);
for (int i = 0; i < 4; ++i) if (i + 1 == curr)
q.emplace_front(c, y + d[2 * i], x + d[2 * i + 1]); else
q.emplace_back(c + 1, y + d[2 * i], x + d[2 * i + 1]);
}
return -1;
}
17.01.2025
2683. Neighboring Bitwise XOR medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/867
Problem TLDR
Can restore next-sibl-xored array? #medium #xor
Intuition
Observe an example:
// a b c
// 1 1 0
// a^b a != b a=1 b=1^1 = 0
// b^c b != c b=0 c=1^0 = 1
// c^a c == a c=1 a=0^1 = 1 correct
We can assume the initial value a
and after all-xor
operation compare if it is the same.
Approach
- initial value can be
0
or1
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun doesValidArrayExist(derived: IntArray) =
derived.reduce(Int::xor) < 1
pub fn does_valid_array_exist(derived: Vec<i32>) -> bool {
derived.into_iter().reduce(|a, b| a ^ b).unwrap() < 1
}
bool doesValidArrayExist(vector<int>& derived) {
int a = 1; for (int x: derived) a ^= x;
return a;
}
16.01.2025
2425. Bitwise XOR of All Pairings medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/866
Problem TLDR
Xor of all pairs xors #medium #xor
Intuition
Observe the all pairs xor:
// 2 1 3
// 10 2 5 0
// 2^10 2^2 2^5 2^0
// 1^10 1^2 1^5 1^0
// 3^10 3^2 3^5 3^0
Even size will reduce other array to 0.
Approach
- we can use a single variable
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun xorAllNums(nums1: IntArray, nums2: IntArray) =
nums1.reduce(Int::xor) * (nums2.size % 2) xor
nums2.reduce(Int::xor) * (nums1.size % 2)
pub fn xor_all_nums(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let mut r = 0;
if nums2.len() % 2 > 0 { for x in &nums1 { r ^= x }}
if nums1.len() % 2 > 0 { for x in &nums2 { r ^= x }}; r
}
int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
int r = 0;
if (nums2.size() % 2) for (int x: nums1) r ^= x;
if (nums1.size() % 2) for (int x: nums2) r ^= x;
return r;
}
15.01.2025
2429. Minimize XOR medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/865
Problem TLDR
Min xor with num1, bits count of num2 #medium
Intuition
// 0011
// 0101
// 0101
// 1 1
// 11001
// 1001000
- if bits count are equal, just return num1, as num1 ^ num1 = 0
- if bits count is more, bc(num1) > bc(num2), we want all the bits of num1 plus the lowest possible vacancies filled
- otherwise, we want lowest possible bits of num1 turned off to make
res ^ num1
minimum (so, leave highest bits of num1 set inres
)
Approach
- we can iterate over bits, or over counts differences
- careful of the Rust
usize
overflow
Complexity
-
Time complexity: \(O(log(n))\)
-
Space complexity: \(O(1)\)
Code
fun minimizeXor(num1: Int, num2: Int): Int {
var cnt = num2.countOneBits() - num1.countOneBits()
var res = num1; var b = 0
while (cnt != 0) {
while ((num1 and (1 shl b) > 0) == cnt > 0) b++
res = res xor (1 shl b++)
if (cnt > 0) cnt-- else cnt++
}
return res
}
pub fn minimize_xor(num1: i32, num2: i32) -> i32 {
let (mut cnt, mut r) =
((num2.count_ones() - num1.count_ones()) as i8, num1);
for b in 0..32 {
if cnt != 0 && ((num1 & (1 << b)) > 0) != (cnt > 0) {
r ^= 1 << b; if cnt > 0 { cnt -= 1 } else { cnt += 1 }
}
}; r
}
int minimizeXor(int num1, int num2) {
int cnt = __builtin_popcount(num2) - __builtin_popcount(num1), r = num1;
for (int b = 0; b < 32 && cnt; ++b)
if ((num1 & (1 << b)) > 0 != cnt > 0)
r ^= 1 << b, cnt -= 2 * (cnt > 0) - 1;
return r;
}
14.01.2025
2657. Find the Prefix Common Array of Two Arrays medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/864
Problem TLDR
A[..i] and B[..i] intersections sizes #medium #counting
Intuition
The problem size is small, for 50 elements brute-force is accepted.
The optimal solution is to do a running counting of visited elements.
Approach
- brute-force is the shortest code
- we can do a 50-bitmask
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun findThePrefixCommonArray(A: IntArray, B: IntArray) =
List(A.size) { A.slice(0..it).intersect(B.slice(0..it)).size }
pub fn find_the_prefix_common_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let (mut f, mut c) = (0u64, 0);
(0..a.len()).map(|i| {
let (a, b) = (1 << a[i] as u64, 1 << b[i] as u64);
c += (f & a > 0) as i32; f |= a;
c += (f & b > 0) as i32; f |= b; c
}).collect()
}
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
vector<int> f(A.size() + 1), res(A.size()); int cnt = 0;
for (int i = 0; i < A.size(); ++i)
res[i] = (cnt += (++f[A[i]] > 1) + (++f[B[i]] > 1));
return res;
}
13.01.2025
3223. Minimum Length of String After Operations medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/863
Problem TLDR
Length after removing repeatings > 2 #medium
Intuition
The takeaways are always either 1
or 2
:
// 1 -> 1
// 2 -> 2
// 3 -> 1
// 4 -> 2
// 5 -> 3 -> 1
// 6 -> 4 -> 2
// 7 -> 1
// 8 -> 2
Count each char’s frequency.
Approach
- we can do some arithmetics
2 - 2 * f
- careful: only count existing characters
- we can apply bitmasks instead of
f[26]
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun minimumLength(s: String) =
s.groupBy { it }.values.sumBy {
2 - it.size % 2
}
pub fn minimum_length(s: String) -> i32 {
let mut f = vec![0; 26];
for b in s.bytes() { f[(b - b'a') as usize] += 1 }
(0..26).filter(|&b| f[b] > 0).map(|b| 2 - f[b] % 2).sum()
}
int minimumLength(string s) {
int e = 0, f = 0;
for (char c: s)
f ^= 1 << (c - 'a'), e |= 1 << (c - 'a');
return 2 * __builtin_popcount(e) - __builtin_popcount(f & e);
}
12.01.2025
2116. Check if a Parentheses String Can Be Valid medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/862
Problem TLDR
Balance parenthesis with wildcards #medium
Intuition
Didn’t solve it without a hint.
Some examples to observe the problem:
// 100000
// (((()(
// 000111
// ()((()
// 101111 f b
// ((()))
// * 0 1
// * 1 2
The corner cases that can’t be balanced:
- odd string length
- locked unbalanced open brace (which is why we have to check the reversed order too)
The hint is: greedy solution just works, consider unlocked positions as wildcards, balance otherwise and check corner cases.
Approach
- separate counters
wildcards
andbalance
can just be a singlebalance
variable, ifwildcards + balance >= 0
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun canBeValid(s: String, locked: String, o: Char = '('): Boolean {
if (s.length % 2 > 0) return false; var b = 0
for (i in s.indices)
if (s[i] == o || locked[i] == '0') b++
else if (--b < 0) return false
return o == ')' || canBeValid(s.reversed(), locked.reversed(), ')')
}
pub fn can_be_valid(s: String, locked: String) -> bool {
if s.len() % 2 > 0 { return false }
let (mut b, mut o, s) = ([0, 0], [b'(', b')'], s.as_bytes());
for i in 0..s.len() { for j in 0..2 {
let i = if j > 0 { s.len() - 1 - i } else { i };
if s[i] == o[j] || locked.as_bytes()[i] == b'0' { b[j] += 1 }
else { b[j] -= 1; if b[j] < 0 { return false }}
}}; true
}
bool canBeValid(string s, string locked) {
if (s.size() % 2 > 0) return 0;
int b[2] = {0}, o[2] = {'(', ')'};
for (int i = 0; i < s.size(); ++i) for (int j = 0; j < 2; ++j) {
int k = j ? s.size() - 1 - i : i;
if (s[k] == o[j] || locked[k] == '0') ++b[j];
else if (--b[j] < 0) return 0;
} return 1;
}
11.01.2025
1400. Construct K Palindrome Strings medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/861
Problem TLDR
Can make k
palindromes from string? #medium
Intuition
The main difficulty is to define how chars frequencies can be used to make k
palindromes:
- chars number must be at least
k
, this is a lower boundary - the
odd
frequencies count must be<= k
, this is a higher boundary even
frequencies are all dissolved into any number of palindromes
Approach
- to find those rules on the fly, we should do attempts on examples (by running the code, or writing them down, or imagine if you can)
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\), O(n) for Kotlin golf
Code
fun canConstruct(s: String, k: Int) =
k <= s.length && s.groupBy { it }
.values.sumBy { it.size % 2 } <= k
pub fn can_construct(s: String, k: i32) -> bool {
let (mut f, k) = (vec![0; 26], k as usize);
for b in s.bytes() { f[(b - b'a') as usize] += 1 }
k <= s.len() &&
(0..26).map(|b| f[b] % 2).sum::<usize>() <= k
}
bool canConstruct(string s, int k) {
int f[26] = {0}, c = 0;
for (int i = 0; i < s.size(); ++i) c += 2 * (++f[s[i] - 'a'] % 2) - 1;
return k <= s.size() && c <= k;
}
10.01.2025
916. Word Subsets medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/860
Problem TLDR
Words containing all chars of words2 #medium
Intuition
Calculate the maximum frequency of words2, then filter words1.
Approach
- how short can it be?
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun wordSubsets(words1: Array<String>, words2: Array<String>) = buildList {
val f2 = IntArray(26)
fun Array<String>.f() = asSequence().map { w ->
val f = IntArray(26); for (c in w) f[c - 'a']++; f to w
}
for ((f, w) in words2.f()) for (i in 0..<26) f2[i] = max(f2[i], f[i])
for ((f, w) in words1.f()) if ((0..<26).all { f2[it] <= f[it] }) add(w)
}
pub fn word_subsets(words1: Vec<String>, words2: Vec<String>) -> Vec<String> {
let mut f2 = vec![0; 26];
let f = |w: &String| { let mut f = vec![0; 26];
for c in w.bytes() { f[(c - b'a') as usize] += 1 }; f };
for w in words2.iter() {
let f = f(w); for i in 0..26 { f2[i] = f2[i].max(f[i]) } }
words1.into_iter().filter(|w| {
let f = f(w); (0..26).all(|i| f2[i] <= f[i]) }).collect()
}
vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
int f2[26] = {0}; vector<string> res;
for (auto &w: words2) {
int f[26] = {0}; for (char c: w) f2[c - 'a'] = max(f2[c - 'a'], ++f[c - 'a']);
}
for (auto &w: words1) {
int f[26] = {0}; for (char c: w) ++f[c - 'a'];
for (int i = 0; i < 26; ++i) if (f2[i] > f[i]) goto out;
res.push_back(w); out:
} return res;
}
09.01.2025
2185. Counting Words With a Given Prefix easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/859
Problem TLDR
Count words with prefix #easy
Intuition
Brute-force is optimal.
Approach
- how short can it be?
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun prefixCount(words: Array<String>, pref: String) =
words.count { it.startsWith(pref) }
pub fn prefix_count(words: Vec<String>, pref: String) -> i32 {
words.iter().filter(|w| w.starts_with(&pref)).count() as _
}
int prefixCount(vector<string>& words, string pref) {
int r = 0;
for (auto &w: words) r += w.starts_with(pref);
return r;
}
08.01.2025
3042. Count Prefix and Suffix Pairs I easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/858
Problem TLDR
Count prefix-suffix matched pairs #easy
Intuition
The brute-force is accepted.
More interesting solutions are:
- Trie: traverse each word forwards and backwards, if suffix trie has the same word as prefix trie, add frequency
- HashMap: just store words in a frequency HashMap and traverse it on each new word
- Robin-Karp rolling hash & KMP/z-function: same idea as with Trie, but check rolling hash to match visited hashes, then do quick-match with KMP/z-function
Approach
- on a smaller input the O(n^2) solutions are faster
- we can use a single Trie with the key of
(prefix-letetr, suffix-letter)
Complexity
-
Time complexity: \(O(n^2w^2)\), or O(nw) for more optimal
-
Space complexity: \(O(1)\) or O(n)
Code
fun countPrefixSuffixPairs(words: Array<String>) =
(0..<words.size).flatMap { i -> (i + 1..<words.size).map { i to it }}
.count { (i, j) -> words[j].startsWith(words[i]) && words[j].endsWith(words[i])}
pub fn count_prefix_suffix_pairs(words: Vec<String>) -> i32 {
#[derive(Default)] struct T(usize, i32, HashMap<u8, T>);
let (mut tf, mut tb, mut res) = (T::default(), T::default(), 0);
for (p, w) in words.iter().map(|w| w.as_bytes()).enumerate() {
let (mut f, mut b) = (&mut tf, &mut tb);
for i in 0..w.len() {
let (cf, cb) = (w[i], w[w.len() - i - 1]);
f = f.2.entry(cf).or_default();
b = b.2.entry(cb).or_default();
if f.0 > 0 && f.0 == b.0 { res += f.1 }
}
f.0 = p + 1; b.0 = p + 1; f.1 += 1; b.1 += 1
}
res
}
int countPrefixSuffixPairs(vector<string>& words) {
unordered_map<string, int> m; int res = 0; m[words[0]] = 1;
for (int i = 1; i < words.size(); ++m[words[i++]])
for (auto& [prev, freq] : m)
if (words[i].starts_with(prev) && words[i].ends_with(prev))
res += freq;
return res;
}
07.01.2025
1408. String Matching in an Array easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/857
Problem TLDR
All substrings #easy
Intuition
Brute force is accepted.
Approach
- we can improve speed by searching for at least 2 matches in the joined words (and speed this up with KMP or Robin-Karp rolling hash)
- careful to not include the word twice
Complexity
-
Time complexity: \(O(n^2w^2)\), w^2 for
word1.contains(word2)
-
Space complexity: \(O(n)\)
Code
fun stringMatching(words: Array<String>) =
words.filter { w -> words.any { w != it && w in it }}
pub fn string_matching(words: Vec<String>) -> Vec<String> {
words.iter().filter(|w| words.iter().any(|w2|
*w != w2 && w2.contains(*w))).cloned().collect()
}
vector<string> stringMatching(vector<string>& words) {
vector<string> r;
for (int i = 0; i < words.size(); ++i)
for (int j = 0; j < words.size(); ++j)
if (i != j && words[j].find(words[i]) != string::npos) {
r.push_back(words[i]); break;
}
return r;
}
06.01.2025
1769. Minimum Number of Operations to Move All Balls to Each Box medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/856
Problem TLDR
Sum distances to all 1
for every position #medium #prefix_sum
Intuition
Let’s observe an example:
// 012345
// 001011
// * 2 45 2+4+5=11, right = 3
// *1 34 11-3=8, right = 3
// * 23 8-3=5 , left = 1, right = 2
// *12 5-2=3, +1=4
// * 3-2=1, +2=3, right = 1, left = 2
// * 1-1, 2+2=4
- the minimum operations of moving all
1
to positioni
is the sum of the distances - we can reuse the previous position result: all
1
’s to the right became closer, and all1
’s to the left increase distance, so we dosum[i + 1] = sum[i] - right_ones + left_ones
Approach
- we don’t need a separate variable for the
left
andright
, as we always operate on thebalance = left - right
- careful with the operations order
- single-pass is impossible, as we should know the balance on the first position already
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun minOperations(boxes: String): IntArray {
var b = 0; var s = 0
for ((i, c) in boxes.withIndex())
if (c > '0') { b--; s += i }
return IntArray(boxes.length) { i ->
s.also { b += 2 * (boxes[i] - '0'); s += b }
}
}
pub fn min_operations(boxes: String) -> Vec<i32> {
let (mut b, mut s) = (0, 0);
for (i, c) in boxes.bytes().enumerate() {
if c > b'0' { b -= 1; s += i as i32 }
}
boxes.bytes().enumerate().map(|(i, c)| {
let r = s; b += 2 * (c - b'0') as i32; s += b; r
}).collect()
}
vector<int> minOperations(string boxes) {
int b = 0, s = 0; vector<int> r(boxes.size());
for (int i = 0; i < boxes.size(); ++i)
if (boxes[i] > '0') b--, s += i;
for (int i = 0; i < boxes.size(); ++i)
r[i] = s, b += 2 * (boxes[i] - '0'), s += b;
return r;
}
05.01.2025
2381. Shifting Letters II medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/855
Problem TLDR
Apply from..to, direction
shifts to string chars #medium #line_sweep
Intuition
We can sort the shifts intervals, then walk them, calculating the running value of shift.
One optimization is to store the starts and ends of each shift in a cumulative shifts array, then scan it’s running value in a linear way.
Approach
- in Rust we can modify the stirng in-place with
unsafe { s.as_bytes_mut() }
- the difference betwen
auto s: shifts
andauto &s: shifts
in c++ is 4ms vs 40ms
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun shiftingLetters(s: String, shifts: Array<IntArray>) = buildString {
val shift = IntArray(s.length + 1); var sh = 0
for ((s, e, d) in shifts) {
shift[s] += d * 2 - 1
shift[e + 1] -= d * 2 - 1
}
for ((i, c) in s.withIndex()) {
sh += shift[i]
append('a' + (c - 'a' + sh % 26 + 26) % 26)
}
}
pub fn shifting_letters(s: String, shifts: Vec<Vec<i32>>) -> String {
let (mut shift, mut sh, mut r) = (vec![0; s.len() + 1], 0, vec![0; s.len()]);
for sh in shifts {
let (s, e, d) = (sh[0] as usize, sh[1] as usize, sh[2] * 2 - 1);
shift[s] += d; shift[e + 1] -= d
}
for (i, c) in s.bytes().enumerate() {
sh += shift[i];
r[i] = b'a' + (c - b'a' + (sh % 26 + 26) as u8) % 26
}; String::from_utf8(r).unwrap()
}
string shiftingLetters(string s, vector<vector<int>>& shifts) {
int sh[50001] = {0}, d = 0;
for (auto &s: shifts)
sh[s[0]] += s[2] * 2 - 1, sh[s[1] + 1] -= s[2] * 2 - 1;
for (int i = 0; i < s.size(); ++i)
s[i] = 'a' + (s[i] - 'a' + (d += sh[i]) % 26 + 26) % 26;
return s;
}
04.01.2025
1930. Unique Length-3 Palindromic Subsequences medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/854
Problem TLDR
Count palindromes of length 3 #medium
Intuition
Count unique characters between each pair of the same chars
Approach
- building a HashSet can be slower then just checking for contains 26 times
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun countPalindromicSubsequence(s: String) =
('a'..'z').sumOf { c ->
val s = s.slice(s.indexOf(c) + 1..< s.lastIndexOf(c))
('a'..'z').count { it in s }
}
pub fn count_palindromic_subsequence(s: String) -> i32 {
('a'..='z').map(|c| {
let i = s.find(c).unwrap_or(0);
let j = s.rfind(c).unwrap_or(0);
if i + 1 >= j { 0 } else
{ ('a'..='z').filter(|&c| s[i+1..j].contains(c)).count() }
}).sum::<usize>() as i32
}
int countPalindromicSubsequence(string s) {
int f[26] = {}, l[26] = {}, r = 0; fill(f, f+26, INT_MAX);
for (int i = 0; i < s.size(); ++i)
f[s[i] - 'a'] = min(f[s[i] - 'a'], i), l[s[i] - 'a'] = i;
for (int i = 0; i < 26; ++i) if (f[i] < l[i])
r += unordered_set<char>(begin(s) + f[i] + 1, begin(s) + l[i]).size();
return r;
}
03.01.2025
2270. Number of Ways to Split Array medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/853
Problem TLDR
Count splits left_sum >= right_sum #medium #prefix_sum
Intuition
Prefix sum can help solve this.
Approach
- careful with an
int
overflow - this is not about the balance and con’t be done in a single pass, as adding negative number decreases the sum, we should hold
left
andright
part separately
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun waysToSplitArray(nums: IntArray): Int {
var r = nums.sumOf { it.toLong() }; var l = 0L
return (0..<nums.lastIndex).count {
l += nums[it]; r -= nums[it]; l >= r
}
}
pub fn ways_to_split_array(nums: Vec<i32>) -> i32 {
let (mut l, mut r) = (0, nums.iter().map(|&x| x as i64).sum());
(0..nums.len() - 1).filter(|&i| {
l += nums[i] as i64; r -= nums[i] as i64; l >= r
}).count() as _
}
int waysToSplitArray(vector<int>& nums) {
int res = 0; long long r = reduce(begin(nums), end(nums), 0LL), l = 0;
for (int i = 0; i < nums.size() - 1; ++i)
res += (l += nums[i]) >= (r -= nums[i]);
return res;
}
02.01.2025
2559. Count Vowel Strings in Ranges medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/852
Problem TLDR
Count words[q[0]..q[1]] starting and ending with “aeiou” #medium
Intuition
The prefix sum will answer to each query in O(1) time.
Approach
- to check vowels, we can use a HashSet, bitmask or just a String
- in some languages
bool
can be converted toint
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun vowelStrings(words: Array<String>, queries: Array<IntArray>): List<Int> {
val fr = IntArray(words.size + 1); val wv = "aeiou"
for ((i, w) in words.withIndex()) fr[i + 1] = fr[i] +
if (w[0] in wv && w.last() in wv) 1 else 0
return queries.map { (f, t) -> fr[t + 1] - fr[f] }
}
pub fn vowel_strings(words: Vec<String>, queries: Vec<Vec<i32>>) -> Vec<i32> {
let mut fr = vec![0; words.len() + 1]; let wv = |b| 1065233 >> (b - b'a') & 1;
for (i, w) in words.iter().map(|w| w.as_bytes()).enumerate() {
fr[i + 1] = fr[i] + wv(w[0]) * wv(w[w.len() - 1])
}
queries.iter().map(|q| fr[q[1] as usize + 1] - fr[q[0] as usize]).collect()
}
vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
unordered_set<char> vw({'a', 'e', 'i', 'o', 'u'}); vector<int> f(1), res;
for (auto &w: words) f.push_back(f.back() + (vw.count(w.front()) && vw.count(w.back())));
for (auto &q: queries) res.push_back(f[q[1] + 1] - f[q[0]]);
return res;
}
01.01.2025
1422. Maximum Score After Splitting a String easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/851
Problem TLDR
Max(left_zeros + right_ones) #easy
Intuition
The brute-force works: try every possible position split.
The better way is two-pass: count the total ones
, then decrease it at every step.
The optimal solution is a single pass: notice, how the sum = zeros + ones
changes at every move, we actually computing the balance around the total ones
.
Approach
- try every solution
- how short can it be?
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun maxScore(s: String): Int {
var ones = s.last() - '0'; var b = 0
return s.dropLast(1).maxOf {
if (it > '0') { ones++; --b } else ++b
} + ones
}
pub fn max_score(s: String) -> i32 {
let (mut ones, mut b) = (0, 0);
s.bytes().enumerate().map(|(i, c)| {
ones += (c > b'0') as i32;
if i < s.len() - 1 {
b -= (c > b'0') as i32 * 2 - 1; } b
}).max().unwrap() + ones
}
int maxScore(string s) {
int o = s[s.size() - 1] == '1', b = 0, r = -1;
for (int i = 0; i < s.size() - 1; ++i) {
o += s[i] > '0';
b -= (s[i] > '0') * 2 - 1;
r = max(r, b);
} return r + o;
}
31.12.2024
983. Minimum Cost For Tickets medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/849
Problem TLDR
Min sum buying 1,7,30-days tickets to travel all days #medium #dymanic_programming
Intuition
Observing the data:
// 1,2,3,4,5,6,7,8,9,10,29,30,31 2 7 15
// * . +2
// * . +2 4
// * . +2 6
// * . +2 8 vs 7, take 7,
// . from = max(1, 4-7)
// . . . to = from+7
// * +2 9
// * +2 11
// * +2 13
- we can retrospectively switch previous ticket from
1
-day to7
day or30
days if it is a less expensive (this is a cleverer solution and requires a clever implementation, so initially I’ve dropped this idea) - the tail (or the head) is independent and can be calculated separately, meaning, we can do a full Depth-First search and cache the result
Approach
- top-down DFS is easier to reason about: do choices, choose the best, then add the caching
- then rewrite to the bottom-up, reverse an iteration order for the CPU cache speed
- the idea of retrospectively replacing the 1-day ticket for 7 or 30-days can be written with queues of 7-day and 30-days ticket results: pop expired from the front, add the current to the tail, best result are at the front (c++ solution)
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\), O(1) for queues, as only the last 30 days are considered
Code
val dp = HashMap<Int, Int>()
fun mincostTickets(days: IntArray, costs: IntArray, start: Int = 0): Int =
if (start < days.size) dp.getOrPut(start) {
var i = start
costs.zip(listOf(1, 7, 30)).minOf { (c, d) ->
while (i < days.size && days[i] - days[start] < d) ++i
c + mincostTickets(days, costs, i)
}
} else 0
pub fn mincost_tickets(days: Vec<i32>, costs: Vec<i32>) -> i32 {
let mut dp = vec![i32::MAX; days.len() + 1]; dp[0] = 0;
for start in 0..days.len() {
let mut i = start;
for (c, d) in costs.iter().zip([1, 7, 30]) {
while i < days.len() && days[i] - days[start] < d { i += 1 }
dp[i] = dp[i].min(dp[start] + c)
}
}; dp[days.len()]
}
int mincostTickets(vector<int>& days, vector<int>& costs) {
queue<pair<int, int>> last7, last30; int res = 0;
for (auto d: days) {
while (last7.size() && last7.front().first + 7 <= d) last7.pop();
while (last30.size() && last30.front().first + 30 <= d) last30.pop();
last7.push({d, res + costs[1]});
last30.push({d, res + costs[2]});
res = min({res + costs[0], last7.front().second, last30.front().second});
} return res;
}
30.12.2024
2466. Count Ways To Build Good Strings medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/848
Problem TLDR
Ways to make 01
-string length of low..high
#medium #dynamic_programming
Intuition
Let’s observe what happens when we adding zeros and ones:
// "0" "11" -> 00 011 110 1111
// 00 111 -> 00 111 00111 111111 0000 11100
// 000 111 -> 000 111 000111 111000 000000 111111
// * .
// 000111000 000111111
// .
// 111000000 111000111
- each new string is a start of another tree of possibilities
- only the length of this string matters
Let’s do a full Depth-First search, give the current length add zeros or add ones and count the total ways. The result can be cached by the key of the starting length.
Approach
- top-down can be rewritten to the bottom-up DP
- then we can reverse the order of iteration
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
val dp = HashMap<Int, Long>()
fun countGoodStrings(low: Int, high: Int, zero: Int, one: Int, len: Int = 0): Long =
if (len > high) 0L else dp.getOrPut(len) {
val addZeros = countGoodStrings(low, high, zero, one, len + zero)
val addOnes = countGoodStrings(low, high, zero, one, len + one)
((if (len < low) 0 else 1) + addZeros + addOnes) % 1_000_000_007L
}
pub fn count_good_strings(low: i32, high: i32, zero: i32, one: i32) -> i32 {
let mut dp = vec![0; 1 + high as usize];
for len in 0..=high as usize {
let add_zeros = dp.get(len - zero as usize).unwrap_or(&0);
let add_ones = dp.get(len - one as usize).unwrap_or(&0);
let curr = (low + len as i32 <= high) as usize;
dp[len] = (curr + add_zeros + add_ones) % 1_000_000_007
}; dp[high as usize] as i32
}
int countGoodStrings(int low, int high, int zero, int one) {
int dp[100001];
for (int l = 0; l <= high; ++l) dp[l] = ((low + l <= high) +
(l < zero ? 0 : dp[l - zero]) +
(l < one ? 0 : dp[l - one])) % 1000000007;
return dp[high];
}
29.12.2024
1639. Number of Ways to Form a Target String Given a Dictionary hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/847
Problem TLDR
Ways to make target with increasing positions in words #hard #dynamic_programming
Intuition
Let’s observe an example at different angles:
// acca bbbb caca aba
// a .b ...a
// a ..b ...a
// a..a .b ....
// a..a ..b. ....
// ...a ..b. .a
// ..b .a.a
// 0123
// a
// aa a
// bbbb
// ccc
// c
// 0 1 2 2 1 0 1 2 0 0 2 1
// [a,b,c]->[a,b,c]->[b,c,c]->[a,a,b]
// aba
// * * *
// * * *
// * * *
// * * *
// * * *
// * * *
Each position i
in words[..]
have a set of chars words[..][i]
. We can use a full Depth-First Search and take
or drop
the current position. To count total ways, we should multiply by count of the taken chars at position. Result can be safely cached by (i, target_pos)
key.
Approach
- we can rewrite top-down DFS + memo into iterative bottom-up DP
- as we only depend on the next (or previous) positions, we can collapse 2D dp into 1D
- some other small optimizations possible, iterate forward for cache-friendliness
Complexity
-
Time complexity: \(O(wt)\)
-
Space complexity: \(O(t)\)
Code
fun numWays(words: Array<String>, target: String): Int {
val fr = Array(words[0].length) { IntArray(26) }
for (w in words) for (i in w.indices) fr[i][w[i] - 'a']++
val dp = Array(fr.size + 1) { LongArray(target.length + 1) { -1L }}
fun dfs(posF: Int, posT: Int): Long = dp[posF][posT].takeIf { it >= 0 } ?: {
if (posT == target.length) 1L else if (posF == fr.size) 0L else {
val notTake = dfs(posF + 1, posT)
val curr = fr[posF][target[posT] - 'a'].toLong()
val take = if (curr > 0) curr * dfs(posF + 1, posT + 1) else 0
(take + notTake) % 1_000_000_007L
}}().also { dp[posF][posT] = it }
return dfs(0, 0).toInt()
}
pub fn num_ways(words: Vec<String>, target: String) -> i32 {
let mut dp = vec![0; target.len() + 1]; dp[target.len()] = 1;
let M = 1_000_000_007i64; let target: Vec<_> = target.bytes().rev().collect();
for posF in 0..words[0].len() {
let mut fr = vec![0; 26];
for w in &words { fr[(w.as_bytes()[posF] - b'a') as usize] += 1 }
for (posT, t) in target.iter().enumerate() {
dp[posT] += fr[(t - b'a') as usize] * dp[posT + 1] % M
}
}; (dp[0] % M) as i32
}
int numWays(vector<string>& words, string target) {
long d[10001] = { 1 }, M = 1e9 + 7;
for (int i = 0; i < words[0].size(); ++i) {
int f[26] = {}; for (auto &w: words) ++f[w[i] - 97];
for (int j = min(i + 1, (int) target.size()); j; --j)
d[j] += f[target[j - 1] - 97] * d[j - 1] % M;
} return d[target.size()] % M;
}
28.12.2024
689. Maximum Sum of 3 Non-Overlapping Subarrays hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/846
Problem TLDR
3 max non-intersecting intervals #hard #dynamic_programming #sliding_window
Intuition
Failed to solve.
The naive DFS+memo with searching for best k
intervals starting with i
gives TLE.
Now, what working solutions are:
- Sliding window: slide 3 window
0..k
,k..2k
,2k..3k
together. The left window just search for it’s max sum. The middle search formax_left + max_middle
. And the right search formax_middle + max_right
. Update indices on every update of maximum. - Dynamic Programming:
dp[i][c]
is (max_sum, start_ind) forc
k-subarrays in0..i
. Then restore parents.
// 0 1 2 3 4 5 6 7 8 9
// ----- ~~~~~ -----
// 0 2 3 5 6 8
// ----- ~~~~~ -----
// 1 3 4 6 7 9 one loop iteration
Approach
- give up after 1 hour, then look for solutions
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun maxSumOfThreeSubarrays(nums: IntArray, k: Int): IntArray {
var i1 = intArrayOf(0); var i12 = i1 + 0; var i123 = i12 + 0
var s1 = 0; var s2 = 0; var s3 = 0; var m1 = 0; var m12 = 0; var m123 = 0
for (i in nums.indices) {
s1 += (nums.getOrNull(i - 2 * k) ?: 0) - (nums.getOrNull(i - 3 * k) ?: 0)
s2 += (nums.getOrNull(i - k) ?: 0) - (nums.getOrNull(i - 2 * k) ?: 0)
s3 += nums[i] - (nums.getOrNull(i - k) ?: 0)
if (s1 > m1) { m1 = s1; i1[0] = i - 3 * k + 1 }
if (m1 + s2 > m12) { m12 = m1 + s2; i12 = i1 + (i - 2 * k + 1) }
if (m12 + s3 > m123) { m123 = m12 + s3; i123 = i12 + (i - k + 1) }
}
return i123
}
pub fn max_sum_of_three_subarrays(nums: Vec<i32>, k: i32) -> Vec<i32> {
let k = k as usize;
let (mut i1, mut i12, mut i123) = (0, (0, k), [0, k, 2 * k]);
let mut s1 = nums[0..k].iter().sum::<i32>();
let mut s2 = nums[k..2 * k].iter().sum::<i32>();
let mut s3 = nums[2 * k..3 * k].iter().sum::<i32>();
let (mut m1, mut m12, mut m123) = (s1, s1 + s2, s1 + s2 + s3);
for i in 3 * k..nums.len() {
s1 += nums[i - 2 * k] - nums[i - 3 * k];
s2 += nums[i - k] - nums[i - 2 * k];
s3 += nums[i] - nums[i - k];
if s1 > m1 { m1 = s1; i1 = i - 3 * k + 1 }
if m1 + s2 > m12 { m12 = m1 + s2; i12 = (i1, i - 2 * k + 1) }
if m12 + s3 > m123 { m123 = m12 + s3; i123 = [i12.0, i12.1, i - k + 1] }
}; i123.iter().map(|&x| x as i32).collect()
}
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size(); vector<int> pref(n + 1, 0);
for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + nums[i - 1];
vector<vector<vector<int>>>dp(n + 1, vector<vector<int>>(4, vector<int>(2, 0)));
int mx = 0, pos = -1;
for (int c = 1; c <= 3; ++c) for (int i = k; i <= n; ++i) {
dp[i][c][0] = dp[i - 1][c][0];
dp[i][c][1] = dp[i - 1][c][1];
int sum = pref[i] - pref[i - k];
if (dp[i][c][0] < dp[i - k][c - 1][0] + sum)
dp[i][c][0] = dp[i - k][c - 1][0] + sum, dp[i][c][1] = i;
if (dp[i][c][0] > mx) mx = dp[i][c][0], pos = dp[i][c][1];
}
vector<int> res(3, 0); for (int i = 3; i; --i)
res[i - 1] = pos - k, pos = dp[pos - k][i - 1][1];
return res;
}
27.12.2024
1014. Best Sightseeing Pair medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/845
Problem TLDR
Max (a[i] + a[j] + i - j), i > j #medium #arithmetics
Intuition
Let’s move the pointers and observe:
// 0 1 2 3
// 3 1 2 5
// j
// i 5 - (3 - 0) + 3 = 5 - 3 + 0 + 3
// 5 - (3 - 1) + 1 = 5 - 3 + 1 + 1
// 5 - (3 - 2) + 2 = 5 - 3 + 2 + 2
Each time we move i
, all possible previous sums are decreased by distance of 1
. By writing down a[i] - (i - j) + a[j]
in another way: (a[i] - i) + (a[j] + j)
we derive the total sum is independent of the distance, always peek the max of a[j] + j
from the previous.
Some other things I’ve considered are: sorting, monotonic stack. But didn’t see any good use of them.
Approach
- the first previous value can be
0
instead ofvalues[0]
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun maxScoreSightseeingPair(values: IntArray): Int {
var p = 0
return values.withIndex().maxOf { (i, n) ->
(n - i + p).also { p = max(p, i + n) }
}
}
pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
let mut p = 0;
values.iter().enumerate().map(|(i, n)| {
let c = n - i as i32 + p; p = p.max(i as i32 + n); c
}).max().unwrap()
}
int maxScoreSightseeingPair(vector<int>& values) {
int res = 0;
for (int i = 0, p = 0; i < values.size(); ++i)
res = max(res, values[i] - i + p), p = max(p, values[i] + i);
return res;
}
26.12.2024
494. Target Sum medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/844
Problem TLDR
Count signs permutations to sum equal target #medium #dynamic_programming
Intuition
The DFS + memo: for every position and current target try plus
sign and minus
sign; terminal condition is target == 0
; add memo using a HashMap or 2D array.
More interesting is how to do this bottom-up: for each new number nums[i]
, check if we have previous results in dp[i - 1][target]
for every target in range -1000..1000
, and if so, do a plus
action and a minus
action by adding it to dp[i][target-nums[i]]
and dp[i][target+nums[i]]
.
The super-clever variant is a 1D dp (stealing it from others). It starts with math:
- we are adding another number to the previous result
- new_target + n = sum
- new_target - n = target
2 * new_target = sum + target, or new_target = (sum + target) / 2
.
That gives us the freedom to do just a plus
operation, and reuse the same dp
array, by adding the extra false-positive check: (sum + target) % 2 == 0, and abs(sum) >= abs(target).
Approach
- let’s implement all of the approaches to feel the numbers
Complexity
-
Time complexity: \(O(n^2)\) to O(n)
-
Space complexity: \(O(n^2)\) to O(n)
Code
fun findTargetSumWays(nums: IntArray, target: Int): Int {
val dp = HashMap<Pair<Int, Int>, Int>()
fun dfs(pos: Int, target: Int): Int = dp.getOrPut(pos to target) {
if (pos == nums.size) if (target == 0) 1 else 0
else dfs(pos + 1, target - nums[pos]) +
dfs(pos + 1, target + nums[pos])
}
return dfs(0, target)
}
pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
let mut dp = vec![vec![0; 2001]; nums.len()];
dp[0][1000 + nums[0] as usize] = 1; dp[0][1000 - nums[0] as usize] += 1;
for i in 1..dp.len() {
for target in 0..2001 {
if dp[i - 1][target] > 0 {
dp[i][target + nums[i] as usize] += dp[i - 1][target];
dp[i][target - nums[i] as usize] += dp[i - 1][target]
}
}
}; dp[dp.len() - 1][1000 + target as usize]
}
int findTargetSumWays(vector<int>& nums, int target) {
vector<int> dp(2001, 0); dp[0] = 1; int s = 0;
for (int n : nums) {
s += n;
for (int t = 1000 + target; t >= n; --t) dp[t] += dp[t - n];
}
return abs(s) < abs(target) || (s + target) % 2 > 0 ? 0: dp[(s + target) / 2];
}
25.12.2024
515. Find Largest Value in Each Tree Row medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/843
Problem TLDR
Tree layers maxes #medium
Intuition
Do DFS or BFS
Approach
- lambdas in c++ are interesting, don’t forget to add
&
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(log(n))\)
Code
fun largestValues(root: TreeNode?): List<Int> = buildList {
fun dfs(n: TreeNode?, d: Int): Unit = n?.run {
if (d < size) set(d, max(get(d), `val`)) else add(`val`)
dfs(left, d + 1); dfs(right, d + 1)
} ?: Unit
dfs(root, 0)
}
pub fn largest_values(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut res = vec![]; let Some(r) = root.clone() else { return res };
let mut q = VecDeque::from([r]);
while q.len() > 0 {
let mut max = i32::MIN;
for _ in 0..q.len() {
let n = q.pop_front().unwrap(); let n = n.borrow();
max = max.max(n.val);
if let Some(x) = n.left.clone() { q.push_back(x); }
if let Some(x) = n.right.clone() { q.push_back(x); }
}
res.push(max);
}; res
}
vector<int> largestValues(TreeNode* root) {
vector<int> r;
auto f = [&](this auto const& f, TreeNode* n, int d) -> void {
if (d < r.size()) r[d] = max(r[d], n->val); else r.push_back(n->val);
if (n->left) f(n->left, d + 1); if (n->right) f(n->right, d + 1);
}; if (root) f(root, 0); return r;
}
24.12.2024
3203. Find Minimum Diameter After Merging Two Trees hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/842
Problem TLDR
Diameter of 2 connected trees #hard #graph #toposort
Intuition
Can’t solve without hint. The hint: 1. connect by centers 2. center of tree is on the diameter 3. diameter if a two-bfs ends connected
There is another approach to find the diameter: topological sort.
Approach
- in toposort, the clever way to find a diameter:
dep[j] + dep[i] + 1
is a total length for both ends connected by one edge
Complexity
-
Time complexity: \(O(EV)\)
-
Space complexity: \(O(EV)\)
Code
fun minimumDiameterAfterMerge(edges1: Array<IntArray>, edges2: Array<IntArray>): Int {
val g = List(2) { HashMap<Int, ArrayList<Int>>() }; val q = ArrayDeque<Int>()
for ((g, e) in g.zip(listOf(edges1, edges2))) for ((a, b) in e) {
g.getOrPut(a) { arrayListOf() } += b; g.getOrPut(b) { arrayListOf() } += a }
fun bfs(s: Int, g: Map<Int, List<Int>>): List<Int> {
q.clear(); q += s; val seen = IntArray(g.size + 1); seen[s] = 1; var d = 0; var l = s
while (q.size > 0) {
val c = q.removeFirst(); l = c;
for (n in g[c] ?: listOf())
if (seen[n] == 0) { seen[n] = seen[c] + 1; q += n; d = max(d, seen[n]) }
}
return listOf(l, d - 1)
}
val d1 = bfs(bfs(0, g[0])[0], g[0])[1]; val d2 = bfs(bfs(0, g[1])[0], g[1])[1]
return maxOf(d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1)
}
pub fn minimum_diameter_after_merge(edges1: Vec<Vec<i32>>, edges2: Vec<Vec<i32>>) -> i32 {
let mut g = [HashMap::new(), HashMap::new()];
for (g, e) in g.iter_mut().zip([edges1, edges2]) { for e in e {
for ix in 0..2 { g.entry(e[ix % 2]).or_insert(vec![]).push(e[(ix + 1) % 2]); }
} }
fn bfs(s: i32, g: &HashMap<i32, Vec<i32>>) -> (i32, i32) {
let mut q = VecDeque::from([s]); let mut seen = vec![0; g.len() + 1];
seen[s as usize] = 1; let (mut l, mut d) = (s, 0);
while let Some(c) = q.pop_front() { l = c; if let Some(sibl) = g.get(&c) {
for &n in sibl { if seen[n as usize] == 0 {
seen[n as usize] = seen[c as usize] + 1;
d = d.max(seen[n as usize]);
q.push_back(n);
}}}}
(l, d - 1)
}
let d1 = bfs(bfs(0, &g[0]).0, &g[0]).1; let d2 = bfs(bfs(0, &g[1]).0, &g[1]).1;
d1.max(d2).max(1 + (d1 + 1) / 2 + (d2 + 1) / 2)
}
int minimumDiameterAfterMerge(vector<vector<int>>& e1, vector<vector<int>>& e2) {
auto f = [](this auto const& f, vector<vector<int>>& e) -> int {
int n = e.size() + 1, res = 0; queue<int> q;
vector<vector<int>> g(n); vector<int> deg(n), dep(n), vis(n);
for (const auto &e: e) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
for (int i = 0; i < n; ++i) if ((deg[i] = g[i].size()) == 1) q.push(i);
while (q.size()) {
int i = q.front(); q.pop(); vis[i] = 1;
for (int j: g[i]) {
if (--deg[j] == 1) q.push(j);
if (!vis[j]) {
res = max(res, dep[j] + dep[i] + 1);
dep[j] = max(dep[j], dep[i] + 1);
}
}
}
return res;
};
int d1 = f(e1), d2 = f(e2);
return max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1});
}
23.12.2024
2471. Minimum Number of Operations to Sort a Binary Tree by Level medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/841
Problem TLDR
Min swaps to sort tree layers #medium #cycle-sort #bfs
Intuition
Can’t solve without a hint. The hint: cycle-sort has optimal swaps count.
// 0 1 2 3 4 5
// 4 5 1 0 3 2
// 0 4
// 1 5
// 2 5
// 3 4
//
// 7 6 5 4
// 0 1 2 3
// 3 2 1 0
To do the cycle-sort, we convert the layer numbers into indices sorted accordingly, then do swap(ix[i], ix[ix[i]])
until all indices at their places.
Approach
- we can use a hashmap or just an array for indices to value mapping
Complexity
-
Time complexity: \(O(nlog(n))\) to sort layers
-
Space complexity: \(O(n)\)
Code
fun minimumOperations(root: TreeNode?): Int {
val q = ArrayDeque<TreeNode>(listOf(root ?: return 0))
var res = 0
while (q.size > 0) {
val s = ArrayList<Int>()
repeat(q.size) {
val n = q.removeFirst(); s += n.`val`
n.left?.let { q += it }; n.right?.let { q += it }
}
val ix = s.indices.sortedBy { s[it] }.toIntArray()
for (i in 0..<ix.size) while (ix[i] != i) {
ix[i] = ix[ix[i]].also { ix[ix[i]] = ix[i] }; res++
}
}
return res
}
pub fn minimum_operations(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let Some(r) = root else { return 0 };
let (mut q, mut r) = (VecDeque::from([r]), 0);
while q.len() > 0 {
let mut s = vec![];
for _ in 0..q.len() {
let n = q.pop_front().unwrap(); let n = n.borrow(); s.push(n.val);
if let Some(n) = n.left.clone() { q.push_back(n) }
if let Some(n) = n.right.clone() { q.push_back(n) }
}
let mut ix: Vec<_> = (0..s.len()).collect();
ix.sort_unstable_by_key(|&i| s[i]);
for i in 0..ix.len() { while ix[i] != i {
let t = ix[i]; ix[i] = ix[t]; ix[t] = t; r += 1
}}
}; r
}
int minimumOperations(TreeNode* root) {
int r = 0; vector<TreeNode*> q{root};
while (q.size()) {
vector<TreeNode*> q1; vector<int> s, ix(q.size());
for (auto n: q) {
s.push_back(n->val);
if (n->left) q1.push_back(n->left);
if (n->right) q1.push_back(n->right);
}
iota(begin(ix), end(ix), 0);
sort(begin(ix), end(ix), [&](int i, int j){ return s[i] < s[j];});
for (int i = 0; i < ix.size(); ++i) for (; ix[i] != i; ++r)
swap(ix[i], ix[ix[i]]);
swap(q, q1);
} return r;
}
22.12.2024
2940. Find Building Where Alice and Bob Can Meet hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/840
Problem TLDR
Common indices t, h[t] > h[a], h[t] > h[b] for queries q[][a,b] #hard #monotonic_stack
Intuition
Didn’t solve it without a hint. The hint: consider queries by rightmost border, use monotonic stack, binary search in it.
Let’s observe an example:
// 0 1 2 3 4 5 6 7
// 5 3 8 2 6 1 4 6
// a b*
// a b*
// a b *>2 1 4 6
// b- a>8
// b a *>5 2 6
// a b [8 2 1], [8]
// i
- we can walk height from the end
- for each right border of a query we should find the closest height that is bigger than
a
andb
- so we should keep big numbers, pop all smaller
Some meta-thoughts: I have considered the monotonic stack/queue, but the solution requiers another leap of insight, the Binary Search. So, this is a two-level-deep insight problem.
Approach
- to have an intuition about what kind of monotonic stack needed, ask
what numbers are useful for the current situation, and what aren't?
Complexity
-
Time complexity: \(O(nlog(n))\)
-
Space complexity: \(O(n)\)
Code
fun leftmostBuildingQueries(heights: IntArray, queries: Array<IntArray>): IntArray {
val r = IntArray(queries.size); val q = ArrayList<Int>(); var j = heights.lastIndex
for (i in queries.indices.sortedBy { -queries[it].max() }) {
val (a, b) = (queries[i].min() to queries[i].max())
if (a == b || heights[a] < heights[b]) { r[i] = b; continue }
while (j > b) {
while (q.size > 0 && heights[q.last()] < heights[j]) q.removeLast()
q += j--
}
var lo = 0; var hi = q.lastIndex; r[i] = -1
while (lo <= hi) {
val m = lo + (hi - lo) / 2
if (heights[q[m]] > heights[a]) { r[i] = q[m]; lo = m + 1 }
else hi = m - 1
}
}
return r
}
pub fn leftmost_building_queries(heights: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
let (mut r, mut q, mut j) = (vec![-1; queries.len()], vec![], heights.len() - 1);
let mut qu: Vec<_> = (0..r.len()).map(|i| { let q = &queries[i]; (-q[0].max(q[1]), q[0].min(q[1]), i)}).collect();
qu.sort_unstable();
for (b, a, i) in qu {
let (a, b) = (a as usize, (-b) as usize);
if a == b || heights[a] < heights[b] { r[i] = b as i32; continue }
while j > b {
while q.last().map_or(false, |&l| heights[l] < heights[j]) { q.pop(); }
q.push(j); j -= 1;
}
let (mut lo, mut hi) = (0, q.len() - 1);
while lo <= hi && hi < q.len() {
let m = lo + (hi - lo) / 2;
if heights[q[m]] > heights[a] { r[i] = q[m] as i32; lo = m + 1 }
else { hi = m - 1 }
}
}; r
}
vector<int> leftmostBuildingQueries(vector<int>& hs, vector<vector<int>>& qs) {
vector<int> q, idx, r(qs.size()); int j = hs.size() - 1;
for (int i = 0; i < qs.size(); ++i) {
sort(begin(qs[i]), end(qs[i]));
if (qs[i][0] == qs[i][1] || hs[qs[i][0]] < hs[qs[i][1]]) r[i] = qs[i][1];
else idx.push_back(i);
}
sort(begin(idx), end(idx), [&](int i, int j) { return qs[i][1] > qs[j][1]; });
for (int i: idx) {
int a = qs[i][0], b = qs[i][1];
while (j > b) {
while (q.size() && hs[q.back()] <= hs[j]) q.pop_back();
q.push_back(j--);
}
auto it = upper_bound(rbegin(q), rend(q), a, [&](int i, int j) { return hs[i] < hs[j]; });
r[i] = it == rend(q) ? -1 : *it;
} return r;
}
21.12.2024
2872. Maximum Number of K-Divisible Components hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/839
Problem TLDR
Max connected components divisible by k
in graph #hard #toposort
Intuition
Can’t solve without hints.
The hints: walk from any node, merge values if sum is not divisible by k
.
If we go from each leaf up to the parent, we can compute the sum of this parent.
Approach
- we can walk with DFS
- we can walk with BFS, doing the Topological Sorting algorithm: decrease in-degrees, add in-degrees of
1
- we can use
values
as a sum results holder
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun maxKDivisibleComponents(n: Int, edges: Array<IntArray>, values: IntArray, k: Int): Int {
val g = Array(n) { ArrayList<Int>() }; for ((a, b) in edges) { g[a] += b; g[b] += a }
fun dfs(crr: Int, frm: Int): Int =
g[crr].sumOf { nxt ->
if (nxt == frm) 0 else dfs(nxt, crr).also { values[crr] += values[nxt] % k }
} + if (values[crr] % k > 0) 0 else 1
return dfs(0, 0)
}
pub fn max_k_divisible_components(n: i32, edges: Vec<Vec<i32>>, mut values: Vec<i32>, k: i32) -> i32 {
let (mut cnt, mut g, mut deg) = (0, vec![vec![]; n as usize], vec![0; n as usize]);
for e in edges { let (u, v) = (e[0] as usize, e[1] as usize);
deg[u] += 1; deg[v] += 1; g[u].push(v); g[v].push(u) }
let mut q = VecDeque::from_iter((0..n as usize).filter(|&u| deg[u] < 2));
while let Some(u) = q.pop_front() {
deg[u] -= 1; if values[u] % k == 0 { cnt += 1 }
for &v in &g[u] {
if deg[v] < 1 { continue }
deg[v] -= 1; values[v] += values[u] % k;
if deg[v] == 1 { q.push_back(v); }
}
}; cnt
}
int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
vector<vector<int>> g(n); vector<int> deg(n); int res = 0; queue<int> q;
for (auto e: edges) g[e[0]].push_back(e[1]), g[e[1]].push_back(e[0]);
for (int i = 0; i < n; ++i) if ((deg[i] = g[i].size()) < 2) q.push(i);
while (q.size()) {
int u = q.front(); q.pop(); --deg[u];
res += values[u] % k == 0;
for (int v: g[u]) if (deg[v]) {
values[v] += values[u] % k;
if (--deg[v] == 1) q.push(v);
}
} return res;
}
20.12.2024
2415. Reverse Odd Levels of Binary Tree medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/838
Problem TLDR
Odd-levels reversal in a perfect tree #medium #dfs #bfs #tree
Intuition
The most straightforward way is a level-order Breadth-First Search traversal. Remember the previous layer, adjust current values accordingly.
The more interesting way is how you can do it recursively:
- pass outer-left and outer-right values
a
andb
(and a depth) - pass inner-right and inner-left values as
a
andb
- swapping
a
andb
will result in the all level reversal (that’s an interesting fact that should be observed and discovered until understood)
Approach
- let’s implement both BFS and DFS
- remember to reverse only
odd
levels - rewrite the
values
instead of the pointers, much simpler code
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\) or O(log(n)) for recursion
Code
fun reverseOddLevels(root: TreeNode?): TreeNode? {
fun f(l: TreeNode?, r: TreeNode?, d: Int) {
l ?: return; r ?: return
if (d % 2 > 0) l.`val` = r.`val`.also { r.`val` = l.`val` }
f(l.left, r.right, d + 1)
f(l.right, r.left, d + 1)
}
f(root?.left, root?.right, 1)
return root
}
pub fn reverse_odd_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
let Some(r) = root.clone() else { return root }; let mut q = VecDeque::from([r]);
let (mut i, mut vs) = (0, vec![]);
while q.len() > 0 {
let mut l = vec![];
for _ in 0..q.len() {
let n = q.pop_front().unwrap(); let mut n = n.borrow_mut();
if i % 2 > 0 && vs.len() > 0 { n.val = vs.pop().unwrap(); }
if let Some(x) = n.left.clone() { l.push(x.borrow().val); q.push_back(x); }
if let Some(x) = n.right.clone() { l.push(x.borrow().val); q.push_back(x); }
}
vs = l; i += 1
}
root
}
TreeNode* reverseOddLevels(TreeNode* root) {
auto f = [](this auto const& f, TreeNode* l, TreeNode* r, int d) {
if (!l || !r) return; if (d % 2) swap(l->val, r->val);
f(l->left, r->right, d + 1); f(l->right, r->left, d + 1);
};
f(root->left, root->right, 1); return root;
}
19.12.2024
769. Max Chunks To Make Sorted medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/837
Problem TLDR
Maximum independent chunks to merge-sort array #medium
Intuition
Let’s observe when we can split the array:
// 0 1 2 3 4 5
// 1 3 4 0 2 5
// [ ][ ]
// 1 3 4 0 5 2
// [ ]
//
Some observations:
- all numbers before split border should be less than the current index
- we should move the border up to the maximum of the seen values
Approach
- let’s use
count
- the problem size of
10
items hint for some brute-force DFS where we try every possible split and do the sort, however it is not the simplest way of solving
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun maxChunksToSorted(arr: IntArray): Int {
var max = 0
return (0..<arr.size).count {
max = max(max, arr[it])
it == max
}
}
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
let mut m = 0;
(0..arr.len()).filter(|&i| {
m = m.max(arr[i]); i as i32 == m
}).count() as _
}
int maxChunksToSorted(vector<int>& arr) {
int r = 0;
for (int i = 0, m = 0; i < arr.size(); ++i) {
m = max(m, arr[i]); if (i == m) r++;
}
return r;
}
18.12.2024
1475. Final Prices With a Special Discount in a Shop easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/836
Problem TLDR
Subtract next smaller value #easy #monotonic_stack
Intuition
Brute force works. The next thing to try is a monotonic stack: iterate from the end, always keep values lower or equal than the current.
The big brain solution is to iterate forward: pop values lower than the current and adjust result at its index with the current value discount.
Approach
- let’s implement all of them
- we can do it in-place if needed
Complexity
-
Time complexity: \(O(n^2)\) or O(n)
-
Space complexity: \(O(n)\) or O(1) for brute-force in-place
Code
fun finalPrices(prices: IntArray) = IntArray(prices.size) { i ->
prices[i] - (prices.slice(i + 1..<prices.size)
.firstOrNull { it <= prices[i] } ?: 0)
}
pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
let (mut s, mut r) = (vec![], vec![0; prices.len()]);
for i in (0..prices.len()).rev() {
while s.last().map_or(false, |&x| x > prices[i]) { s.pop(); }
r[i] = prices[i] - s.last().unwrap_or(&0);
s.push(prices[i])
}; r
}
vector<int> finalPrices(vector<int>& p) {
vector<int> s;
for (int i = 0; i < p.size(); ++i) {
while (s.size() && p[s.back()] >= p[i]) {
p[s.back()] -= p[i]; s.pop_back();
}
s.push_back(i);
} return p;
}
17.12.2024
2182. Construct String With Repeat Limit medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/835
Problem TLDR
Max lexical ordered with repeat_limit
string #medium #bucket_sort
Intuition
Always peek the largest value. If limit is reached peek one of the next.
Approach
- we can use a heap, but have to manage all the next chars at once
- we can use a frequency counter and two pointers: current and next
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun repeatLimitedString(s: String, repeatLimit: Int) = buildString {
val f = IntArray(26); for (c in s) f[c - 'a']++
var cnt = 0; var i = 25; var j = i
while (i >= 0) {
if (f[i] == 0) { i--; continue }
if (length == 0 || get(length - 1) == 'a' + i) cnt++ else cnt = 1
if (cnt > repeatLimit) {
j = min(j, i - 1); while (j >= 0 && f[j] == 0) j--
if (j >= 0) { append('a' + j); f[j]-- } else break
} else { append('a' + i); f[i]-- }
}
}
pub fn repeat_limited_string(s: String, repeat_limit: i32) -> String {
let mut f = [0; 26]; for b in s.bytes() { f[(b - b'a') as usize] += 1 }
let (mut cnt, mut i, mut j, mut r) = (0, 25, 25, vec![]);
loop {
if f[i] == 0 { if i == 0 { break } else { i -= 1; continue }}
if r.last().map_or(true, |&l| l == b'a' + i as u8) { cnt += 1 } else { cnt = 1 }
if cnt > repeat_limit {
if i == 0 { break } else { j = j.min(i - 1) }
loop { if j == 0 || f[j] > 0 { break } else { j -= 1 }}
if f[j] > 0 { r.push(b'a' + j as u8); f[j] -= 1 } else { break }
} else { r.push(b'a' + i as u8); f[i] -= 1}
}; String::from_utf8(r).unwrap()
}
string repeatLimitedString(string s, int repeatLimit) {
int f[26]; for (auto c: s) ++f[c - 'a'];
int cnt = 0, i = 25, j = 25, l = 26; string r;
while (i >= 0) {
if (!f[i]) { --i; continue; }
l == i ? ++cnt : cnt = 1;
if (cnt > repeatLimit) {
j = min(j, i - 1);
while (j > 0 && !f[j]) --j;
if (j >= 0 && f[j]--) { r += 'a' + j; l = j; } else break;
} else { r += 'a' + i; --f[i]; l = i; }
} return r;
}
16.12.2024
3264. Final Array State After K Multiplication Operations I easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/834
Problem TLDR
Mutliply k
minimums #easy
Intuition
The problem size is small, the brute force works.
One improvement is to use a heap.
Approach
- will bucket sort work?
Complexity
-
Time complexity: \(O(n^2)\) or nlog(n)
-
Space complexity: \(O(1)\) or O(n)
Code
fun getFinalState(nums: IntArray, k: Int, multiplier: Int) = nums.apply {
for (i in 1..k) nums[indexOf(min())] *= multiplier
}
pub fn get_final_state(mut nums: Vec<i32>, k: i32, multiplier: i32) -> Vec<i32> {
let mut h = BinaryHeap::from_iter(nums.iter().enumerate().map(|(i, &x)| (-x, -(i as i32))));
for i in 0..k {
let (x, i) = h.pop().unwrap();
nums[(-i) as usize] *= multiplier;
h.push((x * multiplier, i));
}; nums
}
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
while (k--) {
int j = 0;
for (int i = 0; i < nums.size(); ++i) if (nums[i] < nums[j]) j = i;
nums[j] *= multiplier;
} return nums;
}
15.12.2024
1792. Maximum Average Pass Ratio medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/833
Problem TLDR
Arrange passed
students to improve average score #medium #heap
Intuition
Didn’t solve without a hint. The hint: choose the most significant difference that can be made.
Approach
- in Rust we can’t put
f64
into a heap, so convert into the bigi64
numbers
Complexity
-
Time complexity: \(O((n + m)log(n))\)
-
Space complexity: \(O(n)\)
Code
fun maxAverageRatio(classes: Array<IntArray>, extraStudents: Int): Double {
val scores = PriorityQueue<IntArray>(compareBy({
it[0].toDouble() / it[1] - (it[0] + 1).toDouble() / (it[1] + 1) }))
scores += classes
for (s in 1..extraStudents)
scores += scores.poll().also { it[0]++; it[1]++ }
return scores.sumOf { it[0].toDouble() / it[1] } / classes.size
}
pub fn max_average_ratio(classes: Vec<Vec<i32>>, extra_students: i32) -> f64 {
let d = |p: i64, t: i64| -> (i64, i64, i64) {
(((t - p) * 10_000_000) / (t * t + t), p, t) };
let mut h = BinaryHeap::from_iter(classes.iter().map(|c| {
d(c[0] as i64, c[1] as i64) }));
for _ in 0..extra_students {
let (_, p, t) = h.pop().unwrap(); h.push(d(p + 1, t + 1)) }
h.iter().map(|&(d, p, t)|
p as f64 / t as f64).sum::<f64>() / classes.len() as f64
}
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
auto f = [&](double p, double t) { return (p + 1) / (t + 1) - p / t; };
double r = 0; priority_queue<tuple<double, int, int>> q;
for (auto x: classes) r += (double) x[0] / x[1],
q.push({f(x[0], x[1]), x[0], x[1]});
while (extraStudents--) {
auto [d, p, t] = q.top(); q.pop();
r += d; q.push({f(p + 1, t + 1), p + 1, t + 1});
}
return r / classes.size();
}
14.12.2024
2762. Continuous Subarrays medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/832
Problem TLDR
Count subarrays with difference <= 2 #medium #monotonic_queue #tree_set
Intuition
Observe the example, let’s use two pointers sliding window:
// 5 4 2 4 min max iq dq
// i 5 5 5 5
// j
// i 4 5 4 5 4
// i 2 5 2 5 4 2 shrink
// j 2 4 2 4 2 new max
After we shrink the window by moving j
, we should update min
and max
of the window. To keep all potential next maximums and minimums we can use a monotonic queue technique: remove all non-increasing/non-decreasing values.
Another approach is to use a TreeSet: it naturally would give us updated min
and max
.
Approach
- if we drop the duplicates, the max queue size would be 4
- to use Kotlin’s TreeSet, we should also preserve duplicates by storing the indices
Complexity
-
Time complexity: \(O(n)\) or O(nlog(n))
-
Space complexity: \(O(1)\) or O(n)
Code
fun continuousSubarrays(nums: IntArray): Long {
val s = TreeSet<Pair<Int, Int>>(compareBy({it.first}, {it.second}))
var j = 0
return nums.withIndex().sumOf { (i, n) ->
s += n to i
while (s.last().first - s.first().first > 2) s -= nums[j] to j++
1L + i - j
}
}
pub fn continuous_subarrays(nums: Vec<i32>) -> i64 {
let (mut iq, mut dq, mut j) = (VecDeque::new(), VecDeque::new(), 0);
nums.iter().enumerate().map(|(i, &n)| {
while iq.back().map_or(false, |&b| nums[b] >= n) { iq.pop_back(); }
while dq.back().map_or(false, |&b| nums[b] <= n) { dq.pop_back(); }
iq.push_back(i); dq.push_back(i);
while n - nums[*iq.front().unwrap()] > 2 { j = iq.pop_front().unwrap() + 1 }
while nums[*dq.front().unwrap()] - n > 2 { j = dq.pop_front().unwrap() + 1 }
1 + i as i64 - j as i64
}).sum()
}
long long continuousSubarrays(vector<int>& n) {
long long r = 0; multiset<int> s;
for (int i = 0, j = 0; i < n.size(); ++i) {
s.insert(n[i]);
while (s.size() && *s.rbegin() - *s.begin() > 2)
s.erase(s.find(n[j++]));
r += i - j + 1;
}; return r;
}
13.12.2024
2593. Find Score of an Array After Marking All Elements medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/831
Problem TLDR
Sum of minimums in order excluding siblings #medium #monotonic_stack
Intuition
The straightforward way is to sort and take one-by-one, marking taken elements.
The more interesting approach: for each decreasing sequence, we will take every 2nd starting from the smallest.
We can do this with a Stack, or even more simply with alterating sums.
Approach
- let’s try to implement all approaches
- if you look at the code and it looks simple, know it was paid off with pain
Complexity
-
Time complexity: \(O(nlog(n))\) or O(n)
-
Space complexity: \(O(n)\) or O(1)
Code
fun findScore(nums: IntArray): Long {
var res = 0L; var s = Stack<Int>()
for (n in nums + Int.MAX_VALUE)
if (s.size > 0 && s.peek() <= n)
while (s.size > 0) {
res += s.pop()
if (s.size > 0) s.pop()
}
else s += n
return res
}
pub fn find_score(nums: Vec<i32>) -> i64 {
let (mut r, mut a, mut b, mut l) = (0, 0, 0, i64::MAX);
for n in nums {
let n = n as i64;
if l <= n {
r += b; a = 0; b = 0; l = i64::MAX
} else {
(a, b) = (b, a + n); l = n
}
}; r + b
}
long long findScore(vector<int>& n) {
long long r = 0; int e = n.size() - 1;
vector<int> idx(n.size());
iota(begin(idx), end(idx), 0);
stable_sort(begin(idx), end(idx), [&](int i, int j) { return n[i] < n[j];});
for (int i: idx) if (n[i])
r += n[i], n[i] = n[min(e, i + 1)] = n[max(0, i - 1)] = 0;
return r;
}
12.12.2024
2558. Take Gifts From the Richest Pile medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/830
Problem TLDR
Sum after k-Sqrt
of tops in array #easy
Intuition
We can use a heap.
Approach
- some extra attention should be paid to use an sqrt: in Kotiln & Rust convert to Double, in Rust we aren’t able to sort Doubles, so convert back.
- c++ is much more forgiving
Complexity
-
Time complexity: \(O(nlog(n))\)
-
Space complexity: \(O(n)\)
Code
fun pickGifts(gifts: IntArray, k: Int): Long {
val pq = PriorityQueue(gifts.map { -it.toDouble() })
for (i in 1..k) pq += -floor(sqrt(-pq.poll()))
return -pq.sum().toLong()
}
pub fn pick_gifts(gifts: Vec<i32>, k: i32) -> i64 {
let mut bh = BinaryHeap::from_iter(gifts);
for i in 0..k {
let x = bh.pop().unwrap();
bh.push(((x as f64).sqrt()).floor() as i32)
}
bh.iter().map(|&x| x as i64).sum()
}
long long pickGifts(vector<int>& gifts, int k) {
priority_queue<int> pq; long long res = 0;
for (int g: gifts) pq.push(g);
while (k--) {
int x = pq.top(); pq.pop();
pq.push(sqrt(x));
}
while (pq.size()) res += pq.top(), pq.pop();
return res;
}
11.12.2024
2779. Maximum Beauty of an Array After Applying Operation medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/829
Problem TLDR
Max equal nums after adjusting to [-k..+k] #medium #binary_search #line_sweep
Intuition
Let’s observe the data:
// 4 6 1 2 k=2
// 2 4-1 0
// 3 5 0 1
// 4 6 1 2
// 5 7 2 3
// 6 8 3 4
//[2..6] [6..8] [-1..3] [0..4]
// -1 0 1 2 3 4 5 6 7 8
// s * e
// s * * e
// s * e
// s e
// 1 2 3 3 2 2 1
// -16 17 42 75 100
// [ ]
// [ ]
// [ ]
// s s e e e
// s
We can notice, each number is actually an interval of [n-k..n+k]
. The task is to find maximum interval intersections.
This can be done in a several ways, one is to convert starts and ends, sort them, then do a line sweep with counter.
Another way is to search end index of n + 2 * k
, we can do this with a binary search.
Approach
- we also can do a bucket sort for a line sweep, but careful with a zero point
Complexity
-
Time complexity: \(O(nlog(n))\) or O(n)
-
Space complexity: \(O(n)\) or O(1)
Code
fun maximumBeauty(nums: IntArray, k: Int): Int {
val se = mutableListOf<Pair<Int, Int>>()
for (n in nums) { se += (n + k) to 1; se += (n - k) to -1 }
se.sortWith(compareBy({ it.first }, { it.second }))
var cnt = 0
return se.maxOf { cnt -= it.second; cnt }
}
pub fn maximum_beauty(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort_unstable();
(0..nums.len()).map(|i| {
let (mut lo, mut hi) = (i + 1, nums.len() - 1);
while lo <= hi {
let m = (lo + hi) / 2;
if nums[m] > nums[i] + k + k
{ hi = m - 1 } else { lo = m + 1 }
}; lo - i
}).max().unwrap() as i32
}
int maximumBeauty(vector<int>& nums, int k) {
int d[300002] { 0 }; int res = 1;
for (int n: nums) ++d[n-k+100000], --d[n+k+100001];
for (int i = 0, c = 0; i < 300002; ++i)
res = max(res, c += d[i]);
return res;
}
10.12.2024
2981. Find Longest Special Substring That Occurs Thrice I medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/828
Problem TLDR
Max same-char 3-windows length #medium #sliding_window
Intuition
Problem size is small, brute force works: try every length, do a sliding window.
Slightly better is to do a binary search of window length.
The clever solution is to precompute window frequencies and then check every length:
`aaaa` -> 'a' -> 1, 'aa' -> 1, 'aaa' -> 1, 'aaaa' -> 1
len: 4 -> 1, 3 -> f(4) + 1 = 2, 2 -> f(3) + 1 = 3 (take)
Approach
- try every approach
Complexity
-
Time complexity: \(O(n^2)\) -> O(nlog(n)) -> O(n)
-
Space complexity: \(O(n)\) -> O(1)
Code
fun maximumLength(s: String) =
(s.length - 2 downTo 1).firstOrNull { len ->
val f = IntArray(128)
s.windowed(len).any { w -> w.all { it == w[0] } && ++f[w[0].code] > 2 }
} ?: -1
pub fn maximum_length(s: String) -> i32 {
let (mut lo, mut hi, b, mut r) = (1, s.len() - 2, s.as_bytes(), -1);
while lo <= hi {
let m = lo + (hi - lo) / 2; let mut f = vec![0; 26];
if b[..].windows(m).any(|w|
w.iter().all(|&x| x == w[0]) && {
f[(w[0] - b'a') as usize] += 1; f[(w[0] - b'a') as usize] > 2
}) { r = r.max(m as i32); lo = m + 1 } else { hi = m - 1 }
}; r
}
int maximumLength(string s) {
vector<vector<int>> f(26, vector<int>(s.size() + 1, 0));
char p = '.'; int cnt = 0, res = -1;
for (auto c: s) f[c - 'a'][c == p ? ++cnt : (cnt = 1)]++, p = c;
for (int c = 0; c < 26; ++c)
for (int l = s.size(), p = 0; l; --l)
if ((p += f[c][l]) > 2) { res = max(res, l); break; }
return res;
}
09.12.2024
3152. Special Array II medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/827
Problem TLDR
Queries is all adjucents parity differ [i..j] #medium #two_pointers
Intuition
Let’s observe the data and build an intuition:
// 1 1 2 3 4 4 5 6 6 7 7
// 0 1 1 1 0 1 1 0 1 0
// j i
// j i
// [0]
// [ 0 ]
// [ 0 ]
// [1] >= j = 1
// [ 1 ] >= j = 1
// [ 0 ] < j = 0
// [ ]
// [ ]
// [ ]
// [ ]
// [ ]
// [ ]
The interesting observations:
- we can build a parity-diff array
- for each
end
index, thestart
index should be in the same island of1
-ones in parity diff array
We can move two pointers, one for end
border, second j
for the start of the 1-island
. All queries inside it would have start >= j
.
Another, superior tactic is to enumerate all islands, giving them uniq index or key, and then just check if both start
and end
have the same key
.
Approach
- two-pointer is more familar for those who solve too many leetcodes, but if you take a pause and think one step more you could spot the island-indexing tactic
Complexity
-
Time complexity: \(O(nlog(n))\), or O(n)
-
Space complexity: \(O(n)\)
Code
fun isArraySpecial(nums: IntArray, queries: Array<IntArray>): BooleanArray {
val g = IntArray(nums.size)
for (i in 1..<nums.size) g[i] = g[i - 1] + 1 - abs(nums[i] - nums[i - 1]) % 2
return BooleanArray(queries.size) { g[queries[it][0]] == g[queries[it][1]] }
}
fun isArraySpecial(nums: IntArray, queries: Array<IntArray>): BooleanArray {
val inds = queries.indices.sortedBy { queries[it][1] }
var j = 0; var k = 0; val res = BooleanArray(queries.size)
for (i in nums.indices) {
if (i > 0 && nums[i] % 2 == nums[i - 1] % 2) j = i
while (k < queries.size && queries[inds[k]][1] <= i)
res[inds[k]] = queries[inds[k++]][0] >= j
}
return res
}
pub fn is_array_special(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<bool> {
let mut g = vec![0i32; nums.len()];
for i in 1..nums.len() { g[i] = g[i - 1] + 1 - (nums[i] - nums[i - 1]).abs() % 2 }
queries.iter().map(|q| g[q[0] as usize] == g[q[1] as usize]).collect()
}
vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& q) {
vector<int> g(nums.size()); vector<bool> r(q.size());
for (int i = 1; i < nums.size(); ++i)
g[i] = g[i - 1] + 1 - abs(nums[i] - nums[i - 1]) % 2;
for (int i = 0; i < q.size(); ++i)
r[i] = g[q[i][0]] == g[q[i][1]];
return r;
}
08.12.2024
2054. Two Best Non-Overlapping Events medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/826
Problem TLDR
Max two non-overlapping intervals #medium #binary_search
Intuition
Let’s observe some rich example and try to invent an algorithm:
// 0123456789111
// . 012
// [.......7...]
// [.3][.2] .
// [.5][.3] .
// [.4][.4] .
// [.2][.6].
// .[.1][.7]
// .. . .
// t. . . t=3, v=3 maxV=3 maxT=3
// t . . t=4, v=5,maxV=5 maxT=4
// .t . . t=5, v=4,
// . t. . t=6, v=2
// . t . t=7, v=2
// . t . t=7, v=1
// . .t . t=8, v=3
// . . t . t=9, v=4
// . . t. t=10,v=6, maxV=6, maxT=10
// . . .t t=11,v=7, maxV=7, maxT=11
// . . . t t=12,v=7
// 3555555677 maxV
// *f t 5+7
Some observations:
- for current interval we should find the maximum before it
- we can store the maximums as we go
- we should sort events by the
end
times
Another two approaches:
- use a Heap, sort by start, pop from heap all non-intersecting previous and peek a max
- line sweep: put starts and ends in a timeline, sort by time, compute
max
after ends, andres
on start
Approach
- binary search approach have many subtle tricks: add (0, 0) as zero, sort also by bigger values first to make binary search work
Complexity
-
Time complexity: \(O(nlog(n))\)
-
Space complexity: \(O(n)\)
Code
fun maxTwoEvents(events: Array<IntArray>): Int {
val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
var res = 0; var max = 0;
for ((f, t, v) in events.sortedBy { it[0] }) {
while (pq.size > 0 && pq.peek().first < f)
max = max(max, pq.poll().second)
res = max(res, max + v)
pq += t to v
}
return res
}
pub fn max_two_events(mut events: Vec<Vec<i32>>) -> i32 {
let (mut res, mut m) = (0, vec![(0, 0)]);
events.sort_unstable_by_key(|e| (e[1], -e[2]));
for e in events {
let i = m.partition_point(|x| x.1 < e[0]) - 1;
m.push((m.last().unwrap().0.max(e[2]), e[1]));
res = res.max(m[i].0 + e[2]);
}; res
}
int maxTwoEvents(vector<vector<int>>& events) {
vector<tuple<int, int, int>> t; int res = 0, m = 0;
for (auto e: events)
t.push_back({e[0], 1, e[2]}),
t.push_back({e[1] + 1, 0, e[2]});
sort(begin(t), end(t));
for (auto [x, start, v]: t)
start ? res = max(res, m + v) : m = max(m, v);
return res;
}
07.12.2024
1760. Minimum Limit of Balls in a Bag medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/825
Problem TLDR
Max number after at most maxOperations
of splitting #medium #binary_search
Intuition
Let’s observe the problem:
// 9 -> 1 8 -> 1 1 7
// 2 7 2 2 5
// 3 6 3 3 3 ?? math puzzle
// 4 5 4 2 3 ??
// 9 / 2 / 2
// 9/3 -> 3 3 3
// 12/3 -> 3 3 3 3 = 3 (3 (3 3))
// 6/3 -> 3 3
// 7/3 -> 3 (3 1)
// 5/3 -> 3 2
First (naive) intuition is to try to greedily take the largest number and split it evenly. However, it will not work for the test case 9, maxOps = 2
, which produces 4 2 3
instead of 3 3 3
, giving not optimal result of 4
.
(this is a place where I gave up and used the hint)
The hint is: binary search.
But how can I myself deduce binary search at this point? Some thoughts:
- problem size: 10^5 numbers, 10^9 max number -> must be linear or nlog(n) at most (but using the problem size is not always an option)
- the task is to maximize/minimize something when there is a constraint like
at most
/at least
-> maybe it is a function of the constraint and can be searched by it
Approach
- pay attention to the values
low
andhigh
of the binary search
Complexity
-
Time complexity: \(O(nlog(n))\)
-
Space complexity: \(O(1)\)
Code
fun minimumSize(nums: IntArray, maxOperations: Int): Int {
var l = 1; var h = nums.max()
while (l <= h) {
val m = (l + h) / 2
val ops = nums.sumOf { (it - 1) / m }
if (ops > maxOperations) l = m + 1 else h = m - 1
}
return l
}
pub fn minimum_size(nums: Vec<i32>, max_operations: i32) -> i32 {
let (mut l, mut h) = (1, 1e9 as i32);
while l <= h {
let m = (l + h) / 2;
let o: i32 = nums.iter().map(|&x| (x - 1) / m).sum();
if o > max_operations { l = m + 1 } else { h = m - 1 }
}; l
}
int minimumSize(vector<int>& nums, int maxOperations) {
int l = 1, h = 1e9;
while (l <= h) {
int m = (l + h) / 2, o = 0;
for (int x: nums) o += (x - 1) / m;
o > maxOperations ? l = m + 1 : h = m - 1;
} return l;
}
06.12.2024
2554. Maximum Number of Integers to Choose From a Range I medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/824
Problem TLDR
Sum 1..n
excluding banned
until maxSum
#medium
Intuition
- we can use a HashSet
- we can sort and do two pointers
- we can precompute all sums and do a binary search
Approach
- careful with duplicates in the sort solution
Complexity
-
Time complexity: \(O(n)\) or O(nlog(n))
-
Space complexity: \(O(n)\) or O(1)
Code
fun maxCount(banned: IntArray, n: Int, maxSum: Int): Int {
val set = banned.toSet(); var s = 0; var cnt = 0
for (x in 1..n) if (x !in set) {
s += x; if (s > maxSum) break; cnt++
}
return cnt
}
pub fn max_count(mut banned: Vec<i32>, n: i32, max_sum: i32) -> i32 {
banned.sort_unstable(); let (mut j, mut s, mut cnt) = (0, 0, 0);
for x in 1..=n {
if j < banned.len() && x == banned[j] {
while j < banned.len() && x == banned[j] { j += 1 }
k
}; cnt
}
int maxCount(vector<int>& banned, int n, int maxSum) {
int cnt = 0, s = 0; int b[10001] = {};
for (int x: banned) b[x] = 1;
for (int x = 1; x <= n && s + x <= maxSum; ++x)
cnt += 1 - b[x], s += x * (1 - b[x]);
return cnt;
}
05.12.2024
2337. Move Pieces to Obtain a String medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/823
Problem TLDR
Move L
left and R
right to match strings #medium
Intuition
Let’s move both pointers together and calculate the balance of L
, R
and _
:
// R_R___L __RRL__ R b L
// j // jk
// j . i . +1-1=1
// j . i . +1-1=1
// j . i . -1=0 +1=2
// j. i. +1=3 -1 (check R==0)
// j i +1-1=3
// j i -1=2 +1=0
Some observations:
- the final balance should be
0
- we should eliminate the impossible scenarios (that’s where the hardness of this task begins)
- to simplify the corner cases let’s split this into pass forward and pass backwards (then we have ugly long solution but its werks)
Now, the more clever way of solving ignore the spaces _
and only check the balance of l
and r
be not negative. The corner case would be LR
-> RL
and for this check we don’t have l > 0
and r > 0
together.
Another, much simpler way of thinking: move separate pointers instead of a single, and skip the spaces _
, then compare:
s[i] == t[j]
letters should match- some indexes rules: from
start
R
goes forwardi <= j
,L
goes backwardi >= j
Approach
- slow down and think one step at a time
- the good idea of separate pointers eliminates all corner cases (so think broader in a space of ideas before thinking in a space of implementations)
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun canChange(start: String, target: String): Boolean {
var l = 0; var r = 0
for ((i, s) in start.withIndex()) {
val t = target[i]
if (s == 'R') r++
if (t == 'L') l++
if (l * r > 0) return false
kk
if (s == 'L' && --l < 0) return false
k
return l == 0 && r == 0
}
pub fn can_change(start: String, target: String) -> bool {
let (mut i, mut j, s, t, n) =
(0, 0, start.as_bytes(), target.as_bytes(), start.len());
while i < n || j < n {
while i < n && s[i] == b'_' { i += 1 }
while j < n && t[j] == b'_' { j += 1 }
if i == n || j == n || s[i] != t[j] ||
s[i] == b'L' && i < j || s[i] == b'R' && i > j { break }
i += 1; j += 1
}; i == n && j == n
}
bool canChange(string s, string t) {
int l = 0, r = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'R') r++;
if (t[i] == 'L') l++;
if (l * r > 0) return 0;
if (t[i] == 'R' && --r < 0) return 0;
if (s[i] == 'L' && --l < 0) return 0;
}
return l == 0 && r == 0;
}
04.12.2024
2825. Make String a Subsequence Using Cyclic Increments medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/822
Problem TLDR
Increase some chars once to make a subsequence #medium
Intuition
Attention to the description:
- subsequence vs substring
- rotation at most once
- any positions
Let’s scan over str2
(resulting subsequence) and greedily find positions in str1
for each of its letters. Compare the char and its rolled down
version.
Approach
- trick from Lee:
(s2[i] - s1[j]) <= 1
(with % 26 added for ‘a’-‘z’ case)
Complexity
-
Time complexity: \(O(n + m)\)
-
Space complexity: \(O(1)\)
Code
fun canMakeSubsequence(str1: String, str2: String): Boolean {
var j = 0; var i = 0
while (i < str2.length && j < str1.length)
if ((str2[i] - str1[j] + 26) % 26 <= 1) { ++i; ++j } else ++j
return i == str2.length
}
pub fn can_make_subsequence(str1: String, str2: String) -> bool {
k
while i < s2.len() && j < s1.len() {
if (s2[i] - s1[j] + 26) % 26 <= 1 { i += 1; j += 1 } else { j += 1 }
}; i == s2.len()
}
bool canMakeSubsequence(string s1, string s2) {
int i = 0;
for (int j = 0; j < s1.size() && i < s2.size(); ++j)
if ((s2[i] - s1[j] + 26) % 26 <= 1) ++i;
return i == s2.size();
}
03.12.2024
2109. Adding Spaces to a String medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/821
Problem TLDR
Insert spaces into string #medium
Intuition
Iterate over string and adjust second pointer for spaces or iterate over spaces and insert substrings.
Approach
- Kotlin has a
slice
for strings - Rust strings can append
&[..]
slices
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun addSpaces(s: String, spaces: IntArray) = buildString {
for ((j, i) in spaces.withIndex())
k
append(s.drop(spaces.last()))
}
pub fn add_spaces(s: String, spaces: Vec<i32>) -> String {
let mut r = String::new();
for (i, &j) in spaces.iter().enumerate() {
r += &s[r.len() - i..j as usize]; r += " "
}; r += &s[*spaces.last().unwrap() as usize..]; r
}
string addSpaces(string s, vector<int>& spaces) {
string r;
for (int i = 0, j = 0; i < s.size(); ++i)
j < spaces.size() && i == spaces[j]
? j++, r += " ", r += s[i] : r += s[i];
return r;
}
02.12.2024
1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/819
Problem TLDR
Position of the prefix #easy
Intuition
The O(n) time and O(1) memory solution is possible (see c++).
Approach
- we can prepend a word to shorten the index adjusting logic
- c++ will shoot in your foot for comparing
-1
with.size()
- rust has a nice
.map_or
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\) or O(1)
Code
fun isPrefixOfWord(sentence: String, searchWord: String) =
.indexOfFirst { it.startsWith(searchWord) }
pub fn is_prefix_of_word(sentence: String, search_word: String) -> i32 {
sentence.split_whitespace().position(|w| w.starts_with(&search_word))
.map_or(-1, |i| 1 + i as i32)
}
int isPrefixOfWord(string s, string w) {
int p = 1, j = 0, n = w.size();
for (int i = 0; i < s.size() && j < n; ++i)
s[i] == ' ' ? j = 0, ++p :
j >= 0 && s[i] == w[j] ? ++j : j = -1;
return j < n ? -1 : p;
}
01.12.2024
1346. Check If N and Its Double Exist easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/818
Problem TLDR
Any i != j && a[i] = 2 * a[j]
#easy
Intuition
Several ways:
- brute-force O(n^2) and O(1) memory
- HashSet / bitset O(n) and O(n) memory
- sort & binary search O(nlogn) and O(logn) memory
- bucket sort O(n) and O(n) memory
Approach
- corner case is
0
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun checkIfExist(arr: IntArray) = arr.groupBy { it }
.run { keys.any { it != 0 && it * 2 in keys }
|| get(0)?.size ?: 0 > 1 }
pub fn check_if_exist(mut arr: Vec<i32>) -> bool {
arr.sort_unstable(); (0..arr.len()).any(|i| {
i != arr.binary_search(&(2 * arr[i])).unwrap_or(i) })
}
bool checkIfExist(vector<int>& a) {
int l = 1e3, f[2001] = {}; for (int x: a) ++f[x + l];
for (int x = 500; --x;)
if (f[l + x] && f[l + x * 2] || f[l - x] && f[l - x * 2])
return 1;
return f[l] > 1 ? 1 : 0;
}
bool checkIfExist(vector<int>& a) {
int l = 2000; bitset<4001>b;
for (int x: a) if (b[x * 2 + l] || x % 2 < 1 && b[x / 2 + l])
return 1; else b[x + l] = 1;
return 0;
}
30.11.2024
2097. Valid Arrangement of Pairs hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/816
Problem TLDR
Hierholzer algorithm #hard #graph
Intuition
I doubt this can be invented on the fly, so this task is all about one algorithm that we have to know: Hierhoizer.
First, find the node that have more outgoing edges then incoming.
Next, greedily traverse all siblings in a DFS manner, removing the explored edges. Do this without backtracking. Store visited nodes in a path
.
When all the reached nodes have no more siblings, we reached the end, so pop
it from the path
.
While doing the pop
operation we can discover some previously undiscovered loops in the same manner.
Approach
- let’s try to learn something new
Complexity
-
Time complexity: \(O(EV)\)
-
Space complexity: \(O(E + V)\)
Code
fun validArrangement(pairs: Array<IntArray>): Array<IntArray> {
val m = mutableMapOf<Int, MutableList<Int>>()
val f = mutableMapOf<Int, Int>()
for ((a, b) in pairs) {
m.getOrPut(a) { mutableListOf() } += b
f[a] = 1 + (f[a] ?: 0)
f[b] = -1 + (f[b] ?: 0)
}
val first = f.keys.firstOrNull { f[it]!! > 0 } ?: pairs[0][0]
val stack = mutableListOf(first, -1); var prev = -1
return Array(pairs.size) { i ->
do {
prev = stack.removeLast()
while ((m[stack.last()]?.size ?: 0) > 0)
stack += m[stack.last()]!!.removeLast()
} while (prev < 0)
intArrayOf(stack.last(), prev)
}.apply { reverse() }
}
pub fn valid_arrangement(pairs: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let (mut m, mut f) = (HashMap::new(), HashMap::new());
for p in &pairs {
m.entry(p[0]).or_insert_with(Vec::new).push(p[1]);
*f.entry(p[0]).or_insert(0) += 1;
*f.entry(p[1]).or_insert(0) -= 1;
}
let first = f.iter().find(|&(_, &v)| v > 0).map(|(k, _)| *k)
.unwrap_or_else(|| pairs[0][0]);
let mut stack = vec![first, -1]; let mut prev = -1;
let mut res = (0..pairs.len()).map(|i| {
loop {
prev = stack.pop().unwrap();
while let Some(sibl) = m.get_mut(stack.last().unwrap())
{ let Some(s) = sibl.pop() else { break }; stack.push(s) }
if (prev >= 0) { break }
}
vec![*stack.last().unwrap(), prev]
}).collect::<Vec<_>>(); res.reverse(); res
}
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
unordered_map<int, vector<int>> m; unordered_map<int, int> f;
for (auto &p: pairs) {
m[p[0]].push_back(p[1]), ++f[p[0]], --f[p[1]];
}
int first = pairs[0][0]; for (auto [k, v]: f) if (v > 0) first = k;
vector<int> path, s{first}; vector<vector<int>> res;
while (s.size()) {
while (m[s.back()].size()) {
int n = s.back(); s.push_back(m[n].back()); m[n].pop_back();
}
path.push_back(s.back()); s.pop_back();
}
for (int i = path.size() - 1; i; --i) res.push_back({path[i], path[i - 1]});
return res;
}
29.11.2024
2577. Minimum Time to Visit a Cell In a Grid hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/815
Problem TLDR
Min time start-end 4-d travel in 2D matrix with waiting #hard #dijkstra
Intuition
Start with simple BFS.
We can wait
by moving back and forward incrementing time by 2
.
If we put k
Approach
- we can use a simple boolean visited set instead of comparing the time, as we always reach the earliest time first
Complexity
-
Time complexity: \((nmlog(nm))\)
-
Space complexity: \(mn\)
Code
fun minimumTime(grid: Array<IntArray>): Int {
if (grid[0][1] > 1 && grid[1][0] > 1) return -1
val q = PriorityQueue<List<Int>>(compareBy { it[2] }); q += listOf(0, 0, 0)
val visited = Array(grid.size) { BooleanArray(grid[0].size)}
while (q.size > 0) {
val (y, x, t) = q.poll()
if (y == grid.size - 1 && x == grid[0].size - 1) return t
if (visited[y][x]) continue; visited[y][x] = true
for ((y1, x1) in listOf(y - 1 to x, y to x + 1, y + 1 to x, y to x - 1))
if (y1 in grid.indices && x1 in grid[0].indices && !visited[y1][x1])
q += listOf(y1, x1, 1 + max(grid[y1][x1] - max(0, grid[y1][x1] - t) % 2, t))
}; return -1
}
pub fn minimum_time(grid: Vec<Vec<i32>>) -> i32 {
if grid[0][1] > 1 && grid[1][0] > 1 { return -1 }
let mut h = BinaryHeap::from_iter([(0, 1, 1)]);
let mut time = vec![vec![i32::MAX; grid[0].len()]; grid.len()];
while let Some((t, y, x)) = h.pop() {
for (y1, x1) in [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)] {
if y1.min(x1) < 1 || y1 > grid.len() || x1 > grid[0].len() { continue }
let t = (-t + 1).max(grid[y1 - 1][x1 - 1] + (grid[y1 - 1][x1 - 1] + t + 1) % 2);
if t < time[y1 - 1][x1 - 1] { time[y1 - 1][x1 - 1] = t; h.push((-t, y1, x1)); }
}
}; time[grid.len() - 1][grid[0].len() - 1]
}
int minimumTime(vector<vector<int>>& g) {
if (min(g[0][1], g[1][0]) > 1) return -1;
priority_queue<array<int, 3>> pq; pq.push({0, 0, 0});
vector<vector<int>> time(g.size(), vector<int>(g[0].size(), INT_MAX));
while (pq.size()) {
auto [t, y, x] = pq.top(); pq.pop();
for (auto [y1, x1] : array<int[2],4>..{y - 1, x}, {y + 1, x}, {y, x - 1}, {y, x + 1\}..) { // replace '.' to '{'
if (min(y1, x1) < 0 || y1 >= g.size() || x1 >= g[0].size()) continue;
int t1 = max(-t + 1, g[y1][x1] + (g[y1][x1] + t + 1) % 2);
if (t1 >= time[y1][x1]) continue;
time[y1][x1] = t1; pq.push({-t1, y1, x1});
}
} return time.back().back();
}
28.11.2024
2290. Minimum Obstacle Removal to Reach Corner hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/814
Problem TLDR
Min removals to travel first-last in 2D grid #hard #bfs #dijkstra
Intuition
We are interested in the shortest path through obstacles, so the go-to algorithm is the BFS, then we optimize it with Dijkstra by moving only improved paths.
This simple optimization is not enough, however. So, we have another one - use a PriorityQueue to peek the smallest obstacles paths first.
And another cool trick: the are only two types of paths to sort - completely free and ones with obstacles. Free paths must go first. We completely drop the PriorityQueue and just add to the front or to the back. (this is a 0-1 BFS https://codeforces.com/blog/entry/22276)
Approach
- some other small optimizations are possible: we can stop searching at the first arrival to the end
- we can use a two Queues instead of one
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(nm)\)
Code
fun minimumObstacles(grid: Array<IntArray>): Int {
val obs = Array(grid.size) { IntArray(grid[0].size) { Int.MAX_VALUE }}
val q = ArrayDeque<List<Int>>(listOf(listOf(0, 0, 0)))
while (q.size > 0) {
val (y, x, o) = q.removeFirst()
if (y !in 0..<grid.size || x !in 0..<grid[0].size) continue
val n = grid[y][x] + o
if (n < obs[y][x]) {
obs[y][x] = n
for (s in listOf(y - 1, x, n, y, x + 1, n, y + 1, x, n, y, x - 1, n)
.chunked(3)) if (grid[y][x] > 0) q += s else q.addFirst(s)
}
}
return obs[grid.size - 1][grid[0].size - 1]
}
pub fn minimum_obstacles(grid: Vec<Vec<i32>>) -> i32 {
let mut obs = vec![vec![i32::MAX; grid[0].len()]; grid.len()];
let mut q = VecDeque::from_iter([(1, 1, 0)]);
while let Some((y, x, o)) = q.pop_front() {
if y < 1 || y > grid.len() || x < 1 || x > grid[0].len() { continue }
let n = grid[y - 1][x - 1] + o;
if n < obs[y - 1][x - 1] {
obs[y - 1][x - 1] = n;
for s in [(y - 1, x, n), (y + 1, x, n), (y, x - 1, n), (y, x + 1, n)] {
if grid[y - 1][x - 1] > 0 { q.push_back(s); } else { q.push_front(s); }
}
}
}; obs[grid.len() - 1][grid[0].len() - 1]
}
int minimumObstacles(vector<vector<int>>& g) {
int m = g.size(), n = g[0].size();
vector<vector<int>> obs(m, vector<int>(n, INT_MAX));
deque<tuple<int, int, int>> q; q.emplace_back(0, 0, 0);
vector<pair<int, int>>dxy..-1, 0}, {0, 1}, {1, 0}, {0, -1..; // replace . to {
while (q.size()) {
auto [y, x, o] = q.front(); q.pop_front();
for (auto [dy, dx]: dxy) {
int ny = y + dy, nx = x + dx;
if (ny < 0 || ny >= m || nx < 0 || nx >= n || g[ny][nx] + o >= obs[ny][nx]) continue;
int n = g[ny][nx] + o; obs[ny][nx] = n;
if (g[ny][nx] > 0) q.emplace_back(ny, nx, n); else q.emplace_front(ny, nx, n);
}
} return obs[m - 1][n - 1];
}
27.11.2024
3243. Shortest Distance After Road Addition Queries I medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/813
Problem TLDR
Query shortest paths after adding new edges #medium #bfs
Intuition
Unidirectional - one way. (spent 10 minutes on this)
The problem size is small, the simple BFS for each query is accepted.
Some optimizations:
- we can preserve the
lengths
array and only observe improved edges - we can start at the end of the added node
Another angle of thinking from Vlad (https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i/solutions/5583452/dp/):
- for each new edge [a,b] improve all [b..n] nodes lengths and siblings of each
Approach
- pay attention to suspicous words
Complexity
-
Time complexity: \(O(qn)\)
-
Space complexity: \(O(q + n)\)
Code
fun shortestDistanceAfterQueries(n: Int, queries: Array<IntArray