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 1.webp

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 IIIpart, 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 1.webp

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 1.webp

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 over n

  • 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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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... and 101010...
  • 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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 solve 0 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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 for costly movements, or just a single Deque 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 1.webp

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 or 1

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 1.webp

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 1.webp

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 in res)

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 1.webp

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 1.webp

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 1.webp

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 and balance can just be a single balance variable, if wildcards + 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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 position i is the sum of the distances
  • we can reuse the previous position result: all 1’s to the right became closer, and all 1’s to the left increase distance, so we do sum[i + 1] = sum[i] - right_ones + left_ones

Approach

  • we don’t need a separate variable for the left and right, as we always operate on the balance = 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 1.webp

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 and auto &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 1.webp

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 1.webp

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 and right 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 1.webp

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 to int

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 1.webp

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 1.webp

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 to 7 day or 30 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 1.webp

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 1.webp

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 1.webp

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:

  1. 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 for max_left + max_middle. And the right search for max_middle + max_right. Update indices on every update of maximum.
  2. Dynamic Programming: dp[i][c] is (max_sum, start_ind) for c k-subarrays in 0..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 1.webp

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 of values[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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 and b
  • 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 1.webp

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 1.webp

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 and b (and a depth)
  • pass inner-right and inner-left values as a and b
  • swapping a and b 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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 big i64 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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.jpg

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 1.webp

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, the start index should be in the same island of 1-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 1.webp

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:

  1. use a Heap, sort by start, pop from heap all non-intersecting previous and peek a max
  2. line sweep: put starts and ends in a timeline, sort by time, compute max after ends, and res 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 1.webp

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 and high 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 1.webp

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 1.webp

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 forward i <= j, L goes backward i >= 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 1.webp

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 1.webp

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 1.webp

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 1.webp

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 1.webp

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.

algo1.jpg

output.gif

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 1.webp

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 1.webp

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 1.webp

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