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

17.07.2024

1110. Delete Nodes And Return Forest medium blog post substack youtube 2024-07-17_08-51.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/673

Problem TLDR

Trees after remove nodes from tree #medium #tree

Intuition

Just iterate and remove on the fly in a single Depth-First Search. Use a HashSet for O(1) checks.

Approach

  • code looks nicer when we can do n.left = dfs(n.left)
  • Rust’s Option clone() is cheap

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun delNodes(root: TreeNode?, to_delete: IntArray) = buildList {
        val set = to_delete.toSet()
        fun dfs(n: TreeNode?): TreeNode? = n?.run {
            left = dfs(left); right = dfs(right); val remove = `val` in set
            if (remove) { left?.let(::add); right?.let(::add) }
            takeIf { !remove }
        }
        dfs(root)?.let(::add)
    }


    pub fn del_nodes(root: Option<Rc<RefCell<TreeNode>>>, to_delete: Vec<i32>) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let set: HashSet<_> = to_delete.into_iter().collect(); let mut res = vec![];
        fn dfs(n_opt: &Option<Rc<RefCell<TreeNode>>>, set: &HashSet<i32>, res: &mut Vec<Option<Rc<RefCell<TreeNode>>>>) 
            -> Option<Rc<RefCell<TreeNode>>> {
                let Some(n_rc) = n_opt else { return None }; let mut n = n_rc.borrow_mut();
                n.left = dfs(&n.left, set, res); n.right = dfs(&n.right, set, res);
                if set.contains(&n.val) {
                    if n.left.is_some() { res.push(n.left.clone()); }; if n.right.is_some() { res.push(n.right.clone()); }
                    None
                } else { (*n_opt).clone() }
            }
        let root = dfs(&root, &set, &mut res); if root.is_some() { res.push(root) }; res
    }

16.07.2024

2096. Step-By-Step Directions From a Binary Tree Node to Another medium blog post substack youtube 2024-07-16_09-53_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/672

Problem TLDR

U-L-R path from s to d in a Binary Tree #medium #tree

Intuition

My first intuition was to do this in a single Depth-First Search step: if left is found and right is found return the result. However, this gives TLE, as concatenating the path on the fly will worsen the time to O(path^2).

Then I checked the discussion and got the hint to use a StringBuilder. However, this can’t be done in a single recursion step, as we should insert to the middle of the path string sometimes.

Now, the working solution: find the Lowest Common Ancestor and go down from it to the source and to the destination.

Another nice code simplification is achieved by finding two paths from the root, and then removing the common prefix from them.

Approach

  • we can be careful with StringBuilder removals or just make toString on the target

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun getDirections(root: TreeNode?, startValue: Int, destValue: Int): String {
        fun down(n: TreeNode?, v: Int, sb: StringBuilder = StringBuilder()): String = n?.run {
            if (`val` == v) sb.toString() else {
                sb.append('L'); val l = down(left, v, sb)
                if (l != "") l else {
                    sb.deleteAt(sb.lastIndex); sb.append('R')
                    down(right, v, sb).also { sb.deleteAt(sb.lastIndex) }
                }
            }
        } ?: ""
        val s = down(root, startValue); val d = down(root, destValue)
        val skip = s.commonPrefixWith(d).length
        return "U".repeat(s.length - skip) + d.drop(skip)
    }


    pub fn get_directions(root: Option<Rc<RefCell<TreeNode>>>, start_value: i32, dest_value: i32) -> String {
        fn down(n: &Option<Rc<RefCell<TreeNode>>>, v: i32, p: &mut Vec<u8>) -> bool {
            let Some(n) = n else { return false }; let n = n.borrow(); if n.val == v { true } else {
                p.push(b'L'); let l = down(&n.left, v, p);
                if l { true } else {
                    p.pop(); p.push(b'R'); let r = down(&n.right, v, p);
                    if r { true } else { p.pop(); false }
                }
            }
        }
        let mut s = vec![]; let mut d = vec![]; 
        down(&root, start_value, &mut s); down(&root, dest_value, &mut d);
        let skip = s.iter().zip(d.iter()).take_while(|(s, d)| s == d).count();
        let b: Vec<_> = (0..s.len() - skip).map(|i| b'U').chain(d.into_iter().skip(skip)).collect();
        String::from_utf8(b).unwrap()
    }

15.07.2024

2196. Create Binary Tree From Descriptions medium blog post substack youtube 2024-07-15_08-14.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/671

Problem TLDR

Restore binary tree from [parent, child, isLeft] #medium

Intuition

Use the HashMap. Remember which nodes are children.

Approach

  • Kotlin: getOrPut
  • Rust: entry.or_insert_with. Rc cloning is cheap.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun createBinaryTree(descriptions: Array<IntArray>): TreeNode? {
        val valToNode = mutableMapOf<Int, TreeNode>()
        val children = mutableSetOf<Int>()
        for ((parent, child, isLeft) in descriptions) {
            val pNode = valToNode.getOrPut(parent) { TreeNode(parent) }
            val cNode = valToNode.getOrPut(child) { TreeNode(child) }
            if (isLeft > 0) pNode.left = cNode else pNode.right = cNode
            children += child
        }
        return valToNode.entries.find { it.key !in children }?.value
    }


    pub fn create_binary_tree(descriptions: Vec<Vec<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut map = HashMap::new(); let mut set = HashSet::new();
        let mut get = |v| { map.entry(v).or_insert_with(|| Rc::new(RefCell::new(TreeNode::new(v)))).clone() };
        for d in descriptions {
            let child = get(d[1]);
            let mut parent = get(d[0]); let mut parent = parent.borrow_mut();
            set.insert(d[1]);
            *(if d[2] > 0 { &mut parent.left } else { &mut parent.right }) = Some(child)
        }
        map.into_values().find(|v| !set.contains(&v.borrow().val))
    }

14.07.2024

726. Number of Atoms hard blog post substack youtube 2024-07-14_09-58_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/669

Problem TLDR

Simplify chemical formula parenthesis #hard #stack

Intuition

This is a parenthesis problem, and it could be solved with a stack or a recursion.

Approach

The simplest way is to use a global position variable and a recursion. Return frequencies map and merge the result.

The more optimal way is to traverse from the end: that’s how you know the multiplier of each atom beforehand.

Complexity

  • Time complexity: \(O(n)\), we only traverse once, and the merge operation is on a small subset: AB(AB(AB(AB(..)))) where AB.length is much less than the recursion depth will take depth*len = N

  • Space complexity: \(O(n)\)

Code


    fun countOfAtoms(formula: String): String {
        var i = 0
        fun count(): Int {
            if (i > formula.lastIndex || !formula[i].isDigit()) return 1
            val from = i; while (i < formula.length && formula[i].isDigit()) i++
            return formula.substring(from, i).toInt()
        }
        fun dfs(): Map<String, Int> = TreeMap<String, Int>().apply {
            while (i < formula.length) if (formula[i] == ')') break
                else if (formula[i] == '(') {
                    i++; val inBrackets = dfs(); i++
                    var count = count()
                    for ((name, c) in inBrackets) this[name] = c * count + (this[name] ?: 0)
                } else {
                    var from = i++; while (i < formula.length && formula[i].isLowerCase()) i++
                    val name = formula.substring(from, i)
                    this[name] = count() + (this[name] ?: 0)
                }
        }
        return dfs().entries.joinToString("") { it.run { if (value > 1) "$key$value" else key }}
    } 


    pub fn count_of_atoms(formula: String) -> String {
        let (mut map, mut c, mut cnt, mut pow, mut name, mut stack) = 
            (HashMap::new(), 1, 0, 1, vec![], vec![]);
        for b in formula.bytes().rev() { match (b) {
            b'0'..=b'9' => { cnt += (b - b'0') as i32 * pow; pow *= 10 },
            b')' =>  { stack.push(cnt); c *= cnt.max(1); pow = 1; cnt = 0 },
            b'(' => { c /= stack.pop().unwrap().max(1); pow = 1; cnt = 0 },
            b'A'..=b'Z' => {
                name.push(b); name.reverse(); 
                *map.entry(String::from_utf8(name.clone()).unwrap())
                    .or_insert(0) += cnt.max(1) * c;
                name.clear(); pow = 1; cnt = 0
            }, _ => { name.push(b) }
        }}
        let mut keys = Vec::from_iter(map.iter()); keys.sort_unstable();
        keys.iter().map(|&(k, v)| if *v > 1 { format!("{k}{v}") } else { k.into() }).collect()
    }

13.07.2024

2751. Robot Collisions hard blog post substack youtube 2024-07-13_09-40_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/668

Problem TLDR

1-D dimensional robots fight #hard #stack

Intuition

Sort by positions, then solve the matching parenthesis subproblem. We can use a Stack.


    // 11 44 16
    //  1 20 17
    //  R L  R
    //
    //  1->    17->     <-20
    //  11     16         44

Approach

  • move ‘L’ as much as possible in a while loop

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(n)\)

Code


    fun survivedRobotsHealths(positions: IntArray, healths: IntArray, directions: String) = 
        with(Stack<Int>()) {
            val inds = positions.indices.sortedBy { positions[it] }
            for (i in inds) if (directions[i] > 'L') push(i) else {
                while (size > 0 && directions[peek()] > 'L') 
                    if (healths[peek()] == healths[i]) { pop(); healths[i] = 0; break }
                    else if (healths[peek()] < healths[i]) { pop(); healths[i]-- }
                    else { healths[peek()]--; healths[i] = 0; break }
                if (healths[i] > 0) push(i)
            }
            sorted().map { healths[it] }
        }


    pub fn survived_robots_healths(positions: Vec<i32>, mut healths: Vec<i32>, directions: String) -> Vec<i32> {
        let (mut st, mut inds, d) = (vec![], (0..positions.len()).collect::<Vec<_>>(), directions.as_bytes());
        inds.sort_unstable_by_key(|&i| positions[i]);
        for i in inds {
            if d[i] > b'L' { st.push(i) } else {
                while let Some(&j) = st.last() {
                    if d[j] < b'R' { break }
                    if healths[j] > healths[i] { healths[j] -= 1; healths[i] = 0; break }
                    else if healths[j] < healths[i] { st.pop(); healths[i] -= 1 }
                    else { st.pop(); healths[i] = 0; break }
                }
                if healths[i] > 0 { st.push(i) }
            }
        }
        st.sort_unstable(); st.iter().map(|&i| healths[i]).collect()
    }

12.07.2024

1717. Maximum Score From Removing Substrings medium blog post substack youtube 2024-07-12_08-17_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/667

Problem TLDR

Max score removing from s, x for ab, y for ba #medium #greedy #stack

Intuition

The first intuition is to remove greedily, but how exactly? Let’s observe some examples:


    // aba      x=1 y=2
    // a     a
    //  b    ab 
    //
    // aabbab   x=1 y=2  y>x
    // a      a
    //  a     aa
    //   b    aab
    //   
    // bbaabb  x>y
    // b      b
    //  b     bb
    //   a    bba
    //    a   bb 
    // ...

We should maintain the Stack to be able to remove cases like aabb in one go. We should not remove the first ab from aba, when the reward from ba is larger. So, let’s do it in two passes: first remove the larger reward, then the other one.

Approach

  • we can extract the removal function

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun maximumGain(s: String, x: Int, y: Int): Int {
        var points = 0
        val a = if (x > y) 'a' else 'b'; val b = if (a < 'b') 'b' else 'a'
        val stack = Stack<Char>().apply {
            for (c in s) if (c == b && size > 0 && peek() == a) {
                pop(); points += max(x, y)
            } else push(c)
        }
        Stack<Char>().apply {
            for (c in stack) if (c == a && size > 0 && peek() == b) {
                    pop(); points += min(x, y)
                } else push(c)
        }
        return points
    }


    pub fn maximum_gain(s: String, mut x: i32, mut y: i32) -> i32 {
        let (mut a, mut b) = (b'a', b'b'); 
        if x < y { mem::swap(&mut a, &mut b); mem::swap(&mut x, &mut y) }
        fn remove_greedy(s: &String, a: u8, b: u8) -> String {
            let mut res = vec![];
            for c in s.bytes() {
                if res.len() > 0 && *res.last().unwrap() == a && c == b {
                    res.pop();
                } else { res.push(c) }
            }
            String::from_utf8(res).unwrap()
        }
        let s1 = remove_greedy(&s, a, b); let s2 = remove_greedy(&s1, b, a);
        (s.len() - s1.len()) as i32 / 2 * x + (s1.len() - s2.len()) as i32 / 2 * y
    }

11.07.2024

1190. Reverse Substrings Between Each Pair of Parentheses medium blog post substack youtube 2024-07-11_08-54_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/666

Problem TLDR

Reverse string in parentheses recursively #medium

Intuition

The simplest way is to simulate the reversing: do Depth-First Search and use parenthesis as nodes. It will take O(n^2) time.

There is also an O(n) solution possible.

Approach

  • let’s use LinkedList in Rust, it will make solution O(n)

Complexity

  • Time complexity: \(O(n^2)\), O(n) for the Linked List solution

  • Space complexity: \(O(n)\)

Code


    fun reverseParentheses(s: String): String {
        var i = 0
        fun dfs(): String = buildString {
            while (i < s.length)
                if (s[i] == '(') {
                    i++
                    append(dfs().reversed())
                    i++
                } else if (s[i] == ')') break
                else append(s[i++])
        }
        return dfs()
    }


    pub fn reverse_parentheses(s: String) -> String {
        fn dfs(chars: &mut Chars, rev: bool) -> LinkedList<char> {
            let mut list = LinkedList::<char>::new();
            while let Some(c) = chars.next() {
                if c == ')' { break }
                if c == '(' {
                    let mut next = dfs(chars, !rev);
                    if rev { next.append(&mut list); list = next }
                    else { list.append(&mut next) }
                } else { if rev { list.push_front(c) } else { list.push_back(c) }}
            }; list
        }
        return dfs(&mut s.chars(), false).into_iter().collect()
    }

10.07.2024

1598. Crawler Log Folder easy blog post substack youtube 2024-07-10_07-40_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/665

Problem TLDR

Filesystem path depth #easy

Intuition

Simulate the process and compute depth. Corner case: a path doesn’t move up from the root.

Approach

Let’s use fold iterator.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun minOperations(logs: Array<String>) =
        logs.fold(0) { depth, op -> when (op) {
            "../" -> max(0, depth - 1) 
            "./" -> depth else -> depth + 1 }}


    pub fn min_operations(logs: Vec<String>) -> i32 {
        logs.iter().fold(0, |depth, op| match op.as_str() {
            "../" => 0.max(depth - 1), 
            "./" => depth,  _ =>  depth + 1 })
    }

9.07.2024

1701. Average Waiting Time medium blog post substack youtube 2024-07-09_07-43_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/664

Problem TLDR

Average of intersecting intervals #medium #simulation

Intuition

Just simulate the process.

Approach

Let’s use iterators to save lines of code.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun averageWaitingTime(customers: Array<IntArray>): Double {
        var time = 0
        return customers.sumOf { (start, delta) ->
            time = max(start, time) + delta
            (time - start).toDouble()
        } / customers.size
    }


    pub fn average_waiting_time(customers: Vec<Vec<i32>>) -> f64 {
        let mut time = 0;
        customers.iter().map(|c| {
            time = time.max(c[0]) + c[1];
            (time - c[0]) as f64
        }).sum::<f64>() / customers.len() as f64
    }

8.07.2024

1823. Find the Winner of the Circular Game medium blog post substack youtube 2024-07-08_08-27.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/663

Problem TLDR

Last of k-th excluded from 1..n #medium #simulation #math

Intuition

Let’s observe the problem:


    // 1 2 3 4 5 1 2 3 4 5        2
    // * *
    //   x * *              2
    //       x * *          4
    //           x x * x *  1
    //                   x  5
    //   
    // 1 2 3 4 5 1 3 5 3
    //   x   x   x   x

    // 6, 1
    // 1 2 3 4 5 6        1
    // x x x x x 

I didn’t see any simple pattern here (however, it exists, see below). So, let’s just use a linked list and simulate the process.

The math solution involves knowing the Josephus Problem https://en.wikipedia.org/wiki/Josephus_problem, and it is a Dynamic Programming answer(n, k) = (answer(n - 1, k) + k) %n, or ans = 0; for (i in 1..n) ans = (ans + k) % i; ans + 1.

Approach

Kotlin: let’s implement linked list as an array of pointers. Rust: let’s implement a bottom up DP solution. (after reading the wiki and other’s solutions :) )

Complexity

  • Time complexity: \(O(nk)\)

  • Space complexity: \(O(n)\)

Code


    fun findTheWinner(n: Int, k: Int): Int {
        val nexts = IntArray(n + 1) { it + 1 }; nexts[n] = 1
        var curr = 1
        repeat(n - 1) {
            var prev = curr
            repeat(k - 1) { prev = curr; curr = nexts[curr] }
            nexts[prev] = nexts[curr]
            curr = nexts[curr]
        }
        return curr
    }


    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        let mut ans = 0;
        for i in 1..=n { ans = (ans + k) % i }
        ans + 1
    }

7.07.2024

1518. Water Bottles easy blog post substack youtube 2024-07-07_09-25_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/662

Problem TLDR

Bottles drink and exchange simulation #easy #math #simulation

Intuition

Run the simulation:


    // a n
    // drink                      empty
    // a                          a
    // a/n                        a/n+a%n
    // (a/n+a%n)/n                (a/n+a%n)/n+(a/n+a%n)%n

There is also a math solution based on geometric series sum \(a + a/n + a/n^2 + ... = a/(1-1/n) = an/(n-1)\) (https://en.wikipedia.org/wiki/Geometric_series). Given that, it is sometimes off by one, we can write \((an - 1)/(n - 1)\). I doubt I could remember this in an interview or a contest though.

Approach

Let’s use as little variables as possible.

Complexity

  • Time complexity: \(O(log_e(b))\), e - numExchange, b - numBottles

  • Space complexity: \(O(1)\)

Code


    fun numWaterBottles(numBottles: Int, numExchange: Int): Int {
        var drink = numBottles
        var empty = numBottles
        while (empty >= numExchange) {
            drink += empty / numExchange
            empty = empty / numExchange + empty % numExchange
        }
        return drink
    }


    pub fn num_water_bottles(num_bottles: i32, num_exchange: i32) -> i32 {
        let (mut drink, mut empty) = (num_bottles, num_bottles);
        while empty >= num_exchange {
            drink += empty / num_exchange;
            empty = empty / num_exchange + empty % num_exchange
        }
        drink
    }

6.07.2024

2582. Pass the Pillow easy blog post substack youtube 2024-07-06_08-32_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/661

Problem TLDR

Loop position in increasing-decreasing array #easy #math #simulation

Intuition

For the interview or contest just write a simulation code, it is straghtforward: use delta variable and change its sign when i reaches 1 or n, repeat time` times.

The O(1) solution can be derived from the observation of the repeating patterns:


    //n = 4
    //t  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
    //i  1 2 3 4 3 2 1 2 3 4 3  2  1  2  3  4  3  2  1  2  3  4
    //     1 2 3 1 2 3 1 2 3 1  2  3  1  2  3  1  2  3  1  2  3
    //               ^
    //               t=6
    //               6/3 = 2 -> 2%2=0 (increasing)
    //               6%3 = 0 -> i=1+0
    //                 ^
    //                 t=7
    //                 7/3=2 -> 2%2=0 (increasing)
    //                 7%3=1 -> i=1+1=2
    //                     ^
    //                     t=9
    //                     9/3=3 -> 3%2=1 (decreasing)
    //                     9%3=0 -> i=4-0=4
    //                                      ^
    //                                      t=15
    //                                      15/3=5 -> 5%2=1 (decreasing)
    //                                      15%3=0 -> i=4-0=4
    //                           

There are cycles, in which i increases and decreases and we can say, it is n - 1 length. From that we need to find in which kind of cycle we are and derive two cases: in increasing add remainder of cycle to 1, in decreasing subtract the remainder from n.

There is another approach however, it is to consider cycle as a full round of 2 * (n - 1) steps. Then the solution is quite similar.

Approach

Let’s implement it first in Kotlin and second in Rust. (Simulation code I wrote on the youtube screencast, it didn’t require thinking.)

Complexity

  • Time complexity: \(O(1)\)

  • Space complexity: \(O(1)\)

Code


    fun passThePillow(n: Int, time: Int): Int {
        val rounds = time / (n - 1)
        val rem = time % (n - 1)
        return if (rounds % 2 > 0) n - rem else 1 + rem
    }


    pub fn pass_the_pillow(n: i32, time: i32) -> i32 {
        let t = time % (2 * (n - 1));
        if t > n - 1 { n - (t - n) - 1 } else { t + 1 }
    }

5.07.2024

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points medium blog post substack youtube 2024-07-05_09-00_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/660

Problem TLDR

[min, max] distance between critical points in linked list #medium #linked_list

Intuition

Just do what is asked.

Approach

  • we can reuse previous variables a and b

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun nodesBetweenCriticalPoints(head: ListNode?): IntArray {
        var first = -1; var last = -1; var min = Int.MAX_VALUE
        var i = 0; var curr = head?.next; val e = intArrayOf(-1, -1)
        var a = head?.`val` ?: return e; var b = curr?.`val` ?: return e
        while (curr?.next != null) {
            if (a > b && b < curr.next.`val` || a < b && b > curr.next.`val`) 
                if (first == -1) first = i else {
                    min = min(min, i - max(first, last))
                    last = i
                }
            i++; a = b; b = curr.next.`val`; curr = curr.next
        }
        return if (last > 0) intArrayOf(min, last - first) else e
    }


    pub fn nodes_between_critical_points(head: Option<Box<ListNode>>) -> Vec<i32> {
        let (mut first, mut last, mut min, mut i, e) = (-1, -1, i32::MAX, 0, vec![-1, -1]);
        let Some(head) = head else { return e }; let mut a = head.val;
        let Some(mut curr) = head.next else { return e }; let mut b = curr.val;
        while let Some(next) = curr.next {
            if a > b && b < next.val || a < b && b > next.val {
                if first == -1 { first = i } else {
                    min = min.min(i - last.max(first));
                    last = i
                }
            }
            i += 1; a = b; b = next.val; curr = next
        }
        if last > 0 { vec![min, last - first] } else { e }
    }

4.07.2024

2181. Merge Nodes in Between Zeros medium blog post substack youtube 2024-07-04_09-23.webp

https://t.me/leetcode_daily_unstoppable/659

Problem TLDR

Collapse in-between 0 nodes in a LinkedList #medium #linked_list

Intuition

Just do what is asked: iterate and modify the values and links on the fly.

Approach

  • Kotlin: let’s use just one extra variable
  • Rust: I am sorry

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun mergeNodes(head: ListNode?): ListNode? {
        var curr = head?.next
        while (curr?.next != null) 
            if (curr.next?.`val` ?: 0 > 0) {
                curr.`val` += curr.next?.`val` ?: 0
                curr.next = curr.next?.next
            } else {
                curr.next = curr.next?.next
                curr = curr.next
            }
        return head?.next
    }


    pub fn merge_nodes(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let Some(head_box) = head.as_mut() else { return head };
        let mut curr = &mut head_box.next;
        while let Some(curr_box) = curr {
            let Some(next_box) = curr_box.next.as_mut() else { curr_box.next = None; break };
            if next_box.val > 0 {
                curr_box.val += next_box.val;
                curr_box.next = next_box.next.take()
            } else {
                curr_box.next = next_box.next.take();
                curr = &mut curr.as_mut().unwrap().next
            }
        }
        head.unwrap().next
    }

3.07.2024

1509. Minimum Difference Between Largest and Smallest Value in Three Moves medium blog post substack youtube 2024-07-03_07-33_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/658

Problem TLDR

Min difference after 3 changes in array #medium #sliding_window #dynamic_programming

Intuition

Let’s observe some examples and try to derive the algorithm:

    //  1  3  5  7  9  11
    //  min = 1
    //  max4 = (5, 7, 9, 11)
    //  res = 5 - 1 = 4
    //
    //  0 1 1 4 6 6 6
    //  min = 0
    //  max4 = 4 6 6 6
    //
    //  20 75 81 82 95
    //  55          13
    //      i
    //      6
    //           j
    //           1
    //         i

As we see, we cannot just take top 3 max or top 3 min, there are corner cases, where some min and some max must be taken. So, we can do a full search of 3 boolean choices, 2^3 total comparisons in a Depth-First search manner. Another way to look at the problem as suffix-prefix trimming: 0 prefix + 3 suffix, 1 prefix + 2 suffix, 2 prefix + 1 suffix, 3 prefix + 0 suffix. So, a total of 4 comparisons in a Sliding Window manner.

Approach

Let’s implement both approaches.

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


    fun minDifference(nums: IntArray): Int {
        nums.sort()
        fun dfs(i: Int, j: Int, n: Int): Int =
            if (i == j) 0 else if (i > j) Int.MAX_VALUE
            else if (n > 2) nums[j] - nums[i]
            else min(dfs(i + 1, j, n + 1), dfs(i, j - 1, n + 1))
        return dfs(0, nums.lastIndex, 0)
    }


    pub fn min_difference(mut nums: Vec<i32>) -> i32 {
        let n = nums.len(); if n < 4 { return 0 }; nums.sort_unstable();
        (0..4).map(|i| nums[n - 4 + i] - nums[i]).min().unwrap()
    }

2.07.2024

350. Intersection of Two Arrays II easy blog post substack youtube 2024-07-02_07-44_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/657

Problem TLDR

Array intersection with duplicates #easy

Intuition

We can do sorting and two pointers. If nums2 on a hard disk, let’s not touch it, just iterate once. For nums1 we can use a counting sort for O(n) solution. For code golf, we can modify nums1 in-place with O(n^2) solution.

Approach

Golf in Kotlin, can you make it shorter? Counting sort in Rust.

Complexity

  • Time complexity: \(O(n)\) for counting sort, O(nlogn) for both sort & two pointers

  • Space complexity: \(O(n)\) for counting sort (n = 1000), O(1) for sort & two pointers

Code


    fun intersect(nums1: IntArray, nums2: IntArray) = nums2.filter { 
        val i = nums1.indexOf(it); if (i >= 0) nums1[i] = -1; i >= 0
    }


    pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut f = vec![0; 1001]; for n in nums1 { f[n as usize] += 1 }
        nums2.into_iter().filter(|&n| {
            let b = f[n as usize] > 0; f[n as usize] -= 1; b
        }).collect()
    }

1.07.2024

1550. Three Consecutive Odds easy blog post substack youtube 2024-07-01_07-12_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/656

Problem TLDR

Has window of 3 odds? #easy

Intuition

Such questions are helping to start with a new language.

Approach

Can you make it shorter?

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\) for Rust, O(n) for Kotlin, can be O(1) with asSequence.

Code


    fun threeConsecutiveOdds(arr: IntArray) =
        arr.asList().windowed(3).any { it.all { it % 2 > 0 }}


    pub fn three_consecutive_odds(arr: Vec<i32>) -> bool {
        arr[..].windows(3).any(|w| w.iter().all(|n| n % 2 > 0))
    }

30.06.2024

1579. Remove Max Number of Edges to Keep Graph Fully Traversable medium blog post substack youtube 2024-06-30_11-27.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/655

Problem TLDR

Remove extra nodes in a connected graph by type 1, 2 and 3=1+2 #hard #union-find

Intuition

Type 3 nodes are the most valueable, let’s keep them. Then check if type 1 is already connected by type 3 and do the same for type 2. To check connections use the Union-Find.

Approach

  • at the end we can check connections to the first node, or just simple count how many edges added and compare it to n - 1
  • both type1 and type2 must have add (n - 1) edges
  • optimized Union-Find must have path compression and ranking, making time complexity O(1) (google inverse Akkerman function)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun maxNumEdgesToRemove(n: Int, edges: Array<IntArray>): Int {
        class Uf(var v: Int = n - 1): HashMap<Int, Int>() {
            fun u(a: Int, b: Int): Boolean = if (f(a) == f(b)) false 
                else { set(f(a), f(b)); v--; true }
            fun f(a: Int): Int = if (get(a) == a) a else 
                get(a)?.let { b -> f(b).also { set(b, it) } } ?: a
        }
        val uu = List(2) { Uf() }; val u = Uf(); var count = 0
        for ((t, a, b) in edges) if (t == 3) 
            if (!u.u(a, b)) count++ else for (u in uu) u.u(a, b)
        for ((t, a, b) in edges) if (t < 3) if (!uu[t - 1].u(a, b)) count++
        return if (uu.all { it.v < 1 }) count else -1
    }


    pub fn max_num_edges_to_remove(n: i32, edges: Vec<Vec<i32>>) -> i32 {
        fn u(uf: &mut Vec<usize>, a: &[i32]) -> i32 {
            let (fa, fb) = (f(uf, a[1] as usize), f(uf, a[2] as usize)); 
            if fa == fb { 0 } else { uf[fa] = fb; 1 }}
        fn f(uf: &mut Vec<usize>, a: usize) -> usize {
            let mut x = a; while x != uf[x] { x = uf[x] }; uf[a] = x; x }
        let mut u3 = (0..=n as usize).collect::<Vec<_>>();
        let (mut uu, mut v, mut res) = ([u3.clone(), u3.clone()], 2 * n - 2, 0);
        for e in &edges { if e[0] == 3 {
            if u(&mut u3, e) < 1 { res += 1 } 
            else { for t in 0..2 { v -= u(&mut uu[t], e) }}}}
        for e in &edges { if e[0] < 3 { 
            if u(&mut uu[e[0] as usize - 1], e) < 1 { res += 1 } else { v -= 1 }}}
        if v < 1 { res } else { -1 }
    }

29.06.2024

2192. All Ancestors of a Node in a Directed Acyclic Graph medium blog post substack youtube 2024-06-29_08-11_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/654

Problem TLDR

List of ancestors in a DAG #medium #dfs #toposort

Intuition

2024-06-29_08-14.webp We can use Depth-First Search for each node, caching the result to not execute twice, but we should walk backwards from child to parent.

Another solution is to walk from parents in a Topological Sort order and appending the results.

Approach

Let’s implement both approaches. For the toposort solution (in Rust), we should do deduplication as early as possible to prevent OOM.

Complexity

  • Time complexity: \(O(E^2V + V^2log(V))\) for DFS - groupBy will take O(E), DFS depth is O(E) and inside it we iterate over each sibling O(X), X is up to E where we do copy of all collected vertices O(V). The final step is sorting V collected vertexes - VlogV.

\(O(V + EVlog(V))\), the Kahn algorithm for toposort takes O(V + E), in each step of edge taking we append V vertices, and sorting them Vlog(V)

  • Space complexity: \(O(V^2 + E)\) result takes the biggest space

Code


    fun getAncestors(n: Int, edges: Array<IntArray>): List<List<Int>> {
        val g = edges.groupBy({ it[1] }, { it[0] })
        val res = mutableMapOf<Int, Set<Int>>()
        fun dfs(i: Int): Set<Int> = res.getOrPut(i) {
            g[i]?.map { dfs(it) + it }?.flatten()?.toSet() ?: setOf()
        }
        return (0..<n).map { dfs(it).sorted() }
    }


    pub fn get_ancestors(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = n as usize; let (mut deg, mut g, mut res, mut queue) = 
            (vec![0; n], vec![vec![]; n], vec![vec![]; n], VecDeque::new());
        for e in edges {
            g[e[0] as usize].push(e[1] as usize); deg[e[1] as usize] += 1
        }
        for i in 0..n { if deg[i] == 0 { queue.push_back(i); }}
        while let Some(top) = queue.pop_front() { for &j in &g[top] {
            deg[j] -= 1; if deg[j] == 0 { queue.push_back(j); }
            res[j].push(top as i32); let t = res[top].clone(); 
            res[j].extend(t); res[j].sort_unstable(); res[j].dedup()
        }}; res
    }

28.06.2024

2285. Maximum Total Importance of Roads medium blog post substack youtube 2024-06-28_06-37.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/653

Problem TLDR

Sort graph by siblings and compute sum(i*s) #medium

Intuition

Notice that the more siblings the bigger rank should be to produce the optimal result.

Approach

We can sort the count array or use bucket sort of size n to reduce time complexity to O(n).

Complexity

  • Time complexity: \(nlog(n)\)

  • Space complexity: \(O(n)\)

Code


    fun maximumImportance(n: Int, roads: Array<IntArray>): Long {
        val counts = IntArray(n); var i = 1
        for ((a, b) in roads) { counts[a]++; counts[b]++ }
        return counts.sorted().sumOf { it * (i++).toLong() }
    }


    pub fn maximum_importance(n: i32, roads: Vec<Vec<i32>>) -> i64 {
        let mut counts = vec![0; n as usize];
        for r in roads { counts[r[0] as usize] += 1; counts[r[1] as usize] += 1}
        counts.sort_unstable();
        (0..n as usize).map(|i| counts[i] * (i + 1) as i64).sum()
    }

27.06.2024

1791. Find Center of Star Graph easy blog post substack youtube 2024-06-27_06-48_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/652

Problem TLDR

Center of a start graph #easy

Intuition

It’s just a common node between two edges.

Approach

Can you make it shorter?

Complexity

  • Time complexity: \(O(1)\)

  • Space complexity: \(O(1)\)

Code


    fun findCenter(e: Array<IntArray>) =
        e[0].first { it in e[1] }


    pub fn find_center(e: Vec<Vec<i32>>) -> i32 {
       if e[1].contains(&e[0][0]) { e[0][0] } else { e[0][1] }
    }

26.06.2024

1382. Balance a Binary Search Tree medium blog post substack youtube 2024-06-26_06-42_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/651

Problem TLDR

Make a balanced Binary Search Tree #medium

Intuition

Construct it back from a sorted array: always peek the middle.

Approach

  • notice how slices in Rust are helping to reduce the complexity

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun balanceBST(root: TreeNode?): TreeNode? {
        val sorted = mutableListOf<Int>()
        fun dfs1(n: TreeNode?): Unit? = n?.run { 
            dfs1(left); sorted += `val`; dfs1(right) }
        fun dfs2(lo: Int, hi: Int): TreeNode? =
            if (lo > hi) null else {
            val mid = (lo + hi) / 2
            TreeNode(sorted[mid]).apply {
                left = dfs2(lo, mid - 1); right = dfs2(mid + 1, hi)
            }}
        dfs1(root); return dfs2(0, sorted.lastIndex)
    }


    pub fn balance_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs1(n: &Option<Rc<RefCell<TreeNode>>>, sorted: &mut Vec<i32>) {
            let Some(n) = n.as_ref() else { return; }; let n = n.borrow();
            dfs1(&n.left, sorted); sorted.push(n.val); dfs1(&n.right, sorted)
        }
        fn dfs2(sorted: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
            if sorted.len() < 1 { return None }; let mid = sorted.len() / 2;
            let left = dfs2(&sorted[..mid]);
            let right = dfs2(&sorted[mid + 1..]);
            Some(Rc::new(RefCell::new(TreeNode { val: sorted[mid], left: left, right: right })))
        }
        let mut sorted = vec![]; dfs1(&root, &mut sorted); dfs2(&sorted[..])
    }

25.06.2024

1038. Binary Search Tree to Greater Sum Tree medium blog post substack youtube 2024-06-25_07-02_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/650

Problem TLDR

Aggregate Binary Search Tree from the right #medium #tree

Intuition

Just iterate from the tail in an inorder DFS traversal.

2024-06-25_06-24.webp

Approach

  • notice how 26 jumps straight to the root, so we must store the result somewhere
  • there is a nice patter in Rust: `let Some(..) = .. else { .. }

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\) for the call stack, however, it can be O(1) for the Morris Traversal

Code


    var s = 0
    fun bstToGst(root: TreeNode?): TreeNode? = root?.apply {
        bstToGst(right); `val` += s; s = `val`; bstToGst(left)
    }


    pub fn bst_to_gst(mut root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, s: i32) -> i32 {
            let Some(n) = n.as_ref() else { return s }; let mut n = n.borrow_mut();
            n.val += dfs(&n.right, s); dfs(&n.left, n.val) 
        }
        dfs(&root, 0); root
    }

24.06.2024

995. Minimum Number of K Consecutive Bit Flips medium blog post substack youtube 2024-06-24_07-04_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/649

Problem TLDR

Count k-range flips in binary array to make all 1 #hard #sliding_window

Intuition

We should flip all the 0, so let’s do it greedily. The hardness of the problem lies in the question of how much flips are already done for the current position. Let’s observe an example:


    // 0 1 2 3 4 5 6 7   k=3
    // 0 0 0 1 0 1 1 0  flip
    // * * *            [0..2]
    //         * * *    [4..6]
    //           * * *  [5..7]
    //           ^ how much flips in 3..5 range
    //                            or >= 3

If we maintain a window of i-k+1..i, we shall remember only the flips in this window and can safely drop all the flips in 0..i-k range.

Approach

The greedy is hard to prove, so try as much examples as possible.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun minKBitFlips(nums: IntArray, k: Int): Int {
        var total = 0; var flips = ArrayDeque<Int>()
        for ((i, n) in nums.withIndex()) {
            while (flips.size > 0 && flips.first() + k < i + 1) 
                flips.removeFirst()
            if ((1 - n + flips.size) % 2 > 0) {
                total++
                flips += i
                if (i + k > nums.size) return -1
            }
        }
        return total
    }


    pub fn min_k_bit_flips(nums: Vec<i32>, k: i32) -> i32 {
        let (mut total, mut flips) = (0, VecDeque::new());
        for (i, n) in nums.iter().enumerate() {
            while flips.front().unwrap_or(&i) + (k as usize) < i + 1 
                { flips.pop_front(); }
            if (1 - n  + flips.len() as i32) % 2 > 0 {
                total += 1;
                if i + k as usize > nums.len() { return -1 }
                flips.push_back(i)
            }
        }; total as i32
    }

23.06.2024

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit medium blog post substack youtube 2024-06-23_07-19_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/648

Problem TLDR

Longest subarray with abs(a[i] - a[j]) <= limit #medium #sliding_window #monotonic_queue

Intuition

Let’s observe how we can do this in a single iteration:


    //      0 1 2 3
    //      8 2 4 7    limit=4
    // 0    i
    //      j       8
    // 1      i     8 2    or 2 
    // 2        i   8 2 4  8-2=6>4 -> move j
    //        j     2 4
    // 3          i 2 4 7  7-2=5>4 -> move j
    //          j   4 7

We should keep the window j..i and maintain maximums and minimums.

To find next maximum after current is dropped we can use Monotonic Queue technique: make it always decreasing, like 5 4 3 2 1. If any new value is bigger then the tail, for example add 4, it will be the next maximum and the tail 3 2 1 becomes irrelevant: 5 4 3 2 1 + 4 -> 5 4 4.

(Another solution would be to just use two heaps, one for maxiums, another for minimums.)

Approach

  • iterators saves some lines: maxOf, iter().max()
  • notice unwrap_or(&n) trick in Rust

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun longestSubarray(nums: IntArray, limit: Int): Int {
        val mins = ArrayDeque<Int>(); val maxs = ArrayDeque<Int>()
        var j = 0
        return nums.withIndex().maxOf { (i, n) ->
            while (mins.size > 0 && mins.last() > n) mins.removeLast()
            while (maxs.size > 0 && maxs.last() < n) maxs.removeLast()
            mins += n; maxs += n
            if (maxs.first() - mins.first() > limit) {
                if (nums[j] == maxs.first()) maxs.removeFirst()
                if (nums[j++] == mins.first()) mins.removeFirst()
            }
            i - j + 1
        }
    }


    pub fn longest_subarray(nums: Vec<i32>, limit: i32) -> i32 {
        let (mut mins, mut maxs, mut j) = (VecDeque::new(), VecDeque::new(), 0);
        nums.iter().enumerate().map(|(i, &n)| {
            while *mins.back().unwrap_or(&n) > n { mins.pop_back(); }
            while *maxs.back().unwrap_or(&n) < n { maxs.pop_back(); }
            mins.push_back(n); maxs.push_back(n);
            if maxs.front().unwrap() - mins.front().unwrap() > limit {
                if nums[j] == *mins.front().unwrap() { mins.pop_front(); }
                if nums[j] == *maxs.front().unwrap() { maxs.pop_front(); }
                j += 1
            }
            (i - j + 1) as i32
        }).max().unwrap()
    }

22.06.2024

1248. Count Number of Nice Subarrays medium blog post substack youtube 2024-06-22_07-18_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/647

Problem TLDR

Count subarrays with k odds #medium #sliding_window

Intuition

Let’s observe the problem:

    // 1 1 2 1 1      k=3
    // * * * *
    //   * * * *

    // 0 1 2 3 4 5 6 7 8 9 
    // 2 2 2 1 2 2 1 2 2 2  k=2
    //           .          count
    // i         .          0
    //   i       .          0
    //     i     .          0
    //       i   .          1 < k
    //         i .
    //           i
    //             i        2 == k, +4 [0..6],[1..6],[2..6],[3..6] 
    //               i      2 == k  +4  0..7 1..7 2..7 3..7
    //                 i    2 == k  +4  0..8 1..8 2..8 3..8
    //                   i  2 == k  +4  0..9 1..9 2..9 3..9

When we find a good window [3..6] we must somehow calculate the number of contiguous subarrays. Let’s experiment how we can do it in a single pass: when i = 6 we must add to the result all subarrays 0..6 1..6 2..6 3..6 and stop until the first odd. So, let’s use a third pointer border to count the number of prefix subarrays: j - border.

Approach

  • Using sumOf can shorten some lines of code.
  • & 1 gives 1 for odd numbers.
  • Some conditions are exclusive to each other, and we can skip them: cnt > 0 means j will stop at least once. (Don’t do this in an interview, just use j < nums.len().)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun numberOfSubarrays(nums: IntArray, k: Int): Int {
        var border = -1; var j = 0; var cnt = 0
        return nums.sumOf { n ->
            cnt += n and 1
            while (cnt > k) {
                border = j
                cnt -= nums[j++] and 1
            }
            while (cnt > 0 && nums[j] % 2 < 1) j++
            if (cnt < k) 0 else j - border
        }
    }


    pub fn number_of_subarrays(nums: Vec<i32>, k: i32) -> i32 {
        let (mut b, mut cnt, mut j) = (-1, 0, 0);
        nums.iter().map(|n| {
            cnt += n & 1;
            while cnt > k { b = j as i32; cnt -= nums[j] & 1; j += 1 }
            while cnt > 0 && nums[j] & 1 < 1 { j += 1 }
            if cnt < k { 0 } else { j as i32 - b }
        }).sum()
    }

21.06.2024

1052. Grumpy Bookstore Owner medium blog post substack youtube 2024-06-21_07-07_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/646

Problem TLDR

Max customers sum after make consecutive minutes non-grumpy #medium #sliding_window

Intuition

It was hard. First understand the problem: we can take all the 0-grumpy minutes, but 1-grumpy can only be in minutes, and must be choosen. Let’s explore the example:


    // 1  2  3 4  5  6 7  8 9      m=2
    // 1  1  0 1  1  0 1  1 1
    // *  *    *  *    *  *
    //                    * *
    //
    // 2 4 1 4 1   m=2
    // 1 0 1 0 1
    // * *
    //     * *

The sliding window must be from the 1-grumpy days to choose the maximum and ignore all 0-grumpy days, because they are always be taken.

Approach

Keep 0-grumpy and 1 grumpy sums in separate variables.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun maxSatisfied(customers: IntArray, grumpy: IntArray, minutes: Int): Int {
        var sum = 0; var max = 0; var other = 0; var j = 0
        for ((i, c) in customers.withIndex()) {
            sum += c * grumpy[i]
            other += c * (1 - grumpy[i])
            while (j <= i - minutes) sum -= customers[j] * grumpy[j++]
            max = max(max, sum)
        }
        return max + other
    }


    pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, minutes: i32) -> i32 {
        let (mut j, mut sum, mut other, mut max) = (0, 0, 0, 0);
        for i in 0..grumpy.len() {
            other += customers[i] * (1 - grumpy[i]);
            sum += customers[i] * grumpy[i];
            while j as i32 <= i as i32 - minutes { sum -= customers[j] * grumpy[j]; j += 1 }
            max = max.max(sum)
        }; max + other
    }

20.06.2024

1552. Magnetic Force Between Two Balls medium blog post substack youtube 2024-06-20_06-26_1.webp

Join me no Telegram

https://t.me/leetcode_daily_unstoppable/645

Problem TLDR

Max shortest distance between m positions #medium #binary_search

Intuition

In a space of growing shortest distance we move from impossible to possible place m positions. Is Binary Search possible?

Let’s try in example to check in a single pass count how many buckets we could place with given shortest distance = 2:

    // 1 2 3 4 5 6 7 8    m=4
    // * *   * * * * *
    //   ^   ^   ^   ^
    // ^     ^   ^   ^

As we can see, two ways of placing possible, but there is no difference between choosing position 1 or 2, so we can take positions greedily.

Approach

  • we can skip using a separate variable for max, but in the interview it is better to use explicitly

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


    fun maxDistance(position: IntArray, m: Int): Int {
        position.sort()
        var lo = 0; var hi = Int.MAX_VALUE
        while (lo <= hi) {
            val mid = lo + (hi - lo) / 2
            var count = 0; var next = 1
            for (p in position) 
                if (p >= next) { count++; next = p + mid }
            if (count >= m) lo = mid + 1 else hi = mid - 1
        }
        return hi
    }


    pub fn max_distance(mut position: Vec<i32>, m: i32) -> i32 {
        position.sort_unstable(); let (mut lo, mut hi) = (0, i32::MAX);
        while lo <= hi {
            let mid = lo + (hi - lo) / 2;
            let (mut count, mut next) = (0, 1);
            for &p in &position { if p >= next { count += 1; next = p + mid }}
            if count >= m { lo = mid + 1 } else { hi = mid - 1 }
        }; hi
    }

19.06.2024

1482. Minimum Number of Days to Make m Bouquets medium blog post substack youtube 2024-06-19_06-00_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/644

Problem TLDR

Min days to take m k-subarrays #medium #binary_search

Intuition


    //   1 10  3 10  2         m=3 k=1
    //   1
    //               2
    //         3
    //     10    10

    //   7  7  7  7 12  7  7   m=2 k=3
    //  [7  7  7] 7     7  7   +1
    //           [  12   ]     +2

We can binary search in space of days as function grows from not possible to possible with increase of days.

Approach

Don’t forget the -1 case.

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


    fun minDays(bloomDay: IntArray, m: Int, k: Int): Int {
        var lo = 0; var hi = bloomDay.max(); var min = Int.MAX_VALUE
        while (lo <= hi) {
            val mid = lo + (hi - lo) / 2
            var curr = 0; var count = 0
            for (d in bloomDay) {
                if (d > mid) curr = 0 else curr++
                if (curr == k) { curr = 0; count++ }
            }
            if (count >= m) { hi = mid - 1; min = min(min, mid) }
            else lo = mid + 1
        }
        return if (min == Int.MAX_VALUE) -1 else min
    }


    pub fn min_days(bloom_day: Vec<i32>, m: i32, k: i32) -> i32 {
        let (mut lo, mut hi, mut min) = (0, *bloom_day.iter().max().unwrap(), i32::MAX);
        while lo <= hi {
            let (mid, mut curr, mut count) = (lo + (hi - lo) / 2, 0, 0);
            for &d in &bloom_day {
                curr = if d > mid { 0 } else { curr + 1 };
                if curr == k { curr = 0; count += 1 }
            }
            if count >= m { hi = mid - 1; min = min.min(mid) }
            else { lo = mid + 1 }
        }
        if min == i32::MAX { -1 } else { min }
    }

18.06.2024

826. Most Profit Assigning Work medium blog post substack youtube 2024-06-18_07-15_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/643

Problem TLDR

Max profit by assigning [profit, difficulty] to workers any times #medium #sorting #greedy

Intuition

Let’s start with sorting worker and difficulty.

The greedy algorithm:

  • take least able worker
  • take all jobs that he able to work with
  • choose maximum profit job
    //  2  4  6  8 10       4 5 6 7
    // 10 20 30 40 50       a b c d
    //  a  a  
    //  b  b  
    //  c  c  c
    //  d  d  d

    // 68 35 52 47 86          92 10 85 84 82
    // 67 17  1 81  3

    // 35 47 52 68 86          10 82 84 85 92
    // 17 81  1 67  3              d
    //  i              max = 17
    //     i           max = 81
    //        i        max = 81
    //          i      68 < 82, max = 81, use 81
    //                               d = 84, use 81
    //                                  d = 85, use 81
    //                                     d = 92
    //              i  max = 81            use 81

Approach

  • pay attention that we can reuse jobs, otherwise we would have to use the PriorityQueue and poll each taken job

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(n)\)

Code


    fun maxProfitAssignment(difficulty: IntArray, profit: IntArray, worker: IntArray): Int {
        val inds = profit.indices.sortedBy { difficulty[it] }
        var maxProfit = 0
        var i = 0
        return worker.sorted().sumBy { d ->
            while (i < inds.size && difficulty[inds[i]] <= d) 
                maxProfit = max(maxProfit, profit[inds[i++]])
            maxProfit
        }
    }


    pub fn max_profit_assignment(difficulty: Vec<i32>, profit: Vec<i32>, mut worker: Vec<i32>) -> i32 {
        let (mut i, mut res, mut max, mut inds) = (0, 0, 0, (0..profit.len()).collect::<Vec<_>>());
        worker.sort_unstable(); inds.sort_unstable_by_key(|&i| difficulty[i]);
        for d in worker {
            while i < inds.len() && difficulty[inds[i]] <= d { max = max.max(profit[inds[i]]); i += 1 }
            res += max
        }; res
    }

17.06.2024

633. Sum of Square Numbers medium blog post substack youtube 2024-06-17_05-53.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/642

Problem TLDR

Is c sum of squares? #medium #binary_search

Intuition

From simple brute force of 0..c for a and b we can do the following optimizations:

  • use sqrt upper bound O(n^2) -> O((sqrt(n))^2)
  • notice that sum function grows linearly and we can do a Binary Search of c in it O((sqrt(n))^2) -> O(sqrt(n)log(n))
  • the trickiest part: a and b can themselves be the upper and lower bounds -> O(sqrt(n))

Approach

Let’s implement both solutions.

Complexity

  • Time complexity: \(O(sqrt(n)log(n))\) and \(O(sqrt(n))\)

  • Space complexity: \(O(1)\)

Code


    fun judgeSquareSum(c: Int): Boolean {
        val s = Math.sqrt(c.toDouble()).toLong()
        for (a in 0..s) {
            var lo = 0L; var hi = s
            while (lo <= hi) {
                val mid = lo + (hi - lo) / 2
                val sum = a * a + mid * mid 
                if (sum == c.toLong()) return true
                if (sum > c.toLong()) hi = mid - 1 
                else lo = mid + 1
            }
        }
        return false
    }


    pub fn judge_square_sum(c: i32) -> bool {
        let (mut lo, mut hi) = (0u64, (c as f64).sqrt() as u64);
        while lo <= hi {
            let sum = lo * lo + hi * hi;
            if sum == c as u64 { return true }
            if sum > c as u64 { hi -= 1 } else { lo += 1 }
        }; false
    }

16.06.2024

330. Patching Array hard blog post substack youtube 2024-06-16_06-59_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/641

Problem TLDR

Insertions to make subsets sums fill 1..n #hard

Intuition

The hard part for me was to understand range filling law: if range [1..x] is filled, then to fill range [1..x+x] we can add just one number x: it will add all the range of numbers: 1+x, 2+x, 3+x ... x+x

With this in mind, let’s explore example of how to fill the range:

    // 1 5 10      n=20
    // sums = 1, 5, 10, 1+5,1+10,5+10,1+5+10
    // 1 2 3 9
    // 1        [1..1]
    //   2      [..1+2] = [..3]
    //     3    [..3+3] = [..6]
    //       9  9>6+1, 7..9 -> 7 -> [..6+7]= [..13]
    //          [..13+9] = [..22]
    // 1 2 10 20    n=46
    // 1        ..1
    //   2      ..3
    //     10   10>4, ..3+4=..7
    //          10>8, ..7+8=..15
    //          ..15+10=..25

When we reach the number 9, we see the gap between the rightmost border 6 and 9, so we fill it with the next number after border 7. After this operation, the filled range becomes [1..6+7] and we can take the number 9.

Approach

Look for the tips in the discussion section.

Complexity

  • Time complexity: \(O(mlog(n))\), each time we doubling the border, so it takes log(n)

  • Space complexity: \(O(1)\)

Code


    fun minPatches(nums: IntArray, n: Int): Int {
        var count = 0; var border = 0L; var i = 0
        while (border < n) {
            if (i < nums.size && nums[i] <= border + 1) {
                border += nums[i]
                i++
            } else {
                border += border + 1
                count++
            }
        }
        return count
    }


    pub fn min_patches(nums: Vec<i32>, n: i32) -> i32 {
        let (mut border, mut i, mut cnt) = (0, 0, 0);
        while border < n as _ {
            if i < nums.len() && nums[i] as u64 <= border + 1 {
                border += nums[i] as u64;
                i += 1
            } else {
                border += border + 1;
                cnt += 1
            }
        }; cnt
    }

15.06.2024

502. IPO hard blog post substack youtube 2024-06-15_06-36_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/640

Problem TLDR

Max capital by choosing k jobs with profits[] & capital[] given w on start #hard #heap

Intuition

Let’s observe how this works:

    // profits        capital
    // 2 3 4 5 6      1 2 0 3 3      w = 0   k = 3
    // 1 1 4 2 3
    // `cap` only increases

We can choose from a bucket of jobs, each must have capital <= current money. After each job done our money will only grow, and the bucket will expand. And to choose optimally, just take max capital job.

The growing sorted bucket can be done with heap. It is evident that the bucket must take a new job with the smalled capital first, so sort by capital initially.

Approach

  • note that heap in Kotlin is a min-heap; in Rust is a max-heap

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(n)\)

Code


    fun findMaximizedCapital(k: Int, w: Int, profits: IntArray, capital: IntArray): Int {
        val inds = profits.indices.sortedBy { capital[it] }; val pq = PriorityQueue<Int>()
        var cap = w; var j = 0
        repeat (k) {
            while (j < inds.size && capital[inds[j]] <= cap) pq += -profits[inds[j++]]
            cap -= pq.poll() ?: 0
        }
        return cap
    }


    pub fn find_maximized_capital(k: i32, w: i32, profits: Vec<i32>, capital: Vec<i32>) -> i32 {
        let mut inds: Vec<_> = (0..profits.len()).collect(); inds.sort_by_key(|&i| capital[i]);
        let (mut cap, mut bh, mut j) = (w, BinaryHeap::new(), 0);
        for _ in 0..k {
            while j < inds.len() && capital[inds[j]] <= cap { bh.push(profits[inds[j]]); j += 1 }
            cap += bh.pop().unwrap_or(0)
        }; cap
    }

14.06.2024

945. Minimum Increment to Make Array Unique medium blog post substack youtube 2024-06-14_06-25_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/639

Problem TLDR

Min increments to make items unique #medium

Intuition

Let’s observe an example.

    // 1 2 2         delta   diff
    //   i           0       1
    //     i         1       0
    //
    // 1 1 2 2 3 7
    //   i           1       0
    //     i         1       1
    //       i       2       0
    //         i     2       1
    //           i   0       4
    //              (2 - (4-1))

First, sort, then maintain the delta:

  • increase if there is a duplicate
  • decrease by adjucent items diff

Approach

Let’s use iterators: windowed, sumOf.

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\), but O(n) for sorted in Kotlin

Code


    fun minIncrementForUnique(nums: IntArray): Int {
        var delta = 0
        return nums.sorted().windowed(2).sumOf { (a, b) ->
            if (a < b) delta = max(0, delta + a - b + 1) else delta++
            delta
        }
    }


    pub fn min_increment_for_unique(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable(); let mut delta = 0;
        nums[..].windows(2).map(|w| {
            delta = if w[0] < w[1] { 0.max(delta + w[0] - w[1] + 1) } else { delta + 1 };
            delta
        }).sum()
    }

13.06.2024

2037. Minimum Number of Moves to Seat Everyone easy blog post substack youtube 2024-06-13_06-42_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/638

Problem TLDR

Sum of diffs of sorted students and seats #easy

Intuition

Deduce the intuition from the problem examples: the optimal solution is to take difference between sorted seats and students greedily.

Approach

Let’s use some languages iterators:

  • Kotlin: sorted, zip, sumOf
  • Rust: iter, zip, sum

Complexity

  • Time complexity: \(O(nlogn)\)

  • Space complexity: \(O(n)\) for Kotlin, O(1) for Rust solution

Code


    fun minMovesToSeat(seats: IntArray, students: IntArray) =
        seats.sorted().zip(students.sorted()).sumOf { (a, b) -> abs(a - b) }



    pub fn min_moves_to_seat(mut seats: Vec<i32>, mut students: Vec<i32>) -> i32 {
        seats.sort_unstable(); students.sort_unstable();
        seats.iter().zip(students).map(|(a, b)| (a - b).abs()).sum()
    }

12.06.2024

75. Sort Colors medium blog post substack youtube 2024-06-12_08-17_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/637

Problem TLDR

Sort 012 array #medium

Intuition

The simple solution is to just counting sort. However, we can do one pass solution - use zeros and twos zones and fill them:

    // 1 2 0
    // z   t
    // i
    //   i
    //   0 2
    //   t
    //     i
    // 2 1 2
    // z   t
    // i
    //   t
    //   i

The corner case is when 2 and 0 must be swapped before next i. One way is to write if (nums[i] == 2) two--, another way is to not increment i when 2 swapped.

Approach

Let’s implement both solutions.

  • Slice.fill in Rust helps

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun sortColors(nums: IntArray): Unit {
        var zero = 0; var two = nums.lastIndex; var i = 0
        while (i <= two)
            if (nums[i] < 1) {
                nums[zero] = nums[i].also { nums[i++] = nums[zero++] }
            } else if (nums[i] > 1) {
                nums[two] = nums[i].also { nums[i] = nums[two--] }
            } else i++
        }


    pub fn sort_colors(nums: &mut Vec<i32>) {
        let (mut cnt, mut j) = ([0, 0, 0], 0);
        for &n in &*nums { cnt[n as usize] += 1 }
        for i in 0..cnt.len() {
            nums[j..j + cnt[i]].fill(i as _);
            j += cnt[i]
        }
    }

11.06.2024

1122. Relative Sort Array easy blog post substack youtube 2024-06-11_07-08.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/636

Problem TLDR

Sort an array by the given order #easy

Intuition

Associate the arr2, then use it as key for sorting arr1. Another solution is to use the Counting Sort: count arr1, then first place arr2 values, decreasing cnt, and then place the remaining cnt.

Approach

  • there is a compareBy in Kotlin that can receive several comparators
  • or we can just use n + 1001 for this problem
  • notice .cloned() in Rust: it allows to use a value instead of pointer in unwrap_or

Complexity

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

  • Space complexity: \(O(m)\)

Code


    fun relativeSortArray(arr1: IntArray, arr2: IntArray) =
        arr2.withIndex().associate { (i, v) -> v to i }.let { inds ->
            arr1.sortedWith(compareBy({ inds[it] ?: 1001 }, { it }))
        }


    pub fn relative_sort_array(mut arr1: Vec<i32>, arr2: Vec<i32>) -> Vec<i32> {
        let mut inds = HashMap::new(); for i in 0..arr2.len() { inds.insert(arr2[i], i); }
        arr1.sort_unstable_by_key(|n| inds.get(n).cloned().unwrap_or(1001 + *n as usize));
        arr1
    }

10.06.2024

1051. Height Checker easy blog post substack youtube 2024-06-10_06-29_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/635

Problem TLDR

Count unsorted elements in array #easy

Intuition

We can use bucket sort to do this in O(n).

Approach

Let’s just use a simple sort to save the effort.

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(n)\)

Code


    fun heightChecker(heights: IntArray) = heights
        .toList().sorted().withIndex()
        .count { (i, h) -> h != heights[i] }


    pub fn height_checker(heights: Vec<i32>) -> i32 {
        let mut s = heights.clone(); s.sort_unstable();
        (0..s.len()).map(|i| (s[i] != heights[i]) as i32).sum()
    }

09.06.2024

974. Subarray Sums Divisible by K medium blog post substack youtube 2024-06-09_06-36_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/634

Problem TLDR

Count subarrays divisible by k #medium #hashmap

Intuition

Let’s observe an example:


    //   0 1 2  3  4 5
    //   4 5 0 -2 -3 1   s  k=5      sums    count
    //i                              0 -> 1
    //   i               4  4%5=4    4 -> 1
    //     i             9  9%5=4    4 -> 2  +1
    //       i           9  9%5=4    4 -> 3  +2
    //          i        7  7%5=2    2 -> 1
    //             i     4  4%5=4    4 -> 4  +3
    //               i   5  5%5=0    0 -> 2  +1

We can compute the running sum. Subarray sum can be computed from the previous running sum: sum[i..j] = sum[0..j] - sum[0..i]. Next, if sum is divisibile by k, then we can apply % operation rule: sum[i..j] % k = 0 = sum[0..j] % k - sum[0..i] % k, or in another words: sum[0..i] % k == sum[0..j] % k. So, we just need to keep track of all the remiders.

Corner case is when subarray is starts with first item, just make a sentinel counter for it: sums[0] = 1.

Approach

  • using iterators saves some lines of code
  • did you know about hashMapOf & HashMap::from ?

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(k)\)

Code


    fun subarraysDivByK(nums: IntArray, k: Int): Int {
        val sums = hashMapOf(0 to 1); var s = 0
        return (0..<nums.size).sumOf { i ->
            s = (s + nums[i] % k + k) % k
            val count = sums[s] ?: 0
            sums[s] = 1 + count
            count
        }
    }


    pub fn subarrays_div_by_k(nums: Vec<i32>, k: i32) -> i32 {
        let (mut sums, mut s) = (HashMap::from([(0, 1)]), 0);
        (0..nums.len()).map(|i| {
            s = (s + nums[i] % k + k) % k;
            let count = *sums.entry(s).or_default();
            sums.insert(s, 1 + count);
            count
        }).sum()
    }

08.06.2024

523. Continuous Subarray Sum medium blog post substack youtube 2024-06-08_07-51_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/633

Problem TLDR

Any subarray sum % k = 0 #medium #hashmap

Intuition

Let’s observe the problem examples:

    // 5 0 0 0       k = 3   true?? --> [0 0] % 3 = 0
    //
    // 23   2   6   2   5    k = 8
    // 23                    23 % 8 = 0
    //     25                25 % 8 = 7
    //         31            31 % 8 = 7  (31-25)%8=31%8-25%8=0
    //             33
    //                 38
    //
    // 0 1 0 3 0 4 0 4 0  k = 7
    // 23 2   4  6  6
    // 23
    //    25
    //       29
    //          35

We can’t just use two pointers here, because every subarray to the left can give the result in the future. However, we can store subarray sums. But what to do with them next? If we look at example 23 2 6 2 5, k = 8, subarray [2 6] is good, and it is made from sums 31 and 23: 31 - 23 = 8 -> (31 - 23) % k = 8 % k -> 31 % k - 23 % k = k % k = 0 -> 31 % k == 23 % k. So, our subarray sums % k must be equal for subarray between them be good.

The corener cases:

  • For the case 5 0 0 0 result is true because there is [0, 0] subarray which gives 0 % k = 0. That mean, we should store the first occurence index to check the length later.
  • For the case 2 6, k = 8 we must consider entire array, so we must store the first occurence of 0 at position -1.

Approach

  • getOrPut and entry.or_insert in Kotlin & Rust saves us some keystrokes

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun checkSubarraySum(nums: IntArray, k: Int): Boolean {
        val sums = HashMap<Int, Int>().apply { put(0, -1) }
        var sum = 0
        return nums.withIndex().any { (i, n) ->
            sum += n
            sums.getOrPut(sum % k) { i } < i - 1
        }
    }


    pub fn check_subarray_sum(nums: Vec<i32>, k: i32) -> bool {
        let (mut s, mut sums) = (0, HashMap::new()); sums.insert(0, -1);
        (0..nums.len()).any(|i| {
            s += nums[i];
            1 + *sums.entry(s % k).or_insert(i as _) < i as _
        })
    }

07.06.2024

648. Replace Words medium blog post substack youtube 2024-06-07_07-09_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/632

Problem TLDR

Replace words with suffixes from dictionary #medium #trie

Intuition

Walk through the word and check if the suffix is in the dictionary. To speed up this we can use a HashMap or a Trie.

Approach

Let’s use both HashMap and Trie. HashMap code is shorter but slower.

Complexity

  • Time complexity: \(O(n)\), O(nw^2) for HashMap solution, as we rebuilding each suffix in the word of w length

  • Space complexity: \(O(d + w)\)

Code


    fun replaceWords(dictionary: List<String>, sentence: String): String {
        class Trie(var word: Int = -1): HashMap<Char, Trie>()
        val trie = Trie()
        for ((i, r) in dictionary.withIndex()) {
            var t = trie
            for (c in r) t = t.getOrPut(c) { Trie() }
            t.word = i
        }
        return sentence.split(" ").map {
            var t = trie
            for (c in it) {
                if (t.word >= 0) break
                t = t[c] ?: break
            }
            dictionary.getOrNull(t.word) ?: it
        }.joinToString(" ")
    }


    pub fn replace_words(dictionary: Vec<String>, sentence: String) -> String {
        let set = dictionary.into_iter().collect::<HashSet<_>>();
        sentence.split(" ").map(|s| {
            let mut w = String::new();
            for c in s.chars() {
                w.push(c);
                if set.contains(&w) { break }
            }; w
        }).collect::<Vec<_>>().join(" ")
    }

06.06.2024

846. Hand of Straights medium blog post substack youtube 2024-06-06_07-37_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/631

Problem TLDR

Can array be split into consecutive groups #medium #heap #treemap

Intuition

Let’s sort array and try to brute-force solve it with bare hands:

    // 1 2 3 6 2 3 4 7 8

    // 0 1 2 3 4 5 6 7 8
    // 1 2 2 3 3 4 6 7 8
    // 1 2   3
    //     2   3 4
    //             6 7 8

    // 1 2 3 4 5 6       2

    // 1 2 3             1

The naive implementation is accepted: take first not used and mark all consequtive until groupSize reached. This solution will take O(n^2) time, but it is fast as arrays are fast when iterated forward.

To improve we can use PriorityQueue: do the same algorithm, skip the duplicated, then add them back. This will take O(nlogn + gk), where g is groups count, and k is duplicates count.

We can improve event more with TreeMap: keys are the hands, values are the counters, subtract entire count.

Approach

Let’s implement both PriorityQueue and TreeMap solutions.

Complexity

  • Time complexity: \(O(nlogn)\)

  • Space complexity: \(O(n)\)

Code


    fun isNStraightHand(hand: IntArray, groupSize: Int): Boolean {
        val map = TreeMap<Int, Int>() 
        for (h in hand) map[h] = 1 + (map[h] ?: 0)
        for ((h, count) in map) if (count > 0)
            for (x in h..<h + groupSize) {
                if ((map[x] ?: 0) < count) return false
                map[x] = map[x]!! - count
            }
        return true
    }


    pub fn is_n_straight_hand(hand: Vec<i32>, group_size: i32) -> bool {
        let mut bh = BinaryHeap::new(); for &h in &hand { bh.push(-h); }
        while let Some(start) = bh.pop() {
            let mut tmp = vec![];
            for i in -start + 1..-start + group_size {
                while bh.len() > 0 && -bh.peek().unwrap() < i { tmp.push(bh.pop().unwrap()); }
                if bh.is_empty() || -bh.peek().unwrap() > i { return false }
                bh.pop();
            }
            for &h in &tmp { bh.push(h); }
        }; true
    }

05.06.2024

1002. Find Common Characters easy blog post substack youtube 2024-06-05_07-42.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/629

Problem TLDR

Common letters in words #easy

Intuition

We can count frequencies, then choose minimums for each char. Or do the reverse: for each char count minimum count in all words.

Approach

The frequencies code is faster, but the opposite approach is less verbose.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\), but can be O(n) to hold the result

Code


    fun commonChars(words: Array<String>) = 
        ('a'..'z').map { c -> 
            List(words.minOf { it.count { it == c } }) { "$c" }
        }.flatten()


    pub fn common_chars(words: Vec<String>) -> Vec<String> {
        ('a'..='z').map(|c| {
            let min_cnt = words.iter().map(|w| 
                w.chars().filter(|a| *a == c).count()).min();
            vec![format!("{c}"); min_cnt.unwrap_or(0)]
        }).flatten().collect()
    }

04.06.2024

409. Longest Palindrome easy blog post substack youtube 2024-06-04_07-01_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/628

Problem TLDR

Max palindrome length from chars #easy

Intuition

Don’t mistaken this problem with find the longest palindrome, because this time we need to build one. (I have spent 5 minutes solving the wrong problem)

To build a palindrome, we need even counts of chars and at most one odd.

Approach

  • we can use groupBy, sumBy and any
  • f & 1 operation will convert any odd number into 1

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\), but O(n) for the groupBy solution, which can be optimized

Code


    fun longestPalindrome(s: String): Int =
        s.groupBy { it }.values.run {
            2 * sumBy { it.size / 2 } + 
            if (any { it.size % 2 > 0 }) 1 else 0
        }


    pub fn longest_palindrome(s: String) -> i32 {
        let (mut freq, mut res, mut o) = (vec![0;128], 0, 0);
        for b in s.bytes() { freq[b as usize] += 1 }
        for f in freq { o |= f & 1; res += f / 2 }
        2 * res + o
    }

03.06.2024

2486. Append Characters to String to Make Subsequence medium blog post substack youtube 2024-06-03_09-03_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/627

Problem TLDR

Min diff to make t substring of s #medium

Intuition

Try to first solve it with bare hands: take the s string and walk over the chars, simultaneously adjusting the t char position:

s        t
abcccccd abdd
i      . j
 i     .  j
  i    .  j
   i   .  j
    i  .  j
     i .  j
      i.  j
       i   j

Looking at this example, the algorithm is clear: search for the next t[j] char in s.

Approach

  • save three lines of code with getOrNull ?: return in Kotlin
  • walking over bytes is only valid for ascii chars (Rust)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun appendCharacters(s: String, t: String): Int {
        var j = 0
        for (c in s) if (c == t.getOrNull(j) ?: return 0) j++
        return t.length - j
    }


    pub fn append_characters(s: String, t: String) -> i32 {
        let mut tb = t.bytes().peekable();
        t.len() as i32 - s.bytes().map(|b| {
            (b == tb.next_if_eq(&b).unwrap_or(0)) as i32
        }).sum::<i32>()
    }

02.06.2024

344. Reverse String easy blog post substack youtube 2024-06-02_08-19.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/626

Problem TLDR

Reverse an array #easy

Intuition

We can use two pointers or just a single for-loop until the middle.

Approach

  • Careful with the corner case: exclude the middle for the even size
  • try to use built-in functions

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun reverseString(s: CharArray) = s.reverse()


    pub fn reverse_string(s: &mut Vec<char>) {
        s.reverse()
    }

01.06.2024

3110. Score of a String easy blog post substack youtube 2024-06-01_08-37.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/625

Problem TLDR

Sum(abs(window)) #easy

Intuition

Just do what is asked. Use iterators preferably.

Approach

Some notes to Rust:

  • as_bytes gives a slice of [u8] and slices have a window
  • there is an abs_diff, can save some symbols

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun scoreOfString(s: String): Int = 
        s.windowed(2).sumBy { abs(it[0] - it[1]) }
        


    pub fn score_of_string(s: String) -> i32 {
        s.as_bytes().windows(2)
        .map(|x| x[0].abs_diff(x[1]) as i32).sum()
    }

31.05.2024

260. Single Number III medium blog post substack youtube 2024-05-31_08-32.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/623

Problem TLDR

Two not duplicated numbers from array #medium #bit_manipulation

Intuition

The first idea is to xor the array, xor[..] = a ^ b. However from that point there is no clear path to what can be done next.

(I personally gave up and go to the discussion section)

The hint: each 1 bit in the xor result of a ^ b means that in that bit a is different than b. We can split all the numbers in array by this bit: one group will contain a and some duplicates, another group will contain b and some other remaining duplicates. Those duplicates can be xored and a and b distilled.

    // a b cc dd   xor[..] = a ^ b
    // 1 2 1 3 2 5
    // 1  01
    // 2  10
    // 1  01
    // 3  11
    // 2  10
    // 5 101
    //
    // x 110
    //     *   (same bits in a and b)
    //    *    1 1 5       vs   2 3 2      
    //   *     1 2 1 3 2   vs   5

Approach

Some tricks:

  • first and find operators in Kotlin and Rust
  • conversion of boolean to usize in Rust

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun singleNumber(nums: IntArray): IntArray {
        var x = 0; for (n in nums) x = x xor n
        return (0..31).first { x and (1 shl it) != 0 }.let { 
            var a = 0; var b = 0
            for (n in nums) if ((n and (1 shl it)) != 0)
                a = a xor n else b = b xor n
            intArrayOf(a, b)
        }
    }


    pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
        let (mut x, mut r) = (0, vec![0, 0]); for &n in &nums { x ^= n }
        let bit = (0..32).find(|&bit| x & (1 << bit) != 0).unwrap();
        for &n in &nums { r[(n & (1 << bit) != 0) as usize] ^= n }; r
    }

30.05.2024

1442. Count Triplets That Can Form Two Arrays of Equal XOR medium blog post substack youtube 2024-05-30_07-53.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/622

Problem TLDR

Number (i,j,k) where xor arr[i..j] = xor arr[j..k] #medium #bit_manipulation

Intuition

Start with the brute-force solution, it will be accepted.

                for (j in i + 1..k) 
                    a = a ^ arr[j]
                    b = ikXor ^ a
                    if (a == b) res++

Some optimizations:

  • we have precomputed total xor between i..k and now if a = xor [i..j - 1] then b = xor [i..k] ^ a.

Let’s inline a and b in the if (a == b) equation:

if (a ^ arr[j] == ikXor ^ (a ^ arr[j])) ...

We can safely remove ^ a ^ arr[j] from the left and the right parts, leaving it like if (0 == ikXor). As this now independent of j, we can just collapse the third loop into ` if (0 == ikXor) res += k - i`.

(There is one more optimization possible: store xors prefixes count in a HashMap, this will reduce the time to O(n))

Approach

Using sumOf and .map().sum() helps to reduce some lines of code.

Complexity

  • Time complexity: \(O(n^2)\)

  • Space complexity: \(O(1)\)

Code


    fun countTriplets(arr: IntArray): Int =
        arr.indices.sumOf { i ->
            var ikXor = 0
            (i..<arr.size).sumOf { k -> 
                ikXor = ikXor xor arr[k]
                if (0 == ikXor) k - i else 0
            }
        }


    pub fn count_triplets(arr: Vec<i32>) -> i32 {
        (0..arr.len()).map(|i| {
            let mut ik_xor = 0;
            (i..arr.len()).map(|k| {
                ik_xor ^= arr[k];
                if ik_xor == 0 { k - i } else { 0 }
            }).sum::<usize>()
        }).sum::<usize>() as _
    }

29.05.2024

1404. Number of Steps to Reduce a Number in Binary Representation to One medium blog post substack youtube 2024-05-29_09-04.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/621

Problem TLDR

Steps even/2, odd+1 to make binary s to 1 #medium

Intuition

We can just implement what is asked recursively passing a new string each time. The more interesting and effective solution is to iterate from the end and try to count operations on the fly:

  • calculate current and carry
  • apply extra operation if current is odd and do extra increase for carry

Approach

Let’s minify the code using the math tricks.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun numSteps(s: String): Int {
        var carry = 0
        return (s.lastIndex downTo 1).sumOf { i ->
            val curr = s[i] - '0' + carry
            carry = curr / 2 + curr % 2
            1 + curr % 2
        } + carry
    }


    pub fn num_steps(s: String) -> i32 {
        let (mut carry, sb) = (0, s.as_bytes());
        (1..s.len()).rev().map(|i| {
            let curr = sb[i] as i32 - b'0' as i32 + carry;
            carry = curr / 2 + curr % 2;
            1 + curr % 2
        }).sum::<i32>() + carry
    }

28.05.2024

1208. Get Equal Substrings Within Budget medium blog post substack youtube 2024-05-28_07-23.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/620

Problem TLDR

Max substring sum(abs(s[..] - t[..])) < maxCost #medium #sliding_window

Intuition

There is a known Sliding Window technique to find any max or min in a substring or subarray (contiguous part): use one pointer to take one more element on the right border, compute the result, then if there are some conditions, move the left border and recompute the result again. This will find the maximum while not checking every possible subarray: because we check all subarrays ends borders and we drop every start border that are clearly out of scope by max function.

Approach

  • maxOf in Kotlin and .map().max() in Rust will help to save some lines of code

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun equalSubstring(s: String, t: String, maxCost: Int): Int {
        var i = 0; var cost = 0
        return s.indices.maxOf { 
            cost += abs(s[it] - t[it])
            if (cost > maxCost) cost -= abs(s[i] - t[i++])
            it - i + 1
        }
    }


    pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
        let (mut i, mut cost, sb, tb) = (0, 0, s.as_bytes(), t.as_bytes());
        (0..s.len()).map(|j| {
            cost += (sb[j] as i32 - tb[j] as i32).abs();
            if cost > max_cost { cost -= (sb[i] as i32 - tb[i] as i32).abs(); i += 1 }
            j - i + 1
        }).max().unwrap() as _
    }

27.05.2024

1608. Special Array With X Elements Greater Than or Equal X easy blog post substack youtube 2024-05-27_07-27.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/619

Problem TLDR

Count of more or equal nums[i] equal itself #easy

Intuition

Star with brute force, the n is in range 0..1000, try them all, and for each count how many numbers are nums[i] >= n.

This will pass the checker. Now time to optimize. If we sort the nums we can optimize the nums[i] >= n, as n only grows up so the i. We can start with the previous i next time. Another optimizations, there are no more than nums.size count possible, so n’s range is 0..nums.size inclusive.

Approach

Let’s write non-optimal one-liner in Kotlin, and more robust solution in Rust.

Complexity

  • Time complexity: \(O(nlogn)\) and \(O(n^2)\)

  • Space complexity: \(O(1)\)

Code


    fun specialArray(nums: IntArray): Int = (0..nums.size)
        .firstOrNull { n -> n == nums.count { it >= n }} ?: -1


    pub fn special_array(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable(); let (mut n, mut i) = (0, 0);
        for n in 0..=nums.len() {
            while i < nums.len() && nums[i] < n as i32 { i += 1 }
            if n == nums.len() - i { return n as i32 }
        }; -1
    }

26.05.2024

552. Student Attendance Record II hard blog post substack youtube

2024-05-26_10-18.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/618

Problem TLDR

N times: A -> LP, L -> AP, P -> AL, at most one A, no LLL #hard #dynamic_programming

Intuition

The key to solving this is to detect each kind of a unique generator. From this example we can separate several unique rules - a, l, p, al, ll, all:

    // 1 -> A L P
    //      good = 3
    //      a = 1 l = 1 p = 1
    // 2 -> 
    //    a A -> AP AL (AA)
    //    l L -> LP LL LA
    //    p P -> PP PL PA
    //      good = 8
    //      a = 3    l = 1    p = 2   al = 1   ll = 1 
    //    a AP     p PL     l LP    a AL     l LL
    //    l LA              p PP    
    //    p PA
    //      
    // 3 -> 
    //   a  AP -> APP APL(APA)
    //  al  AL -> ALP ALL(ALA)
    //   p  LP -> LPP LPL LPA
    //  ll  LL -> LLP(LLL)LLA
    //   a  LA -> LAP LAL(LAA)
    //   p  PP -> PPP PPL PPA
    //   l  PL -> PLP PLL PLA
    //   a  PA -> PAP PAL(PAA)
    //      good = 19
    //      a = 8    l = 2     p = 4    al = 3    ll = 1    all = 1
    //   a  APP    p LPL    p  LPP    a APL     l PLL    al ALL
    //  al  ALP    p PPL    ll LLP    a LAL   
    //  ll  LLA             p  PPP    a PAL
    //   a  LAP             l  PLP
    //   p  PPA        
    //   l  PLA
    //   a  PAP
    //   p  LPA   
    //
    //   a1 = (a + l + p + al + ll + all)
    //                     p1 = (p + l + ll)
    //                                         ll = l
    //            l = p
    //                                                  all = al
    //                               al = a

These rules can be described as the kingdoms where each have a unique properties:

  • a - the only one 'a' possible kingdom rule, it will not allow any other a to happen
  • l - the ending with 'l' rule, will generate ll in the next round
  • p - the I am a simple guy here, abide all the rules rule
  • al - the busy guy, he will make all in the next round, also no a is allowed next
  • ll - the guard, will not permit l in the next round
  • all - the serial killer, no l and no a will survive next round

After all the rules are detected, we have to notice the pattern of how they pass to the next round.

Approach

Somebody find this problem easy, but I have personally failed to detect those rules under 1.5 hours mark.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun checkRecord(n: Int): Int {
        val m = 1_000_000_007L; var a = 0L; var l = 0L; 
        var p = 1L; var ll = 0L; var al = 0L; var all = 0L
        for (i in 0..n) {
            val p1 = (p + l + ll) % m
            val a1 = (a + l + p + al + ll + all) % m
            ll = l; l = p; p = p1; all = al; al = a; a = a1
        }
        return a.toInt()
    }


    pub fn check_record(n: i32) -> i32 {
        let (m, mut a, mut l) = (1_000_000_007i64, 0, 0); 
        let (mut p, mut ll, mut al, mut all) = (1, 0, 0, 0);
        for i in 0..=n {
            let p1 = (p + l + ll) % m;
            let a1 = (a + l + p + al + ll + all) % m;
            ll = l; l = p; p = p1; all = al; al = a; a = a1
        }; a as i32
    }

25.05.2024

140. Word Break II hard blog post substack youtube 2024-05-25_10-17.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/617

Problem TLDR

All string splits with dictionary #hard #dfs #dynamic_programming

Intuition

There are several ways to attack this problem: we can make a Trie or HashSet from the dictionary, then just walk the string for all suffixes and use a Dynamic Programming formula for the answer dp[s] = prefix + dp[s - prefix].

Approach

Let’s try to be clever and reuse the method signature with the cost of performance loss of not using memoization.

Complexity

  • Time complexity: \(O(ws^s^2)\), the recursion depth is in the worst case aaaaa is s, at each level we try s times and in each successfull prefix iterating over 2^s next results each prepending s symbols. With memoization it is \(O(w2^s)\). With helper function and the single set precalculation is \(O(w + 2^s)\).

  • Space complexity: \(O(ws + 2^s)\), recursion depth is s, each level holds w copy and 2^s result.

Code


    fun wordBreak(s: String, wordDict: List<String>): List<String> = buildList {
        val set = wordDict.toSet()
        for (i in s.indices) if (s.take(i + 1) in set) 
            if (i == s.lastIndex) add(s) else
                for (next in wordBreak(s.drop(i + 1), wordDict)) 
                    add("${ s.take(i + 1) } $next")
    }


    pub fn word_break(s: String, word_dict: Vec<String>) -> Vec<String> {
        let (mut res, set) = (vec![], word_dict.iter().map(|w| w.as_str()).collect::<HashSet<_>>());
        for i in 0..s.len() { let w = &s[0..=i]; if set.contains(w) {
            if i == s.len() - 1 { res.push(w.to_string()) } else {
                for n in Self::word_break(s[i + 1..].to_string(), word_dict.clone()) {
                    res.push(format!("{} {}", w, n).to_string())
                }}
        }}; res
    }

24.05.2024

1255. Maximum Score Words Formed by Letters hard blog post substack youtube 2024-05-24_08-45.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/612

Problem TLDR

Max score of words subset from letters #hard #backtracking #dfs

Intuition

This is just a mechanical backtracking problem: do a full Depth-First search over all subsets of words, and count max score.

We can precompute some things beforehead.

Approach

  • in Kotlin there is a .code field, use it
  • in Rust: use [0; 26] type, it is fast, also use slices, they are cheap and reduce code size

Complexity

  • Time complexity: \(O(2^n)\)

  • Space complexity: \(O(n)\)

Code


    fun maxScoreWords(words: Array<String>, letters: CharArray, score: IntArray): Int {
        val f = IntArray(26); for (c in letters) f[c.code - 'a'.code]++
        val wf = words.map { IntArray(26).apply { 
                for (c in it) this[c.code - 'a'.code]++ }}
        val ws = words.map { it.sumOf { score[it.code - 'a'.code] }}
        fun dfs(i: Int): Int = if (i < wf.size) max(dfs(i + 1),
            if ((0..25).all { wf[i][it] <= f[it] }) {
                for (j in 0..25) f[j] -= wf[i][j]
                ws[i] + dfs(i + 1).also { for (j in 0..25) f[j] += wf[i][j] }
            } else 0) else 0
        return dfs(0)
    }


    pub fn max_score_words(words: Vec<String>, letters: Vec<char>, score: Vec<i32>) -> i32 {
        let (mut f, mut wf, mut ws) = ([0; 26], vec![[0; 26]; words.len()], vec![0; words.len()]);
        for &c in letters.iter() { f[(c as u8 - b'a') as usize] += 1 }
        for (i, w) in words.iter().enumerate() {
            for b in w.bytes() { wf[i][(b - b'a') as usize] += 1; ws[i] += score[(b - b'a') as usize] }
        }
        fn dfs(f: &mut [i32; 26], ws: &[i32], wf: &[[i32; 26]]) -> i32 {
            if wf.len() > 0 { dfs(f, &ws[1..], &wf[1..]).max(
                if (0..25).all(|i| wf[0][i] <= f[i]) {
                    for i in 0..25 { f[i] -= wf[0][i] }
                    let next = ws[0] + dfs(f, &ws[1..], &wf[1..]);
                    for i in 0..25 { f[i] += wf[0][i] }; next
                } else { 0 }) } else { 0 }
        } dfs(&mut f, &ws, &wf)
    }

23.05.2024

2597. The Number of Beautiful Subsets medium blog post substack youtube 2024-05-23_09-05.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/611

Problem TLDR

Count subsets without k difference in them #medium #dfs #backtracking

Intuition

There are a DP solutions, but a simple brute-force backtracking is also works. Do a Depth-First search, check element (n-k) not added, add element, go deeper, remove element. To get the intuition about how to count subsets, consider this example:

    // 1 1 1 =(111)+(1)+(1)+(1)+(11)+(11)+(11)

For each subset of size n there are 2^n - 1 subsets. We can sum the on the finish line, or just add on the fly.

One way to optimize this is to use a HashMap and a counter instead of just list. Another optimization is a bitmask instead of list.

Approach

Some tricks here:

  • sorting to check just the lower num n - k
  • sign to shorten the if (size > ) 1 else 0
  • as i32 do the same in Rust
  • [i32] slice and [1..] next window without the index variable

Complexity

  • Time complexity: \(O(n2^n)\)

  • Space complexity: \(O(n)\)

Code



    fun beautifulSubsets(nums: IntArray, k: Int): Int {
        val curr = mutableListOf<Int>(); nums.sort()
        fun dfs(i: Int): Int = if (i < nums.size) {
                if ((nums[i] - k) in curr) 0 else {
                    curr += nums[i]; dfs(i + 1).also { curr.removeLast() }
                } + dfs(i + 1)
            } else curr.size.sign
        return dfs(0)
    }


    pub fn beautiful_subsets(mut nums: Vec<i32>, k: i32) -> i32 {
        let mut curr = vec![]; nums.sort_unstable();
        fn dfs(nums: &[i32], curr: &mut Vec<i32>, k: i32) -> i32 {
            if nums.len() > 0 {
                (if curr.contains(&(nums[0] - k)) { 0 } else {
                    curr.push(nums[0]); let r = dfs(&nums[1..], curr, k);
                    curr.pop(); r
                }) + dfs(&nums[1..], curr, k)
            } else { (curr.len() > 0) as i32 }
        } dfs(&nums[..], &mut curr, k)
    }

22.05.2024

131. Palindrome Partitioning medium blog post substack youtube 2024-05-22_09-02.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/610

Problem TLDR

All palindrome partitions #medium #dfs #dynamic_programming

Intuition

The backtracking solution is trivial: do a full Depth-First Search over indices, take substring start..i if it is a palindrome, collect at the end. We can also precalculate all palindromes in a dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]

Approach

However, there is a clever approach to reuse the existing method signature: we can define Dynamic Programming problem as a subproblem for the palindrome_substring + DP(rest of the string). Where + operation would include current palindrome substring in all the suffix’s solutions.

Given the problem size, let’s skip the memoization part to save lines of code (weird decision for the interview).

Complexity

  • Time complexity: \(O(2^n)\), the worst case is aaaaa all chars the same

  • Space complexity: \(O(2^n)\)

Code


    fun partition(s: String): List<List<String>> = buildList {
        for (i in s.indices) 
            if ((0..i).all { s[it] == s[i - it] })
                if (i < s.lastIndex) 
                    for (next in partition(s.drop(i + 1)))
                        add(listOf(s.take(i + 1)) + next)
                else add(listOf(s))
    }


    pub fn partition(s: String) -> Vec<Vec<String>> {
        let mut res = vec![];
        for i in 0..s.len() {
            if (0..=i).all(|j| s.as_bytes()[j] == s.as_bytes()[i - j]) {
                if i < s.len() - 1 {
                    for next in Self::partition(s[i + 1..].to_string()) {
                        res.push(vec![s[..=i].to_string()].into_iter().chain(next).collect())
                    }
                } else { res.push(vec![s.to_string()]) }
            }
        }; res
    }

21.05.2024

78. Subsets medium blog post substack youtube 2024-05-21_08-23.webp https://youtu.be/xRtcs1VgxXg

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/609

Problem TLDR

All subsets #medium #backtrack

Intuition

The are several ways to solve this:

  1. DFS with a single choice: take or leave. Effectively this is a 2 ways exploration with depth of n and n copy operations at each end, so O(2 + n)^n) = O(n^n).
  2. DFS with cycle from index so far until the end. The depth is the same n, however, it slighly more optimal, as we are skipping some go-in-depth invocations. The time complexity not changes.
  3. DP: res[i] = nums[i] added to each of res[i - 1]. Time complexity is the same, as res[i] hold all the results and we are iterating over.

Approach

Can you make it shorter?

Complexity

  • Time complexity: \(O(n^n)\)

  • Space complexity: \(O(n^n)\)

Code


    fun subsets(nums: IntArray): List<List<Int>> = buildList {
        add(listOf())
        for (n in nums) for (i in indices) add(get(i) + n)
    }


    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![vec![]; 1]; 
        for n in nums { for i in 0..res.len() {
            res.push(res[i].iter().chain([&n]).cloned().collect())
        }}; res
    }

20.05.2024

1863. Sum of All Subset XOR Totals easy blog post substack youtube 2024-05-20_08-11.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/608

Problem TLDR

Sum of subsets xors #easy #dfs #backtracking

Intuition

The problem size is small, only 12 items, we can brute-force the problem. One way is a bitmask from 0 to 2^12, then each time iterate over array and choose only set bits for indices. This will take O(n2^n) time and O(1) space. Another way is recursive backtracking: each time make a decision to take item or leave it, adding to the result in the end. This will take O(2^n) time and O(n) space for the recursion depth.

Approach

Backtracking code is shorter.

  • notice how slices are used in Rust

Complexity

  • Time complexity: \(O(2^n)\) two decision explorations are made n times

  • Space complexity: \(O(n)\) for the recursion depth

Code


    fun subsetXORSum(nums: IntArray): Int {
        fun dfs(i: Int, x: Int): Int = if (i < nums.size) 
            dfs(i + 1, x) + dfs(i + 1, x xor nums[i]) else x
        return dfs(0, 0)
    }


    pub fn subset_xor_sum(nums: Vec<i32>) -> i32 {
        fn dfs(n: &[i32], x: i32) -> i32 { if n.len() > 0 
            { dfs(&n[1..], x) + dfs(&n[1..], x ^ n[0]) } else { x }
        }
        dfs(&nums, 0)
    }

19.05.2024

3068. Find the Maximum Sum of Node Values hard blog post substack youtube 2024-05-19_11-13.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/607

Problem TLDR

Max sum after xor k any edges in a tree #hard #math

Intuition

Let’s just draw and try to build an intuition. 2024-05-19_09-10.webp 2024-05-19_09-21.webp We can cancel out xor if we apply an even number of times.

This is where I was stuck and gave up after trying to build the DP solution.

Now, the actual solution: we can cancel out all xor between any two nodes: a-b-c-d, a^k-b^k-c-d, a^k-b-c^k-d, a^k-b-c-d^k. Effectively, the task now is to do xor on all nodes where it gives us increase in the sum.

However, as xor must happen in pairs we still need to consider how many operations we do. For even just take the sum, but for odd there are two cases: flip one xor back, or do one extra xor (that’s why we use abs). To do the extra flip we must choose the minimum return of the value.

Approach

Spend at least 1 hour before giving up.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun maximumValueSum(nums: IntArray, k: Int, edges: Array<IntArray>): Long {
        var sum = 0L; var xorCount = 0; var minMax = Int.MAX_VALUE / 2
        for (n in nums) {
            sum += max(n, n xor k).toLong()
            if (n xor k > n) xorCount++
            minMax = min(minMax, abs((n xor k) - n))
        }
        return sum - minMax * (xorCount % 2)
    }


    pub fn maximum_value_sum(nums: Vec<i32>, k: i32, edges: Vec<Vec<i32>>) -> i64 {
        let (mut sum, mut cnt, mut min) = (0, 0, i32::MAX);
        for n in nums {
            sum += n.max(n ^ k) as i64;
            if n ^ k > n { cnt += 1 }
            min = min.min(((n ^ k) - n).abs())
        }; sum - (min * (cnt % 2)) as i64
    }

18.05.2024

979. Distribute Coins in Binary Tree medium blog post substack youtube 2024-05-18_09-23.webp https://youtu.be/-bec2qToKoM

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/606

Problem TLDR

Min moves to spread the coins across the tree #medium #dfs #tree

Intuition

Let’s observe some examples: 2024-05-18_08-32.webp Some observations:

  • each coin moves individually, even if we move 2 coins at once, it makes no difference to the total moves
  • eventually, every node will have exactly 1 coin We can use abstract flow:
  • 0 coins at leaves have flow = -1, because they are attracting coin
  • flow is accumulating from children to parent, so we can compute it independently for the left and right nodes
  • total moves count is sign-independent sum of total flow: we count both negative and positive moves

Approach

  • for Rust there is an interesting way to use Option in combinations with ? operation that will return None; it helps to reduce the code size

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\), for the recursion depth

Code


    fun distributeCoins(root: TreeNode?): Int {
        var res = 0 
        fun dfs(n: TreeNode?): Int = n?.run { 
          (dfs(left) + dfs(right) + `val` - 1).also { res += abs(it) }} ?: 0
        dfs(root)
        return res
    }


    pub fn distribute_coins(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, res: &mut i32) -> Option<i32> {
            let n = n.as_ref()?; let n = n.borrow();
            let flow = dfs(&n.left, res).unwrap_or(0) + dfs(&n.right, res).unwrap_or(0) + n.val - 1;
            *res += flow.abs(); Some(flow)
        }
        let mut res = 0; dfs(&root, &mut res); res
    }

17.05.2024

1325. Delete Leaves With a Given Value easy blog post substack youtube 2024-05-17_08-57.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/605

Problem TLDR

Recursively remove target leafs from the tree #easy #dfs #tree

Intuition

When dealing with Binary Trees try to solve the subproblem recursively.

Approach

  • Notice how drop is used in Rust, without it borrow checker would not allow to return Some(node)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\) for the recursion depth

Code


    fun removeLeafNodes(root: TreeNode?, target: Int): TreeNode? = root?.run {
        left = removeLeafNodes(left, target)
        right = removeLeafNodes(right, target)
        if (left == null && right == null && `val` == target) null else root
    }


    pub fn remove_leaf_nodes(root: Option<Rc<RefCell<TreeNode>>>, target: i32) -> Option<Rc<RefCell<TreeNode>>> {
        let node = root?; let mut n = node.borrow_mut();
        n.left = Self::remove_leaf_nodes(n.left.take(), target);
        n.right = Self::remove_leaf_nodes(n.right.take(), target);
        if n.left.is_none() && n.right.is_none() && n.val == target { None } else { drop(n); Some(node) }
    }

16.05.2024

2331. Evaluate Boolean Binary Tree easy blog post substack youtube 2024-05-16_08-48.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/604

Problem TLDR

Evaluate tree where 0/1 is false/true and 2/3 is or/and #easy #tree #dfs

Intuition

We can solve a subproblem for each node in a recursion.

Approach

Let’s try to avoid the double walk by changing the boolean operations order.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\) for the recursion depth

Code


    fun evaluateTree(root: TreeNode?): Boolean = root?.run {
    if (`val` < 1) false else `val` < 2
    || evaluateTree(left) && (`val` < 3 || evaluateTree(right))
    || `val` < 3 && evaluateTree(right) } ?: false


    pub fn evaluate_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        root.as_ref().map_or(false, |n| { let mut n = n.borrow_mut();
            if n.val < 1 { false } else {
            n.val < 2 || Self::evaluate_tree(n.left.take()) 
            && (n.val < 3 || Self::evaluate_tree(n.right.take()))
            || n.val < 3 && Self::evaluate_tree(n.right.take())
        }})
    }

15.05.2024

2812. Find the Safest Path in a Grid medium blog post substack youtube 2024-05-15_09-43.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/603

Problem TLDR

Safest path in a grid with thieves #medium #bfs #heap

Intuition

Let’s firs build a map, marking each cell with its safety number, this can be done with Breadth-First Search from all thieves: 2024-05-15_07-58.webp The path finding part is straightforward Dijkstra: choose the most optimal path from the heap, stop on the first arrival.

Approach

There are some tricks possible:

  • use the grid itself as a visited set: check 0 and mark with negative
  • we can avoid some extra work if we start safety with 1

Complexity

  • Time complexity: \(O(nmlog(nm))\)

  • Space complexity: \(O(nm)\)

Code


    fun maximumSafenessFactor(grid: List<List<Int>>): Int {
        val g = grid.map { it.toTypedArray() }; val n = g.size
        with(ArrayDeque<Pair<Int, Int>>()) {
            for (y in 0..<n) for(x in 0..<n) if (g[y][x] > 0) add(y to x)
            while (size > 0) {
                val (y, x) = removeFirst(); val step = g[y][x] + 1
                fun a(y: Int, x: Int): Unit =
                    if (x in 0..<n && y in 0..<n && g[y][x] < 1) {
                        add(y to x); g[y][x] = step
                    } else Unit
                a(y - 1, x); a(y, x - 1); a(y + 1, x); a(y, x + 1)
            }
        }
        data class Path(val f: Int, val x: Int, val y: Int)
        return with(PriorityQueue<Path>(compareBy { it.f })) {
            add(Path(-g[0][0], 0, 0))
            while (size > 0) {
                val (f, x, y) = poll()
                fun a(x: Int, y: Int): Unit =
                    if (x in 0..<n && y in 0..<n && g[y][x] > 0) {
                        add(Path(-min(-f, g[y][x]), x, y)); g[y][x] *= -1
                    } else Unit
                if (x == n - 1 && y == n - 1) return -f - 1
                a(x - 1, y); a(x, y - 1); a(x + 1, y); a(x, y + 1)
            }; -1
        }
    }


    pub fn maximum_safeness_factor(mut g: Vec<Vec<i32>>) -> i32 {
        let (n, mut q, mut h) = (g.len(), VecDeque::new(), BinaryHeap::new());
        for y in 0..n { for x in 0..n { if g[y][x] > 0 { q.push_back((y, x) )}}}
        while let Some((y, x)) = q.pop_front() {
            let s = g[y][x] + 1;
            if y > 0 && g[y - 1][x] < 1 { q.push_back((y - 1, x)); g[y - 1][x] = s; }
            if x > 0 && g[y][x - 1] < 1 { q.push_back((y, x - 1)); g[y][x - 1] = s; }
            if y < n - 1 && g[y + 1][x] < 1 { q.push_back((y + 1, x)); g[y + 1][x] = s; }
            if x < n - 1 && g[y][x + 1] < 1 { q.push_back((y, x + 1)); g[y][x + 1] = s; }
        }
        h.push((g[0][0], 0, 0));
        while let Some((f, y, x)) = h.pop() {
            if x == n - 1 && y == n - 1 { return f - 1 }
            if y > 0 && g[y - 1][x] > 0 { h.push((f.min(g[y - 1][x]), y - 1, x)); g[y - 1][x] *= -1; }
            if x > 0 && g[y][x - 1] > 0 { h.push((f.min(g[y][x - 1]), y, x - 1)); g[y][x - 1] *= -1; }
            if y < n - 1 && g[y + 1][x] > 0 { h.push((f.min(g[y + 1][x]), y + 1, x)); g[y + 1][x] *= -1; }
            if x < n - 1 && g[y][x + 1] > 0 { h.push((f.min(g[y][x + 1]), y, x + 1)); g[y][x + 1] *= -1; }
        }; -1
    }

14.05.2024

1219. Path with Maximum Gold medium blog post substack youtube 2024-05-14_08-57.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/602

Problem TLDR

Max one-way path in matrix #medium #dfs

Intuition

Path search can almost always be done with a Depth-First Search. Given the problem size 15x15, we can do a full search with backtracking.

Approach

Modify the grid to save some lines of code. Don’t do this in a production code however (or document it with warnings).

Complexity

  • Time complexity: \(O(3^p)\), where p is the longest path or the number of the gold cells, 3 - is the ways count each step

  • Space complexity: \(O(p)\), for the recursion depth

Code


    fun getMaximumGold(grid: Array<IntArray>): Int {
        fun f(y: Int, x: Int): Int = 
            if (grid.getOrNull(y)?.getOrNull(x) ?: 0 < 1) 0 else {
                val v = grid[y][x]; grid[y][x] = 0
                v + maxOf(f(y - 1, x), f(y + 1, x), f(y, x - 1), f(y, x + 1))
                    .also { grid[y][x] = v }
            }
        return grid.indices.maxOf { y -> grid[0].indices.maxOf { f(y, it) }}
    }


    pub fn get_maximum_gold(mut grid: Vec<Vec<i32>>) -> i32 {
        fn f(y: usize, x: usize, grid: &mut Vec<Vec<i32>>) -> i32 {
            let v = grid[y][x]; if v < 1 { return 0 }
            let mut r = 0; grid[y][x] = 0;
            if y > 0 { r = r.max(f(y - 1, x, grid)) }
            if x > 0 { r = r.max(f(y, x - 1, grid)) }
            if y < grid.len() - 1 { r = r.max(f(y + 1, x, grid)) }
            if x < grid[0].len() - 1 { r = r.max(f(y, x + 1, grid)) }
            grid[y][x] = v; r + v
        }
        let mut res = 0;
        for y in 0..grid.len() { for x in 0..grid[0].len() { 
            res = res.max(f(y, x, &mut grid))
        }}; res
    }

13.05.2024

861. Score After Flipping Matrix medium blog post substack youtube 2024-05-13_08-42.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/601

Problem TLDR

Max binary-row sum after toggling rows and columns #medium

Intuition

Let’s consider example: 2024-05-13_08-10.webp Our intuition:

  • we can toggle rows only if the first bit is 0 otherwise it will make the number smaller
  • we can toggle the column only if the number of 0 bits is bigger that 1 bits, otherwise sum will be smaller

Approach

We can toggle rows then toggle columns.

  • We didn’t have to actually toggle columns, just choose the max(count, height - count).
  • (The tricky part): we didn’t have to toggle rows, just invert each bit if the first bit is zero.

Complexity

  • Time complexity: \(O(nm)\)

  • Space complexity: \(O(1)\)

Code


    fun matrixScore(grid: Array<IntArray>) =
        grid[0].indices.fold(0) { sum, x -> 
            var count = grid.indices.sumOf { grid[it][x] xor grid[it][0] }
            sum * 2 + max(count, grid.size - count)
        }


    pub fn matrix_score(mut grid: Vec<Vec<i32>>) -> i32 {
        (0..grid[0].len()).fold(0, |sum, x| {
            let count: i32 = (0..grid.len()).map(|y| grid[y][0] ^ grid[y][x]).sum();
            sum * 2 + count.max(grid.len() as i32 - count)
        })
    }

12.05.2024

2373. Largest Local Values in a Matrix easy blog post substack youtube 2024-05-12_08-45.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/600

Problem TLDR

Max pooling by 3x3 matrix #easy

Intuition

The easiest way is to just iterate over the neighbours each time. (However one can possible find an algorithm to do a running-max with a monotonic stack)

Approach

Let’s try to write it shorter this time.

Complexity

  • Time complexity: \(O(n^2k^4)\), where k = 3 is constant

  • Space complexity: \(O(n^2)\)

Code


    fun largestLocal(grid: Array<IntArray>) =
        Array(grid.size - 2) { y -> IntArray(grid.size - 2) { x ->
            (0..8).maxOf { grid[y + it / 3][x + it % 3] }
        }}


    pub fn largest_local(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut res = vec![vec![0; grid.len() - 2]; grid.len() - 2];
        for y in 0..res.len() { for x in 0..res.len() {
            res[y][x] = (0..9).map(|i| grid[y + i / 3][x + i % 3]).max().unwrap()
        }}; res
    }

11.05.2024

857. Minimum Cost to Hire K Workers hard blog post substack youtube 2024-05-11_10-06.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/599

Problem TLDR

Min cost of k workers each doing quality[i] work for fair rate #hard #heap #sorting

Intuition

Let’s do the painful part - try to solve this problem by bare hands:

    // 10 20 5   70 50 30   2
    //  5    10    20    30 70 50
    //  5/20 10/20
    //  5/10
    //  5/20   5/10  10/20 
    // 30,50  30,70  70,50
    // 30*4   30*2   50/2=25
    // 50/4   70/2   70*2
    // take 70: q=10
    //   i=1  pay=20/10*70=140 q1=20
    //   i=2  pay=(10/5)*70=35
    // sort by quality
    // 5 10 20   30 70 50
    // take q=5 p=30, price = 30/5=6
    // i=1 pay=10*6=60 (less than 70, increase price 70/10=7)
    // ...
    // convert q-w to prices: 70/10 50/20 30/5
    // 7 2.5 6
    // sort
    // 20  5   10
    // 2.5 6.0 7.0    how many workers we can take 
    //                for price = 2.5? 1, cost = 50
    // 2.5*20 2.5*5  2.5*10
    // 50     7.5    25
    //                for price = 6.0? 2, cost 120+30=150
    // 6*20 6*5 6*10
    // 120  30  60                             
    //                for price = 7.0? 3, cost 140+35+70=245
    // 7*20 7*5 7*10
    // 140  35  70
    // 20   25  35 prefix sum?
    //      [5+10=15]

At this point I had an idea: there is a rate which is the wage/quality. The fair rate condition is just we must pay this rate * quality each worker produces. Now the interesting part: when we sort the workers by thier rate, we can try first with the lowest possible rate and then increase it to the next worker's rate. And we can take as much workers to the left as we want - all of them will agree to this rate as it is the largest so far.

    // 4 8 2  2  7 w     k=3
    // 3 1 10 10 1 q
    // sort by cost
    // 2  2  4  7  8  w
    // 10 10 3  1  1  q    3*4/3 + 10*2*4/3 + 10*2*4/3 = 4*23/3 = 92/3
    // 10 20 23 24 25 prefixSum?

The last piece is how to choose k workers from the all available: the simple sliding window is not optimal, as the qualities varies and we can leave cheap at the start.

Let’s just take all the workers with the lowest qualities to pay them less. The cost would be total sum of the workers qualities multiplied by top rate.

Approach

  • use a min-heap PriorityQueue to choose the lowest k
  • Rust can’t just pick min or sort by f64 key

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(n)\)

Code


    fun mincostToHireWorkers(quality: IntArray, wage: IntArray, k: Int): Double {
        var qSum = 0; val pq = PriorityQueue<Int>()
        return wage.indices.sortedBy { 1.0 * wage[it] / quality[it] }.minOf {
            val q = quality[it]; qSum += q; pq += -q
            if (pq.size > k) qSum += pq.poll()
            if (pq.size >= k) 1.0 * qSum * wage[it] / q else Double.MAX_VALUE
        }
    }


    pub fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 {
        let (mut qSum, mut bh, mut inds) = (0, BinaryHeap::new(), (0..wage.len()).collect::<Vec<_>>()); 
        inds.sort_unstable_by(|&i, &j| (wage[i] * quality[j]).cmp(&(wage[j] * quality[i])));
        inds.iter().map(|&i| {
            let q = quality[i]; qSum += q; bh.push(q);
            if bh.len() as i32 > k { qSum -= bh.pop().unwrap() }
            if bh.len() as i32 >= k { qSum as f64 * wage[i] as f64 / q as f64 } else { f64::MAX }
        }).min_by(|a, b| a.total_cmp(b)).unwrap()
    }

10.05.2024

786. K-th Smallest Prime Fraction medium blog post substack youtube 2024-05-10_10-07.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/598

Problem TLDR

kth arr[i]/arr[j], i < j, arr[i] < arr[j] #medium #heap #binary_search

Intuition

The n^2-ish solution is trivial: use PriorityQueue to keep lowest k fractions and scan n^2 indices pairs.

The folow up is hard. Let’s observe the fractions in the matrix a/b:

    //          1   2   3   5   a
    //
    //      5   1/5 2/5 3/5
    //      3   1/3 2/3
    //      2   1/2
    //      b
    //

The idea is to for any particular fraction m count how many fractions are less than it in O(n) time. We should invent the way of walking the indices based on observation that fractions grow in both directions of the matrix. Let’s iterate over each a value a = arr[i]. And for each a let’s move b = arr[j] forward while the current fraction is bigger: we can move it only forward and don’t need to backtrack, as if arr[x]/arr[j] > m than arr[x..]/arr[j] is also > m.

    // count less than m = 0.5
    // i=0 1/2 1/3 1/5
    //     j=1 j=2      stop on j=2, count(i=0) = 4-2 = size - j
    // i=1     2/3 2/5
    //         j=2 j=3  stop on j=3, count(i=1) = 4-3 = 1
    // i=2         3/5
    //             j=3 j=4 stop on j=4, count = 0

Now, we have a continuous function of count that grows with fraction m in 0..1 and can do a BinarySearch for k on it.

Approach

This BinarySearch is in double space, so we can’t just use m + 1 or m - 1, and lo must not be equal hi.

Complexity

  • Time complexity: \(O(n^2log^2(k))\) for the heap, \(O(nlogn)\) for the binary search (the search space of 0..1 is quantized by the number of pairs, so n^2, log(n^2) = 2log(n))

  • Space complexity: \(O(k)\) for the heap, \(O(1)\) for the binary search

Code


    fun kthSmallestPrimeFraction(arr: IntArray, k: Int): IntArray {
        val pq = PriorityQueue<IntArray>(Comparator<IntArray> { a, b ->
            -(a[0] * b[1]).compareTo(b[0] * a[1])
        })
        for (j in arr.indices) for (i in 0..<j) {
            pq += intArrayOf(arr[i], arr[j])
            if (pq.size > k) pq.poll()
        }
        return pq.poll()
    }


    pub fn kth_smallest_prime_fraction(arr: Vec<i32>, k: i32) -> Vec<i32> {
        let (mut lo, mut hi, mut r) = (0.0, 1.0, vec![0, 0]);
        while lo < hi {
            let (m, mut j, mut cnt, mut max) = (lo + (hi - lo) / 2.0, 1, 0, 0.0);
            for i in 0..arr.len() - 1 {
                while j < arr.len() && arr[i] as f64 >= m * arr[j] as f64 { j += 1 }
                let f = if j < arr.len() { arr[i] as f64 / arr[j] as f64 } else { break };
                if f > max { max = f; r = vec![arr[i], arr[j]] }
                cnt += (arr.len() - j) as i32
            }
            if cnt == k { break } else if cnt < k { lo = m } else { hi = m }
        }; r
    }

09.05.2024

3075. Maximize Happiness of Selected Children medium blog post substack youtube 2024-05-09_11-24.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/597

Problem TLDR

Sum of k maximums decreasing each step #medium #sorting #heap #quickselect

Intuition

By the problem definition we may assume that optimal solution is to take the largest values first, as smaller values will not decrease the result after reaching zero.

There are several ways to take k largest values: sort the entire array, use Heap (PriorityQueue) or use QuickSelect and sort partially.

Approach

Let’s use PriorityQueue in Kotlin (min heap) and QuickSelect in Rust (select_nth_unstable).

  • when using heap we can take at most k values into it to save space and time
  • Rust’s select_nth_unstable result tuple is not very easy to use (do you know a better way?)

Complexity

  • Time complexity: \(O(n + klog(k))\) for the Heap and for the QuickSelect

  • Space complexity: \(O(n)\) for the Heap, \(O(1)\) for the QuickSelect

Code


    fun maximumHappinessSum(happiness: IntArray, k: Int): Long {
        val pq = PriorityQueue<Int>()
        for (h in happiness) { pq += h; if (pq.size > k) pq.poll() }
        return (0..<k).sumOf { max(0, pq.poll() + it - k + 1).toLong() }
    }


    pub fn maximum_happiness_sum(mut happiness: Vec<i32>, k: i32) -> i64 {
        let count = 0.max(happiness.len() as i32 - k - 1) as usize;
        let gt = if count > 0 { happiness.select_nth_unstable(count).2 }
                 else { &mut happiness[..] };
        gt.sort_unstable_by(|a, b| b.cmp(a));
        (0..k).map(|i| 0.max(gt[i as usize] - i) as i64).sum()
    }

08.05.2024

506. Relative Ranks easy blog post substack youtube 2024-05-08_08-04.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/596

Problem TLDR

Convert results array to ranks array #easy #sorting

Intuition

Understand what the problem is:

4 3 2 1 -> "4" "Bronze" "Silver" "Gold

We need to convert each result with it’s position in a sorted order. There are several ways to do this: use a HashMap, Priority Queue, or just sort twice.

Approach

Let’s try to write the minimum lines of code version.

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(n)\)

Code


    fun findRelativeRanks(score: IntArray): Array<String> {
        val medals = listOf("Gold", "Silver", "Bronze")
        val inds = score.indices.sortedByDescending { score[it] }
        return inds.indices.sortedBy { inds[it] }.map { 
            if (it > 2) "${ it + 1 }" else "${ medals[it] } Medal"
        }.toTypedArray()
    }


    pub fn find_relative_ranks(score: Vec<i32>) -> Vec<String> {
        let mut inds: Vec<_> = (0..score.len()).collect();
        inds.sort_unstable_by_key(|&i| Reverse(score[i]));
        let (mut res, medals) = (inds.clone(), vec!["Gold", "Silver", "Bronze"]);
        res.sort_unstable_by_key(|&r| inds[r]);
        res.iter().map(|&place| if place > 2 { format!("{}", place + 1) } 
            else { format!("{} Medal", medals[place]) }).collect()
    }

07.05.2024

2816. Double a Number Represented as a Linked List medium blog post substack youtube 2024-05-07_07-58.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/595

Problem TLDR

Double the number as a Linked List #medium #linked_list

Intuition

The trivial solution is to reverse the list and iterate from the back. However, there is a more clever solution (not mine): add sentinel head and compute always the next node.

Approach

  • For the Rust: notice how to use head with as_mut and as_ref - without them it will not compile as borrow will occur twice.
  • For the Kotlin solution: let’s use a single extra variable, just for fun.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun doubleIt(head: ListNode?): ListNode? {
        var prev = head
        while (head?.next != null) {
            val next = head?.next?.next
            head?.next?.next = prev
            prev = head?.next
            head?.next = next
        }
        var carry = 0
        while (prev != null) {
            val v = carry + prev.`val` * 2
            carry = v / 10
            prev.`val` = v % 10
            if (head == prev) break
            val next = prev.next
            prev.next = head?.next
            head?.next = prev
            prev = next
        }
        return if (carry > 0) ListNode(1)
            .apply { next = head } else head
    }


    pub fn double_it(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut head = Some(Box::new(ListNode { val: 0, next: head }));
        let mut prev_box = head.as_mut().unwrap();
        while let Some(curr_box) = prev_box.next.as_mut() {
            let v = curr_box.val * 2;
            curr_box.val = v % 10;
            prev_box.val += v / 10;
            prev_box = curr_box
        }
        if head.as_ref().unwrap().val < 1 { head.unwrap().next } else { head }
    }

06.05.2024

2487. Remove Nodes From Linked List medium blog post substack youtube 2024-05-06_09-06.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/594

Problem TLDR

Make a Linked List non-increasing #medium #linked_list

Intuition

The trivial way to solve it is to use a monotonic stack technique: remove from the stack all lesser nodes and always add the current. However, there is a clever O(1) memory solution: just reverse the Linked List and iterate from the tail.

Approach

Let’s save some lines of code just for the fun of it: can you use a single extra variable?

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun removeNodes(head: ListNode?): ListNode? {
        var m = head
        while (head?.next != null) {
            val next = head?.next?.next
            head?.next?.next = m
            m = head?.next
            head?.next = next
        }
        while (m != null) {
            val next = if (m == head) null else m.next
            if (m.`val` >= (head?.next?.`val` ?: 0)) {
                if (m == head) return head
                m.next = head?.next
                head?.next = m
            }
            m = next
        }
        return head?.next
    }


    pub fn remove_nodes(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let (mut curr, mut prev) = (head, None);
        while let Some(mut curr_box) = curr {
            let next = curr_box.next;
            curr_box.next = prev;
            prev = Some(curr_box);
            curr = next;
        }
        while let Some(mut prev_box) = prev {
            let next = prev_box.next;
            if prev_box.val >= curr.as_ref().map_or(0, |curr| curr.val) {
                prev_box.next = curr;
                curr = Some(prev_box);
            }
            prev = next
        }
        curr
    }

05.05.2024

237. Delete Node in a Linked List medium blog post substack youtube 2024-05-05_08-14.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/593

Problem TLDR

Delete current node in a Linked List #medium

Intuition

The O(n) solution is trivial: swap current and next values until the last node reached. There is an O(1) solution exists, and it’s clever: remove just the next node.

Approach

No Rust solution, as there is no template for it in leetcode.com.

Complexity

  • Time complexity: \(O(1)\)

  • Space complexity: \(O(1)\)

Code


    fun deleteNode(node: ListNode?) {
        node?.`val` = node?.next?.`val`
        node?.next = node?.next?.next
    }


    void deleteNode(ListNode* node) {
        *node = *node->next;
    }

04.05.2024

881. Boats to Save People medium blog post substack youtube 2024-05-04_08-54.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/592

Problem TLDR

Minimum total boats with at most 2 people & limit weight #medium #two_pointers #greedy

Intuition

First idea as to try to take as much people as possible in a single boat: if we start with light first, then heavier people might not give a space for a limit. By intuition, we need to try put most heavy and most light people in pairs together:

    // 6654321   limit = 6
    // i     j
    // i         +1
    //  i        +1
    //   i   j   +1
    //    i j    +1
    //     i     +1

Approach

The interesting part is how some conditions are not relevant: we can skip i < j check when moving j--.

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


    fun numRescueBoats(people: IntArray, limit: Int): Int {
        people.sortDescending(); var j = people.lastIndex
        for ((i, p) in people.withIndex())
            if (i > j) return i
            else if (p + people[j] <= limit) j--
        return people.size
    }


    pub fn num_rescue_boats(mut people: Vec<i32>, limit: i32) -> i32 {
        people.sort_unstable_by(|a, b| b.cmp(a)); 
        let mut j = people.len() - 1;
        for (i, p) in people.iter().enumerate() {
            if i > j { return i as _ }
            else if p + people[j] <= limit { j -= 1 }
        }; people.len() as _
    }

03.05.2024

165. Compare Version Numbers medium blog post substack youtube 2024-05-03_09-21.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/591

Problem TLDR

Compare version numbers #medium

Intuition

We can use two pointers and scan the strings with O(1) memory. More compact and simple code would be by using a split.

Approach

  • zip helps to save some lines of code

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\), or can be O(1)

Code


    fun compareVersion(version1: String, version2: String): Int {
        var r1 = version1.split(".").map { it.toInt() }
        var r2 = version2.split(".").map { it.toInt() }
        val pad = List(abs(r1.size - r2.size)) { 0 }
        return (r1 + pad).zip(r2 + pad).firstOrNull { (a, b) -> a != b }
            ?.let { (a, b) -> a.compareTo(b) } ?: 0
    }


    pub fn compare_version(version1: String, version2: String) -> i32 {
        let v1: Vec<_> = version1.split('.').map(|x| x.parse().unwrap()).collect();
        let v2: Vec<_> = version2.split('.').map(|x| x.parse().unwrap()).collect();
        for i in 0..v1.len().max(v2.len()) {
            let a = if i < v1.len() { v1[i] } else { 0 };
            let b = if i < v2.len() { v2[i] } else { 0 };
            if a < b { return -1 }
            if a > b { return 1 }
        }; 0
    }

02.05.2024

2441. Largest Positive Integer That Exists With Its Negative easy blog post substack youtube 2024-05-02_08-34.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/590

Problem TLDR

Max number that has its negative in array #easy #two_pointers

Intuition

One possible solution is to sort array and compare minimums with maximums by moving two pointers from left and right of the array. Another way is to remember which numbers are seen and choose the maximum of them.

Approach

  • For the second solution, we can use just a [2000] array, as the total count is not that big.

Complexity

  • Time complexity: \(O(nlog(n))\) and \(O(n)\)

  • Space complexity: \(O(1)\) and \(O(n)\)

Code


    fun findMaxK(nums: IntArray): Int {
        nums.sort()
        var i = 0; var j = nums.lastIndex
        while (i < j)
            if (nums[i] == -nums[j]) return nums[j]
            else if (-nums[i] < nums[j]) j-- else i++
        return -1
    }


    pub fn find_max_k(nums: Vec<i32>) -> i32 {
        let (mut counts, mut res) = (vec![0; 2001], -1);
        for x in nums {
            if counts[1000 - x as usize] > 0 { res = res.max(x.abs()) }
            counts[x as usize + 1000] += 1
        }; res
    }

01.05.2024

2000. Reverse Prefix of Word easy blog post substack youtube 2024-05-01_09-09.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/589

Problem TLDR

Reverse [..ch] prefix in string #easy

Intuition

First find the position, then reverse the prefix.

Approach

Can you make the code shorter? (Don’t do this in the interview, however, we skipped optimized case of not found index.)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun reversePrefix(word: String, ch: Char) = String(
        word.toCharArray().apply { reverse(0, indexOf(ch) + 1) }
    )


    pub fn reverse_prefix(mut word: String, ch: char) -> String {
        let i = word.find(ch).unwrap_or(0) + 1;
        word[..i].chars().rev().chain(word[i..].chars()).collect()
    }

30.04.2024

1915. Number of Wonderful Substrings medium blog post substack youtube 2024-04-30_09-16.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/588

Problem TLDR

Count substrings with at most one odd frequency #medium #bit_manipulation

Intuition

This is a hard problem. Let’s try to look at the problem with our bare hands:

    // aba
    // a     a
    // ab    -
    //  b    b
    //  ba   -
    // aba   aba

    // aab
    // a     +    xor = a
    // aa    +    xor = 0
    //  a    +    xor = a
    // aab   +    xor = b
    //  ab   -    xor = ab
    //   b   +    xor = b
    //   * = (aa, a) + b

    // dp or two-pointers?
    // dp: f(aabb) = f(aab)? + b
    // two pointers: 
    // aabb
    //    i  move i: a + a + b + b + aa + aab + aabb
    //    j  move j: abb + bb
    //  skip ab?

We quickly run out of possible solutions patterns: neither dp or two pointers approach would work. However, there are some thoughts:

  • only odd-even matters, so, we can somehow use xor
  • xor works well for interval i..j when we pre-compute all the prefixes: xor i..j = xor 0..j xor xor 0..i

This is where my brain has stopped, and I used the hints:

  • use prefix’s bitmask, as we only have 10 unique chars

Let’s try to make use of the prefix’s bitmasks:


    // bitmask           00
    // a                 01
    //  a                00
    //   b               10  m[ab] = m[aab] xor m[a]
    //    b              00  m[abb] = m[aabb] xor m[a]
    //     how many previous masks have mismatched bits?
    //                                  ~~~~~~~~~~

We know the current prefix’s bitmask m and our interest is how many subarrays on the left are good. We can xor with all the previous masks to find out the xor result of subarrays: this result must have at most one 1 bit. We can compress this search by putting unique masks in a counter HashMap.

    // mismatched = differs 1 bit or equal
    //
    // ab                m
    //                   00
    // a                 01 +1(00)
    //  b                11 +1(01)

    // 0123
    // aabb              m   res
    //                   00  
    //0a                 01  +1(00)
    //1 a                00  +2(00,01)
    //2  b               10  +2(00,00)
    //3   b              00  +4(00,01,00,10) 
    //    

Approach

  • Another neat trick: we don’t have to check all the masks from a HashMap, just check by changing every of the 10 bits of mask.
  • array is faster, we have at most 2^10 unique bits combinations

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(2^k)\), k - is an alphabet, at most 2^10 masks total

Code


    fun wonderfulSubstrings(word: String): Long {
        val masksCounter = LongArray(1024); masksCounter[0] = 1
        var m = 0; var res = 0L
        for (c in word) {
            m = m xor (1 shl (c.code - 'a'.code))
            res += masksCounter[m]
            for (i in 0..9) res += masksCounter[m xor (1 shl i)]
            masksCounter[m]++
        }
        return res
    }


    pub fn wonderful_substrings(word: String) -> i64 {
        let mut counter = vec![0; 1024]; counter[0] = 1;
        let (mut m, mut res) = (0, 0);
        for b in word.bytes() {
            m ^= 1 << (b - b'a');
            res += counter[m];
            for i in 0..10 { res += counter[m ^ (1 << i)] }
            counter[m] += 1
        }; res
    }

29.04.2024

2997. Minimum Number of Operations to Make Array XOR Equal to K medium blog post substack youtube 2024-04-29_07-41.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/587

Problem TLDR

Bit diff between k and nums xor #medium #bit_manipulation

Intuition

Let’s observe how the result xor built:

    // 2  010 -> 110
    // 1  001
    // 3  011 -> 010
    // 4  100
    // x  100 -> 000 -> 001
    // k  001

The result x differs from k by two bit flips: 100 -> 000 -> 001. We can do those bit flips on any number in the array, the final xor does not depend on the number choice.

Approach

Let’s try to use built-in methods: fold, countOneBits, count_ones.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun minOperations(nums: IntArray, k: Int) =
        nums.fold(k) { r, t -> r xor t }.countOneBits()


    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        nums.iter().fold(k, |r, t| r ^ t).count_ones() as _
    }

28.04.2024

834. Sum of Distances in Tree hard blog post substack youtube 2024-04-28_10-54.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/586

Problem TLDR

Sums of paths to each leafs in a tree #hard #dfs

Intuition

Let’s observe how the result is calculated for each of the node: 2024-04-28_08-48.webp

As we see, there are some relationships between sibling nodes: they differ by some law. Our goal is to reuse the first iteration result. When we change the root, we are decreasing all the paths that are forwards and increasing all the paths that are backwards. The number of forward and backward paths can be calculated like this: 2024-04-28_09-01.webp Given that, we can derive the formula to change the root: 2024-04-28_11-08.webp

new root == previous root - forward + backward, or R2 = R1 - count1 + (n - count1)

Approach

There are two possible ways to solve this: recursion and iteration.

  • we can drop the counts array and just use the result
  • for the post-order iterative solution, we also can simplify some steps: step 0 - go deeper, step 1 - return with result, that is where child nodes are ready, step 2 - again go deeper to do the root changing operation

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun sumOfDistancesInTree(n: Int, edges: Array<IntArray>): IntArray {
        val graph = Array(n) { mutableListOf<Int>() }
        for ((a, b) in edges) { graph[a] += b; graph[b] += a }
        val res = IntArray(n)
        fun dfs(curr: Int, from: Int, path: Int): Int = (1 + graph[curr]
            .sumOf { if (it != from) dfs(it, curr, path + 1) else 0 })
            .also { res[0] += path; if (curr > 0) res[curr] = n - 2 * it }
        fun dfs2(curr: Int, from: Int) {
            if (curr > 0) res[curr] += res[from]
            for (e in graph[curr]) if (e != from) dfs2(e, curr)
        }
        dfs(0, 0, 0); dfs2(0, 0)
        return res
    }


    pub fn sum_of_distances_in_tree(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
        let (mut g, mut res, mut st) = (vec![vec![]; n as usize], vec![0; n as usize], vec![(0, 0, 0, 0)]);
        for e in edges { let (a, b) = (e[0] as usize, e[1] as usize); g[a].push(b); g[b].push(a) }
        while let Some((curr, from, path, step)) = st.pop() {
            if step == 0 {
                st.push((curr, from, path, 1));
                for &e in &g[curr] { if e != from { st.push((e, curr, path + 1, 0)) }}
                res[0] += path
            } else if step == 1 {
                if curr == 0 { st.push((curr, from, 0, 2)); continue }
                for &e in &g[curr] { if e != from { res[curr] -= n - res[e] }}
                res[curr] += n - 2
            } else {
                if curr > 0 { res[curr] += res[from] }
                for &e in &g[curr] { if e != from { st.push((e, curr, 0, 2)) }}
            }
        }; res
    }

27.04.2024

514. Freedom Trail hard blog post substack youtube 2024-04-27_09-19.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/585

Problem TLDR

Min steps to produce key by rotating ring #hard #dynamic_programming #recursion #hash_map

Intuition

Let’s from the current position do the full search by trying each position with give letter. The minimum path is only depending on the current position of the ring and position in the key so it can be memoized.

However, don’t forget to rotate optimally, sometimes it’s a left rotation: 2024-04-27_08-36.webp

We can store the ring positions ahead of time.

Approach

Another approach is to do a Breadth-First Search: for each key position store all the min-length paths and their positions. Iterate from them at the next key position.

Complexity

  • Time complexity: \(O(r^2k)\), the worst case r^2 if all letters are the same

  • Space complexity: \(O(rk)\)

Code


    fun findRotateSteps(ring: String, key: String): Int {
        val cToPos = ring.indices.groupBy { ring[it] }
        val dp = mutableMapOf<Pair<Int, Int>, Int>()
        fun dfs(i: Int, j: Int): Int = if (j == key.length) 0 else 
        dp.getOrPut(i to j) {
            1 + if (ring[i] == key[j]) dfs(i, j + 1) else { 
            cToPos[key[j]]!!.minOf { 
                min(abs(i - it), ring.length - abs(i - it)) + dfs(it, j + 1)
        }}}
        return dfs(0, 0)
    }


    pub fn find_rotate_steps(ring: String, key: String) -> i32 {
        let mut pos = vec![vec![]; 26];
        for (i, b) in ring.bytes().enumerate() { pos[(b - b'a') as usize].push(i) }
        let mut layer = vec![(0, 0)];
        for b in key.bytes() {
            let mut next = vec![];
            for &i in (&pos[(b - b'a') as usize]).iter() {
                next.push((i, layer.iter().map(|&(j, path)| {
                    let diff = if i > j { i - j } else { j - i };
                    diff.min(ring.len() - diff) + path
                }).min().unwrap()))
            }
            layer = next
        }
        (layer.iter().map(|x| x.1).min().unwrap() + key.len()) as i32
    }

26.04.2024

1289. Minimum Falling Path Sum II hard blog post substack youtube 2024-04-26_08-15.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/584

Problem TLDR

Min non-direct path top down in a 2D matrix #hard #dynamic_programming

Intuition

Let’s try an example: 2024-04-26_07-43.webp On each row we need to know the min value from the previous row, or the second min, if first is directly up. Then adding this min to the current cell would give us the min-sum.

Approach

We can reuse the matrix for brevety, however don’t do this in the interview or in a production code.

Complexity

  • Time complexity: \(O(nm)\)

  • Space complexity: \(O(1)\), or O(m) if the separate array used

Code


    fun minFallingPathSum(grid: Array<IntArray>): Int {
        var min1 = -1; var min2 = -1
        for (y in grid.indices) { grid[y].let {
            if (y > 0) for (x in it.indices) 
                it[x] += grid[y - 1][if (x == min1) min2 else min1]
            min1 = -1; min2 = -1
            for (x in it.indices) 
                if (min1 < 0 || it[x] < it[min1]) {
                    min2 = min1; min1 = x
                } else if (min2 < 0 || it[x] < it[min2]) min2 = x
        }}
        return grid.last()[min1]
    }


    pub fn min_falling_path_sum(mut grid: Vec<Vec<i32>>) -> i32 {
        let n = grid[0].len(); let (mut min1, mut min2) = (n, n);
        for y in 0..grid.len() {
            if y > 0 { for x in 0..n {
                grid[y][x] += grid[y - 1][if x == min1 { min2 } else { min1 }]
            }}
            min1 = n; min2 = n;
            for x in 0..n {
                if min1 == n || grid[y][x] < grid[y][min1] {
                    min2 = min1; min1 = x
                } else if min2 == n || grid[y][x] < grid[y][min2] { min2 = x }
            }
        }
        grid[grid.len() - 1][min1]
    }

25.04.2024

2370. Longest Ideal Subsequence medium blog post substack youtube 2024-04-25_08-26.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/583

Problem TLDR

Max length of less than k adjacent subsequence #medium #dynamic_programming

Intuition

Examining some examples, we see some properties:

    // acfgbd   k=2
    // a             a
    //  c            ac
    //   f           f
    //    g          fg
    //     b         acb
    //      d        acbd
  • we must be able to backtrack to the previous subsequences, so this is full search or at least memoization problem
  • at particular position, we know the result for the suffix given the starting char, so we know 26 results
  • we can memoise it by (pos, char) key

Approach

There are some optimizations:

  • current result only depends on the next result, so only [26] results are needed
  • we can rewrite memoisation recursion with iterative for-loop
  • changing the direction of loop is irrelevant, so better iterate forward for cache friendliness
  • the clever trick is to consider only adjacent k chars and only update the current char

Complexity

  • Time complexity: \(O(n)\), assuming the alphabet size is constant

  • Space complexity: \(O(1)\)

Code


    fun longestIdealString(s: String, k: Int): Int {
        var dp = IntArray(128)
        for (c in s) dp = IntArray(128) { max(
            if (abs(it - c.code) > k) 0
            else 1 + dp[c.code], dp[it]) }
        return dp.max()
    }


    pub fn longest_ideal_string(s: String, k: i32) -> i32 {
        let mut dp = vec![0; 26];
        for b in s.bytes() {
            let lo = ((b - b'a') as usize).saturating_sub(k as usize);
            let hi = ((b - b'a') as usize + k as usize).min(25);
            dp[(b - b'a') as usize] = 1 + (lo..=hi).map(|a| dp[a]).max().unwrap()
        }
        *dp.iter().max().unwrap()
    }

24.04.2024

1137. N-th Tribonacci Number easy blog post substack youtube 2024-04-24_08-41.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/582

Problem TLDR

nth Tribonacci number f(n + 3) = f(n) + f(n + 1) + f(n + 2) #easy

Intuition

Use tree variables and compute the result in a for-loop.

Approach

There are some clever approaches:

  • we can use an array and loop the index
  • we can try to play this with tree variables but without a temp variable

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun tribonacci(n: Int): Int {
        if (n < 2) return n
        val t = intArrayOf(0, 1, 1)
        for (i in 3..n) t[i % 3] = t.sum()
        return t[n % 3]
    }


    pub fn tribonacci(n: i32) -> i32 {
        if n < 2 { return n }
        let (mut t1, mut t2, mut t0t1) = (1, 1, 1);
        for _ in 2..n as usize {
            t2 += t0t1;
            t0t1 = t1 + t2 - t0t1;
            t1 = t0t1 - t1
        }; t2
    }

23.04.2024

310. Minimum Height Trees medium blog post substack youtube 2024-04-23_10-25.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/581

Problem TLDR

Center of an acyclic graph #medium #graph #toposort

Intuition

Didn’t solve it myself again.

The naive intuition that didn’t work for me was to move from the edges in BFS manner until a single or just two nodes left. This however doesn’t work for some cases: 2024-04-23_09-07.webp

After I gave up, in the solution section I saw a Topological Sort: always go from nodes with indegree == 1 and decrease it as you go.

There is also a two-dfs solution exists, it’s very clever: do two dfs runs from leaf to leaf and choose two middles of thier paths.

Approach

  • careful with order of decreasing indegree: first decrease, then check for == 1.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun findMinHeightTrees(n: Int, edges: Array<IntArray>): List<Int> {
        val graph = mutableMapOf<Int, MutableList<Int>>()
        val indegree = IntArray(n)
        for ((a, b) in edges) {
            indegree[a]++
            indegree[b]++
            graph.getOrPut(a) { mutableListOf() } += b
            graph.getOrPut(b) { mutableListOf() } += a
        }
        var layer = mutableListOf<Int>()
        for (x in 0..<n) if (indegree[x] < 2) {
            layer += x; indegree[x]--
        }
        while (layer.size > 1) {
            val next = mutableListOf<Int>()
            for (x in layer) for (y in graph[x]!!) {
                indegree[y]--
                if (indegree[y] == 1) next += y
            }
            if (next.size < 1) break
            layer = next
        }
        return layer
    }


    pub fn find_min_height_trees(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
        let mut graph = HashMap::new();
        let mut indegree = vec![0; n as usize];
        for e in edges {
            indegree[e[0] as usize] += 1;
            indegree[e[1] as usize] += 1;
            graph.entry(e[0]).or_insert(vec![]).push(e[1]);
            graph.entry(e[1]).or_insert(vec![]).push(e[0])
        }
        let mut layer = vec![];
        for x in 0..n as usize { if indegree[x] < 2 {
            layer.push(x as i32); indegree[x] -= 1
        }}
        while layer.len() > 1 {
            let mut next = vec![];
            for x in &layer { if let Some(nb) = graph.get(&x) {
                for &y in nb {
                    indegree[y as usize] -= 1;
                    if indegree[y as usize] == 1 { next.push(y) }
                }
            }}
            if next.len() < 1 { break }
            layer = next
        }
        layer
    }

22.04.2024

752. Open the Lock medium blog post substack youtube 2024-04-22_09-28.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/580

Problem TLDR

Steps to rotate 4-wheel 0000 -> target #medium #bfs #deque

Intuition

Whe can imagine each rotation as a graph edge and each combination as a graph node. The task now is to find the shortest path. This can be done with BFS.

Approach

We can use Strings or better to just use numbers.

Complexity

  • Time complexity: \(O(E)\), there are total 9999 number of nodes, and each node connected to 42=8 other nodes, so E = 810^4, V = 10^4

  • Space complexity: \(O(N)\), N is size of deadends

Code


    fun openLock(deadends: Array<String>, target: String) = 
        with(ArrayDeque<String>(listOf("0000"))) {
            val visited = deadends.toMutableSet()
            var step = 0
            while (size > 0) {
                repeat(size) {
                    val curr = removeFirst()
                    if (!visited.add(curr)) return@repeat
                    if (curr == target) return step
                    for ((i, c) in curr.withIndex()) {
                        add(curr.replaceRange(i, i + 1, "${if (c == '9') '0' else c + 1}"))
                        add(curr.replaceRange(i, i + 1, "${if (c == '0') '9' else c - 1}"))
                    }
                }
                step++
            }
            -1
        }


    pub fn open_lock(deadends: Vec<String>, target: String) -> i32 {
        let target = target.parse::<u16>().unwrap();
        let (mut deque, mut step) = (VecDeque::new(), 0);
        let mut visited: HashSet<_> = deadends.iter().map(|s| s.parse().unwrap()).collect();
        deque.push_back(0000);
        while deque.len() > 0 {
            for _ in 0..deque.len() {
                let curr = deque.pop_front().unwrap();
                if !visited.insert(curr) { continue }
                if curr == target { return step }
                for i in &[1000, 0100, 0010, 0001] {
                    let wheel = (curr / i) % 10;
                    deque.push_back((curr - i * wheel) + (i * ((wheel + 1) % 10)));
                    deque.push_back((curr - i * wheel) + (i * ((wheel + 9) % 10)));
                }
            }
            step += 1
        }
        -1
    }

21.04.2024

1971. Find if Path Exists in Graph easy blog post substack youtube 2024-04-21_08-22.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/578

Problem TLDR

Are source and destination connected in graph? #easy

Intuition

Let’s check connected components with Union-Find data structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Approach

We can use a HashMap or just simple array. To optimize Union-Find root function, we can use path compression step. There are other tricks (https://arxiv.org/pdf/1911.06347.pdf), but let’s keep code shorter.

Complexity

  • Time complexity: \(O(E + V)\), V = n, E = edges.size, assuming root is constant for inverse Ackermann function (https://codeforces.com/blog/entry/98275) (however only with all the tricks implemented, like ranks and path compressing https://cp-algorithms.com/data_structures/disjoint_set_union.html)

  • Space complexity: \(O(V)\)

Code


    fun validPath(n: Int, edges: Array<IntArray>, source: Int, destination: Int): Boolean {
        val uf = IntArray(n) { it }
        fun root(a: Int): Int { var x = a; while (x != uf[x]) x = uf[x]; uf[a] = x; return x }
        for ((a, b) in edges) uf[root(a)] = root(b)
        return root(source) == root(destination)
    }


    pub fn valid_path(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
        let mut uf = (0..n as usize).collect(); 
        fn root(uf: &mut Vec<usize>, a: i32) -> usize {
            let mut x = a as usize; while x != uf[x] { x = uf[x] }; uf[a as usize] = x; x
        }
        for ab in edges { let a = root(&mut uf, ab[0]); uf[a] = root(&mut uf, ab[1]) }
        root(&mut uf, source) == root(&mut uf, destination)
    }

20.04.2024

1992. Find All Groups of Farmland medium blog post substack youtube 2024-04-20_09-05.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/577

Problem TLDR

Count 1-rectangles in 0-1 2D matrix #medium

Intuition

We can use DFS or just move bottom-right, as by task definition all 1-islands are rectangles

Approach

  • find the right border, then fill arrays with zeros
  • Rust didn’t have a fill method

Complexity

  • Time complexity: \(O(nm)\)

  • Space complexity: \(O(r)\), where r is a resulting count of islands, can be up to nm/2

Code


    fun findFarmland(land: Array<IntArray>) = buildList {
        for (y in land.indices) for (x in land[0].indices) { if (land[y][x] > 0) {
            var y2 = y; var x2 = x
            while (x2 < land[0].size && land[y][x2] > 0) x2++
            while (y2 < land.size && land[y2][x] > 0) land[y2++].fill(0, x, x2)
            add(intArrayOf(y, x, y2 - 1, x2 - 1))
    }}}.toTypedArray()


    pub fn find_farmland(mut land: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        for y in 0..land.len() { for x in 0..land[0].len() { if land[y][x] > 0 {
            let (mut y2, mut x2) = (y, x);
            while x2 < land[0].len() && land[y][x2] > 0 { x2 += 1 }
            while y2 < land.len() && land[y2][x] > 0 {
                for i in x..x2 { land[y2][i] = 0 }
                y2 += 1
            }
            res.push(vec![y as i32, x as i32, y2 as i32 - 1, x2 as i32 - 1])
        }}}; res
    }

19.04.2024

200. Number of Islands medium blog post substack youtube 2024-04-19_07-38.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/576

Problem TLDR

Count 1-islands in 0-1 a 2D matrix #medium

Intuition

Let’s visit all the connected 1’s and mark them somehow to visit only once. Alternative solution would be using Union-Find, however for such trivial case it is unnecessary.

Approach

We can modify the input array to mark visited (don’t do this in production code or in interview).

Complexity

  • Time complexity: \(O(nm)\)

  • Space complexity: \(O(1)\), or O(nm) if we forbidden to modify the grid

Code


    fun numIslands(grid: Array<CharArray>): Int {
        fun dfs(y: Int, x: Int): Boolean =
            if (grid[y][x] == '1') {
                grid[y][x] = '0'
                if (x > 0) dfs(y, x - 1)
                if (y > 0) dfs(y - 1, x)
                if (x < grid[0].size - 1) dfs(y, x + 1)
                if (y < grid.size - 1) dfs(y + 1, x)
                true
            } else false
        return (0..<grid.size * grid[0].size).count {
            dfs(it / grid[0].size, it % grid[0].size)
        } 
    }


    pub fn num_islands(mut grid: Vec<Vec<char>>) -> i32 {
        fn dfs(grid: &mut Vec<Vec<char>>, y: usize, x: usize) -> i32 {
            if grid[y][x] == '1' {
                grid[y][x] = '0';
                if x > 0 { dfs(grid, y, x - 1); }
                if y > 0 { dfs(grid, y - 1, x); }
                if x < grid[0].len() - 1 { dfs(grid, y, x + 1); }
                if y < grid.len() - 1 { dfs(grid, y + 1, x); }
                1
            } else { 0 }
        }
        (0..grid.len() * grid[0].len()).map(|xy| {
            let x = xy % grid[0].len(); let y = xy / grid[0].len();
            dfs(&mut grid, y as usize, x as usize)
        }).sum()
    }

18.04.2024

463. Island Perimeter easy blog post substack youtube 2024-04-18_08-48.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/575

Problem TLDR

Perimeter of 1’s islands in 01-matrix #easy

Intuition

Let’s observe the problem example: 2024-04-18_08-05.webp As we see, the perimeter increases on the 0-1 transitions, we can just count them. Another neat approach I steal from someone: every 1 increases by 4 and then decreases by 1-1 borders.

Approach

Let’s try to save some keystrokes

  • did you know compareTo(false) will convert Boolean to Int? (same is as i32 in Rust)

Complexity

  • Time complexity: \(O(nm)\)

  • Space complexity: \(O(1)\)

Code


    fun islandPerimeter(grid: Array<IntArray>) =
        (0..<grid.size * grid[0].size).sumBy { xy ->
            val x = xy % grid[0].size; val y = xy / grid[0].size
            if (grid[y][x] < 1) 0 else
            (x < 1 || grid[y][x - 1] < 1).compareTo(false) +
            (y < 1 || grid[y - 1][x] < 1).compareTo(false) +
            (x == grid[0].lastIndex || grid[y][x + 1] < 1).compareTo(false) +
            (y == grid.lastIndex || grid[y + 1][x] < 1).compareTo(false)
        }


    pub fn island_perimeter(grid: Vec<Vec<i32>>) -> i32 {
        let mut p = 0;
        for y in 0..grid.len() { for x in 0..grid[0].len() {
            if grid[y][x] < 1 { continue }
            if y > 0 && grid[y - 1][x] > 0 { p -= 2 }
            if x > 0 && grid[y][x - 1] > 0 { p -= 2 }
            p += 4
        } }; p
    }

17.04.2024

988. Smallest String Starting From Leaf medium blog post substack youtube 2024-04-17_08-17.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/574

Problem TLDR

Smallest string from leaf to root in a Binary Tree #medium

Intuition

After trying some examples with bottom-up approach, we find out one that would not work: 2024-04-17_08-02.webp That means, we should use top down.

Approach

  • We can avoid using a global variable, comparing the results.
  • The if branching can be smaller if we add some symbol after z for a single-leafs.

Complexity

  • Time complexity: \(O(nlog^2(n))\), we prepending to string with length of log(n) log(n) times, can be avoided with StringBuilder and reversing at the last step

  • Space complexity: \(O(log(n))\), recursion depth

Code


    fun smallestFromLeaf(root: TreeNode?, s: String = ""): String = root?.run {
        val s = "${'a' + `val`}" + s
        if (left == null && right == null) s 
        else minOf(smallestFromLeaf(left, s), smallestFromLeaf(right, s))
    } ?: "${ 'z' + 1 }"


    pub fn smallest_from_leaf(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, s: String) -> String {
            n.as_ref().map_or("{".into(), |n| { let n = n.borrow();
                let s = ((b'a' + (n.val as u8)) as char).to_string() + &s;
                if n.left.is_none() && n.right.is_none() { s } 
                else { dfs(&n.left, s.clone()).min(dfs(&n.right, s)) }
            })
        }
        dfs(&root, "".into())
    }

16.04.2024

623. Add One Row to Tree medium blog post substack youtube 2024-04-16_08-54.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/573

Problem TLDR

Insert nodes at the depth of the Binary Tree #medium

Intuition

We can use Depth-First or Breadth-First Search

Approach

Let’s use DFS in Kotlin, and BFS in Rust. In a DFS solution we can try to use result of a function to shorten the code: to identify which node is right, mark depth as zero for it.

Complexity

  • Time complexity: \(O(n)\), for both DFS and BFS

  • Space complexity: \(O(log(n))\) for DFS, but O(n) for BFS as the last row can contain as much as n/2 items

Code


    fun addOneRow(root: TreeNode?, v: Int, depth: Int): TreeNode? = 
        if (depth < 2) TreeNode(v).apply { if (depth < 1) right = root else left = root } 
        else root?.apply {
            left = addOneRow(left, v, depth - 1)
            right = addOneRow(right, v, if (depth < 3) 0 else depth - 1)
        }


    pub fn add_one_row(mut root: Option<Rc<RefCell<TreeNode>>>, val: i32, depth: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if depth < 2 { return Some(Rc::new(RefCell::new(TreeNode { val: val, left: root, right: None }))) }
        let mut queue = VecDeque::new(); queue.push_back(root.clone());
        for _ in 2..depth { for _ in 0..queue.len() {
                if let Some(n) = queue.pop_front() { if let Some(n) = n {
                        let n = n.borrow();
                        queue.push_back(n.left.clone());
                        queue.push_back(n.right.clone());
                } }
        } }
        while queue.len() > 0 {
            if let Some(n) = queue.pop_front() { if let Some(n) = n {
                    let mut n = n.borrow_mut();
                    n.left = Some(Rc::new(RefCell::new(TreeNode { val: val, left: n.left.take(), right: None })));
                    n.right = Some(Rc::new(RefCell::new(TreeNode { val: val, left: None, right: n.right.take() })));
            } }
        }; root
    }

15.04.2024

129. Sum Root to Leaf Numbers medium blog post substack youtube 2024-04-15_07-58.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/572

Problem TLDR

Sum root-leaf numbers in a Binary Tree #medium

Intuition

Pass the number as an argument and return it on leaf nodes

Approach

I for now think it is impossible to reuse the method signature as-is and do it bottom up, at least you must return the power of 10 as an additional value.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\), for the recursion, however Morris Traversal will make it O(1)

Code


    fun sumNumbers(root: TreeNode?, n: Int = 0): Int = root?.run {
        if (left == null && right == null) n * 10 + `val` else
        sumNumbers(left, n * 10 + `val`) + sumNumbers(right, n * 10 + `val`)
    } ?: 0


    pub fn sum_numbers(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, x: i32) -> i32 {
            n.as_ref().map_or(0, |n| { let n = n.borrow();
                if n.left.is_none() && n.right.is_none() { x * 10 + n.val } else {
                    dfs(&n.left, x * 10 + n.val) + dfs(&n.right, x * 10 + n.val)
                }
            })
        }
        dfs(&root, 0)
    }

14.04.2024

404. Sum of Left Leaves easy blog post substack youtube 2024-04-14_08-17.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/571

Problem TLDR

Left-leaf sum in a Binary Tree #easy

Intuition

Do a Depth-First Search and check if left node is a leaf

Approach

Let’s try to reuse the original method’s signature.

  • in Rust Rc::clone is a cheap operation

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\), for the recursion stack space

Code


    fun sumOfLeftLeaves(root: TreeNode?): Int = root?.run {
       (left?.takeIf { it.left == null && it.right == null }?.`val` ?: 
       sumOfLeftLeaves(left)) + sumOfLeftLeaves(right)
    } ?: 0


    pub fn sum_of_left_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        root.as_ref().map_or(0, |n| { let n = n.borrow(); 
            n.left.as_ref().map_or(0, |left| { let l = left.borrow();
                if l.left.is_none() && l.right.is_none() { l.val } 
                else { Self::sum_of_left_leaves(Some(Rc::clone(left))) }
            }) +
            n.right.as_ref().map_or(0, |r| Self::sum_of_left_leaves(Some(Rc::clone(r))))
        })
    }

13.04.2024

85. Maximal Rectangle hard blog post substack youtube 2024-04-13_09-13.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/570

Problem TLDR

Max 1-only area in a 0-1 matrix #hard

Intuition

The n^4 solution is kind of trivial, just precompute the prefix sums, then do some geometry: 2024-04-13_09-101.webp

The trick here is to observe a subproblem (https://leetcode.com/problems/largest-rectangle-in-histogram/): 2024-04-13_09-102.webp This can be solved using a Monotonic Increasing Stack technique:

    //i0 1 2 3 4
    // 3 1 3 2 2
    //0*          3
    //1  *        1  
    //2    *      1 3 
    //3      *    1 3 2  -> 1 2 
    //4        *  1 2 2
    //           * empty

Pop all positions smaller than the current heights. Careful with the area calculation though, the height will be the popping one, and the width is a distance between popped and a new top.

Approach

There are some tricks:

  • using a sentinel 0-height at the end of h will help to save some lines of code
  • Stack object can be reused

Complexity

  • Time complexity: \(O(nm)\)

  • Space complexity: \(O(m)\)

Code

```kotlin []

fun maximalRectangle(matrix: Array<CharArray>): Int = with(Stack<Int>()) {
    val h = IntArray(matrix[0].size + 1)
    var max = 0
    for (y in matrix.indices) for (x in h.indices) {
        if (x < h.size - 1) h[x] = if (matrix[y][x] > '0') 1 + h[x] else 0
        while (size > 0 && h[peek()] > h[x]) 
            max = max(max, h[pop()] * if (size > 0) x - peek() - 1 else x)
        if (x < h.size - 1) push(x) else clear()
    }
    max
}
```rust 

    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let (mut st, mut h, mut max) = (vec![], vec![0; matrix[0].len() + 1], 0);
        for y in 0..matrix.len() {
            for x in 0..h.len() {
                if x < h.len() - 1 { h[x] = if matrix[y][x] > '0' { 1 + h[x] } else { 0 }}
                while st.len() > 0 && h[*st.last().unwrap()] > h[x] {
                    let l = st.pop().unwrap();
                    max = max.max(h[l] * if st.len() > 0 { x - *st.last().unwrap() - 1 } else { x })
                }
                if x < h.len() - 1 { st.push(x) } else { st.clear() }
            }
        }
        max as i32
    }

12.04.2024

42. Trapping Rain Water hard blog post substack youtube 2024-04-12_08-45.webp

Problem TLDR

Trap the water in area between vertical walls #hard

Intuition

Let’s observe some examples and try to apply decreasing stack technique somehow:

    //               #
    //       #       # #   #
    //   #   # #   # # # # # #
    //i0 1 2 3 4 5 6 7 8 91011
    // 0 1 0 2 1 0 1 3 2 1 2 1
    //0*             .          0(0)
    //1  *           .          1
    //2    *         .          1(1) 0(2)     
    //3      *       .          2(3)     + (3-2)*(1-0)
    //4        *     .          2(3) 1(4)     
    //5          *   .          2(3) 1(4) 0(5)
    //6            * .          2(3) 1(6)    + (1-0)*(5-4)
    //7              *          3(7)         + (2-1)*(6-3)

    //2#  #
    //1## #
    //0####
    // 0123
    //
    // 0 1 2 3     
    // 2 1 0 2      
    // *          2(0)
    //   *        2(0) 1(1)
    //     *      2(0) 1(1) 0(2)
    //       *    2(3)           + a=2,b=1, (i-b-1)*(h[b]-h[a])=(3-1-1)*(1-0)
    //                             a=1,b=0, (3-0-1)*(2-1)

    // #
    // #   #
    // # # #
    // # # #
    // 0 1 2
    // 4 2 3

    //           #
    // #         #
    // #     #   #
    // # #   # # #
    // # #   # # #
    // 0 1 2 3 4 5
    // 4 2 0 3 2 5

    // #         #
    // #         #
    // #         #
    // # #   #   #
    // # # # # # #
    // 0 1 2 3 4 5
    // 5 2 1 2 1 5

As we meet a new high value we can collect some water. There are corner cases when the left border is smaller than the right.

Approach

  • try to come up with as many corner cases as possible
  • horizontal width must be between the highest columns

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun trap(height: IntArray): Int = with(Stack<Int>()) {
        var sum = 0
        for ((i, hb) in height.withIndex()) {
            while (size > 0 && height[peek()] <= hb) {
                val ha = height[pop()]
                if (size > 0) sum += (i - peek() - 1) * (min(hb, height[peek()]) - ha)
            }
            push(i)
        }
        return sum
    }


    pub fn trap(height: Vec<i32>) -> i32 {
        let (mut sum, mut stack) = (0, vec![]);
        for (i, &hb) in height.iter().enumerate() {
            while stack.len() > 0 && height[*stack.last().unwrap()] <= hb {
                let ha = height[stack.pop().unwrap()];
                if stack.len() > 0 {
                    let dh = hb.min(height[*stack.last().unwrap()]) - ha;
                    sum += ((i - *stack.last().unwrap()) as i32 - 1) * dh
                }
            }
            stack.push(i)
        }
        sum
    }

11.04.2024

402. Remove K Digits medium blog post substack youtube 2024-04-11_09-09.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/568

Problem TLDR

Minimum number after removing k digits #medium

Intuition

Let’s observe some examples:

    // 1432219    k=3
    // *
    //  *       14
    //   *      13  1, remove 4
    //    *     12  2, remove 3
    //     *    122
    //      *   121 3, remove 2

    // 12321    k=1
    // *        1
    //  *       12
    //   *      123
    //    *     122, remove 3

We can use increasing stack technique to choose which characters to remove: remove all tail that less than a new added char.

Approach

We can use Stack or just a StringBuilder directly. Counter is optional, but also helps to save one line of code.

  • we can skip adding 0 when string is empty

Complexity

  • Time complexity: \(O(n)\), n^2 when using deletaAt(0), but time is almost the same (we can use a separate counter to avoid this)

  • Space complexity: \(O(n)\)

Code


    fun removeKdigits(num: String, k: Int) = buildString {
        for (i in num.indices) {
            while (i - length < k && length > 0 && last() > num[i])
                setLength(lastIndex)
            append(num[i])
        }
        while (num.length - length < k) setLength(lastIndex)
        while (firstOrNull() == '0') deleteAt(0)
    }.takeIf { it.isNotEmpty() } ?: "0"


    pub fn remove_kdigits(num: String, mut k: i32) -> String {
        let mut sb = String::with_capacity(num.len() - k as usize);
        for c in num.chars() {
            while k > 0 && sb.len() > 0 && sb.chars().last().unwrap() > c {
                sb.pop();
                k -= 1
            }
            if !sb.is_empty() || c != '0' { sb.push(c) }
        }
        for _ in 0..k { sb.pop(); }
        if sb.is_empty() { sb.push('0') }
        sb
    }

10.04.2024

950. Reveal Cards In Increasing Order medium blog post substack youtube 2024-04-10_09-01.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/567

Problem TLDR

Sort cards by rules: take top, next goes bottom #medium

Intuition

Let’s reverse the problem: go from the last number, then prepend a value and rotate.

Approach

We can use ArrayDeque in Kotlin and just a vec[] in Rust (however VecDeque is also handy and make O(1) operation instead of O(n)).

Complexity

  • Time complexity: \(O(nlogn)\), O(n^2) for vec[] solution, but the real time is still 0ms.

  • Space complexity: \(O(n)\)

Code


    fun deckRevealedIncreasing(deck: IntArray) = with(ArrayDeque<Int>()) {
        deck.sortDescending()
        for (n in deck) {
            if (size > 0) addFirst(removeLast())
            addFirst(n)
        }
        toIntArray()
    }


    pub fn deck_revealed_increasing(mut deck: Vec<i32>) -> Vec<i32> {
        deck.sort_unstable_by_key(|n| -n);
        let mut queue = vec![];
        for n in deck {
            if queue.len() > 0 { queue.rotate_right(1) }
            queue.insert(0, n)
        }
        queue
    }

09.04.2024

2073. Time Needed to Buy Tickets easy blog post substack youtube 2024-04-09_08-27.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/565

Problem TLDR

Seconds to buy tickets by k-th person in a rotating 1 second queue #easy

Intuition

The brute-force implementation is trivial: just repeat decreasing tickets[i] untile tickets[k] == 0. It will take at most O(n^2) time.

However, there is a one-pass solution. To get the intuition go to the comment section… just a joke. We take tickets[k] for people before k and we don’t take last round tickets for people after k, so only tickets[k] - 1.

Approach

Let’s use some iterators to reduce the number of lines of code: sumOf, withIndex or iter().enumerate(),

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun timeRequiredToBuy(tickets: IntArray, k: Int) =
        tickets.withIndex().sumOf { (i, t) ->
            min(tickets[k] - (if (i > k) 1 else 0), t)
    }


    pub fn time_required_to_buy(tickets: Vec<i32>, k: i32) -> i32 {
        tickets.iter().enumerate().map(|(i, &t)| 
            t.min(tickets[k as usize] - i32::from(i > k as usize))).sum()
    }

08.04.2024

1700. Number of Students Unable to Eat Lunch easy blog post substack youtube 2024-04-08_08-24.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/564

Problem TLDR

First sandwitch not eaten by any while popped from a queue #easy

Intuition

First, understant the problem: we searching the first sandwitch which none of the students are able to eat. The simulation code is straighforward and takes O(n^2) time which is accepted. However, we can count how many students are 0-eaters and how many 1-eaters, then stop when none are able to eat current sandwitch.

Approach

We can use two counters or one array. How many lines of code can you save?

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun countStudents(students: IntArray, sandwiches: IntArray): Int {
        val count = IntArray(2)
        for (s in students) count[s]++
        for ((i, s) in sandwiches.withIndex()) 
            if (--count[s] < 0) return students.size - i
        return 0
    }


    pub fn count_students(students: Vec<i32>, sandwiches: Vec<i32>) -> i32 {
        let (mut count, n) = (vec![0; 2], students.len());
        for s in students { count[s as usize] += 1 }
        for (i, &s) in sandwiches.iter().enumerate() {
            count[s as usize] -= 1;
            if count[s as usize] < 0 { return (n - i) as i32 }
        }; 0
    }

07.04.2024

678. Valid Parenthesis String medium blog post substack youtube 2024-04-07_08-18.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/563

Problem TLDR

Are parenthesis valid with wildcard? #medium

Intuition

Let’s observe some examples:

     *(    w  o
     *     1
      (       1

     (*(*( 

     )*
     o < 0

     **((
       ^

As we can see, for example **(( the number of wildcards matches with the number of non-matched parenthesis, and the entire sequence is invalid. However, this sequence in reverse order ))** is simple to resolve with just a single counter. So, the solution would be to use a single counter and check sequence in forward and in reverse order.

Another neat trick that I wouldn’t invent myself in a thousand years, is to consider the open counter as a RangeOpen = (min..max), where every wildcard broadens this range.

Approach

Let’s implement both solutions.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun checkValidString(s: String): Boolean {
        var open = 0
        for (c in s)
            if (c == '(' || c == '*') open++
            else if (c == ')' && --open < 0) return false
        open = 0
        for (i in s.lastIndex downTo 0) 
            if (s[i] == ')' || s[i] == '*') open++
            else if (s[i] == '(' && --open < 0) return false
        return true
    }


    pub fn check_valid_string(s: String) -> bool {
        let mut open = (0, 0);
        for b in s.bytes() {
            if b == b'(' { open.0 += 1; open.1 += 1 }
            else if b == b')' { open.0 -= 1; open.1 -= 1 }
            else { open.0 -= 1; open.1 += 1 }
            if open.1 < 0 { return false }
            if open.0 < 0 { open.0 = 0 }
        }
        open.0 == 0
    }

06.04.2024

1249. Minimum Remove to Make Valid Parentheses medium blog post substack youtube 2024-04-06_08-43.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/562

Problem TLDR

Remove minimum to make parenthesis valid #medium

Intuition

Let’s imagine some examples to better understand the problem:

     (a
     a(a
     a(a()
     (a))a

We can’t just append chars in a single pass. For example (a we don’t know if open bracket is valid or not. The natural idea would be to use a Stack somehow, but it is unknown how to deal with letters then. For this example: (a))a, we know that the second closing parenthesis is invalid, so the problem is straighforward. Now the trick is to reverse the problem for this case: (a -> a).

Approach

How many lines of code can you save?

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun minRemoveToMakeValid(s: String) = buildString {
        var open = 0
        for (c in s) {
            if (c == '(') open++
            if (c == ')') open--
            if (open >= 0) append(c)
            open = max(0, open)
        }
        for (i in length - 1 downTo 0) if (get(i) == '(') {
            if (--open < 0) break
            deleteAt(i)
        }
    }


    pub fn min_remove_to_make_valid(s: String) -> String {
        let (mut open, mut res) = (0, vec![]);
        for b in s.bytes() {
            if b == b'(' { open += 1 }
            if b == b')' { open -= 1 }
            if open >= 0 { res.push(b) }
            open = open.max(0)
        }
        for i in (0..res.len()).rev() {
            if open == 0 { break }
            if res[i] == b'(' {
                res.remove(i);
                open -= 1
            }
        }
        String::from_utf8(res).unwrap()
    }

05.04.2024

1544. Make The String Great easy blog post substack youtube

2024-04-05_08-24.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/561

Problem TLDR

Remove lowercase-uppercase pairs #easy

Intuition

Consider example:

    EbBe
     **
    E  e
    

After removing the middle bB we have to consider the remaining Ee. We can use Stack to do that.

Approach

In Kotlin: no need for Stack, just use StringBuilder. In Rust: Vec can be used as a Stack. There is no to_lowercase method returning a char, however there is a to_ascii_lowercase.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


  fun makeGood(s: String) = buildString {
    for (c in s)
      if (length > 0 && c != get(lastIndex) && 
        c.lowercase() == get(lastIndex).lowercase()
      ) setLength(lastIndex) else append(c)
  }


  pub fn make_good(s: String) -> String {
    let mut stack = vec![];
    for c in s.chars() {
      if stack.is_empty() { stack.push(c) }
      else {
        let p = *stack.last().unwrap();
        if c != p && c.to_lowercase().eq(p.to_lowercase()) {
          stack.pop();
        } else { stack.push(c) }
      }
    }
    stack.iter().collect()
  }

04.04.2024

1614. Maximum Nesting Depth of the Parentheses easy blog post substack youtube 2024-04-04_09-03.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/560

Problem TLDR

Max nested parenthesis #easy

Intuition

No special intuition, just increase or decrease a counter.

Approach

  • There is a maxOf in Kotlin, but solution is not pure functional. It can be with fold.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


  fun maxDepth(s: String): Int {
    var curr = 0
    return s.maxOf { 
      if (it == '(') curr++
      if (it == ')') curr--
      curr
    }
  }


  pub fn max_depth(s: String) -> i32 {
    let (mut curr, mut max) = (0, 0);
    for b in s.bytes() {
      if b == b'(' { curr += 1 }
      if b == b')' { curr -= 1 }
      max = max.max(curr)
    }
    max
  }

03.04.2024

79. Word Search medium blog post substack youtube 2024-04-03_08-01.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/559

Problem TLDR

Does grid have a word path? #medium

Intuition

Simple Depth-First Search for every starting point will give the answer. One trick is to store visited set in a grid itself.

Approach

  • Use dummy char to mark visited in a path.
  • Don’t forget to restore back.
  • Only mark visited right before traveling to the next to avoid failing at restoring.

Complexity

  • Time complexity: \(O(n3^n)\), n is a grid area

  • Space complexity: \(O(n)\)

Code


  fun exist(board: Array<CharArray>, word: String): Boolean {
    fun dfs(x: Int, y: Int, i: Int): Boolean {
      if (i == word.length) return true
      if (x !in 0..<board[0].size || y !in 0..<board.size) return false
      val c = board[y][x]
      if (c != word[i]) return false
      board[y][x] = '.'
      val res = dfs(x - 1, y, i + 1) || dfs(x + 1, y, i + 1)
             || dfs(x, y - 1, i + 1) || dfs(x, y + 1, i + 1)
      board[y][x] = c
      return res
    }
    for (y in 0..<board.size) for (x in 0..<board[0].size)
      if (dfs(x, y, 0)) return true
    return false
  }


  pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
    fn dfs(mut board: &mut Vec<Vec<char>>, word: &String, x: i32, y: i32, i: usize) -> bool {
      if i == word.len() { return true }
      if x < 0 || y < 0 || x == board[0].len() as i32 || y == board.len() as i32 { return false }
      let c = board[y as usize][x as usize];
      if c as u8 != word.as_bytes()[i] { return false }
      board[y as usize][x as usize] = '.';
      let res = 
        dfs(board, word, x - 1, y, i + 1) || dfs(board, word, x + 1, y, i + 1) ||
        dfs(board, word, x, y - 1, i + 1) || dfs(board, word, x, y + 1, i + 1);
      board[y as usize][x as usize] = c; res
    }
    let (n, m) = (board.len() as i32, board[0].len() as i32);
    for y in 0..n { for x in 0..m {
      if dfs(&mut board, &word, x, y, 0) { return true }
    }}
    false
  }

02.04.2024

205. Isomorphic Strings easy blog post substack youtube 2024-04-02_08-59.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/558

Problem TLDR

Can map chars from one string to another? #easy

Intuition

Let’s check if previous mapping is the same, otherwise result is false

Approach

We can use a HashMap or a simple [128] array.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(w)\), w is an alphabet or O(1)

Code


  fun isIsomorphic(s: String, t: String): Boolean {
    val map = mutableMapOf<Char, Char>()
    val map2 = mutableMapOf<Char, Char>()
    for ((i, c) in s.withIndex()) {
      if (map[c] != null && map[c] != t[i]) return false
      map[c] = t[i]
      if (map2[t[i]] != null && map2[t[i]] != c) return false
      map2[t[i]] = c
    }
    return true
  }


  pub fn is_isomorphic(s: String, t: String) -> bool {
    let mut m1 = vec![0; 128]; let mut m2 = m1.clone();
    for i in 0..s.len() {
      let c1 = s.as_bytes()[i] as usize;
      let c2 = t.as_bytes()[i] as usize;
      if m1[c1] > 0 && m1[c1] != c2 { return false }
      if m2[c2] > 0 && m2[c2] != c1 { return false }
      m1[c1] = c2; m2[c2] = c1
    }
    return true
  }

01.04.2024

58. Length of Last Word easy blog post substack youtube 2024-04-01_08-06.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/557

Problem TLDR

Last word length #easy

Intuition

There are many ways, let’s try to write an efficient solution. Iterate from the end, stop after the first word.

Approach

In Kotlin we can use first, takeWhile and count. In Rust let’s to write a simple for loop over bytes.

Complexity

  • Time complexity: \(O(w + b)\), where w is a last word length, and b suffix blank space length

  • Space complexity: \(O(1)\)

Code


  fun lengthOfLastWord(s: String) =
    ((s.lastIndex downTo 0).first { s[it] > ' ' } downTo 0)
    .asSequence().takeWhile { s[it] > ' ' }.count()


  pub fn length_of_last_word(s: String) -> i32 {
    let mut c = 0;
    for b in s.bytes().rev() {
      if b > b' ' { c += 1 } else if c > 0 { return c }
    }
    c
  }

31.03.2024

2444. Count Subarrays With Fixed Bounds hard blog post substack youtube 2024-03-31_12-25.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/555

Problem TLDR

Count subarrays of range minK..maxK #hard

Intuition

“all hope abandon ye who enter here” I’ve failed this question the second time (first was 1 year ago), and still find it very clever.

Consider the safe space as min(a, b)..max(a,b) where a is the last index of minK and b is the last index of maxK. We will remove suffix of 0..j where j is a last out of range minK..maxK.

Let’s examine the trick:


  // 1 3 5 2 7 5      1..5
  //j 
  //a 
  //b 
  // i
  // a
  //   i
  //     i
  //     b           +1 = min(a, b) - j = (0 - (-1))
  //       i         +1 = ...same...

another example:


  // 0 1 2 3 4 5 6
  // 7 5 2 2 5 5 1     
  //j      .
  //i      .
  //a
  //b
  // i     .
  // j     .
  //   i   .
  //   b   .
  //     i .
  //     a .         +1
  //       i
  //       a         +1
  //         i
  //         b       +3 = 3 - 0
  //           i
  //           b     +3

The interesting part happen at the index i = 4: it will update the min(a, b), making it a = 3.

Basically, every subarray starting between j..(min(a, b)) and ending at i will have minK and maxK, as min(a,b)..max(a,b) will have them.

Approach

Try to solve it yourself first.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


  fun countSubarrays(nums: IntArray, minK: Int, maxK: Int): Long {
    var res = 0L; var a = -1; var j = -1; var b = -1
    for ((i, n) in nums.withIndex()) {
      if (n == minK) a = i 
      if (n == maxK) b = i
      if (n !in minK..maxK) j = i
      res += max(0, min(a, b) - j)
    }
    return res
  }


  pub fn count_subarrays(nums: Vec<i32>, min_k: i32, max_k: i32) -> i64 {
    let (mut res, mut a, mut b, mut j) = (0, -1, -1, -1);
    for (i, &n) in nums.iter().enumerate() {
      if n == min_k { a = i as i64 }
      if n == max_k { b = i as i64 }
      if n < min_k || n > max_k { j = i as i64 }
      res += (a.min(b) - j).max(0)
    }
    res
  }

30.03.2024

992. Subarrays with K Different Integers hard blog post substack youtube 2024-03-30_10-33.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/554

Problem TLDR

Count subarrays with k distinct numbers #hard

Intuition

We surely can count at most k numbers using sliding window technique: move the right pointer one step at a time, adjust the left pointer until condition met. All subarrays start..k where start in 0..j will have more or equal than k number of distincts if j..k have exatly k of them, so take j at each step.

To count exactly k we can remove subset of at least k from at least k - 1. (The trick here is that the number of at least k - 1 is the bigger one)

Approach

Let’s use a HashMap and some languages sugar:

  • Kotlin: sumOf
  • Rust: lambda to capture the parameters, entry.or_insert

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\), we have a frequencies stored in a map, can be up to n

Code


  fun subarraysWithKDistinct(nums: IntArray, k: Int): Int {
    fun countAtLeast(k: Int): Int {
      val freq = mutableMapOf<Int, Int>()
      var j = 0; var count = 0
      return nums.indices.sumOf { i -> 
        freq[nums[i]] = 1 + (freq[nums[i]] ?: 0)
        if (freq[nums[i]] == 1) count++
        while (count > k) {
          freq[nums[j]] = freq[nums[j]]!! - 1
          if (freq[nums[j++]] == 0) count--
        }
        j
      }
    }
    return countAtLeast(k - 1) - countAtLeast(k)
  }


  pub fn subarrays_with_k_distinct(nums: Vec<i32>, k: i32) -> i32 {
    let count_at_least = |k: i32| -> i32 {
      let (mut freq, mut j, mut count) = (HashMap::new(), 0, 0);
      (0..nums.len()).map(|i| {
        *freq.entry(&nums[i]).or_insert(0) += 1;
        if freq[&nums[i]] == 1  { count += 1 }
        while count > k {
          *freq.get_mut(&nums[j]).unwrap() -= 1;
          if freq[&nums[j]] == 0 { count -= 1}
          j += 1;
        }
        j as i32
      }).sum()
    };
    count_at_least(k - 1) - count_at_least(k)
  }

29.03.2024

2962. Count Subarrays Where Max Element Appears at Least K Times medium blog post substack youtube 2024-03-29_09-26.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/553

Problem TLDR

Count subarrays with at least k array max in #medium

Intuition

Let’s observe an example 1 3 3:

    // inverse the problem
    // [1], [3], [3], [1 3], [1 3 3], [3 3] // 6
    // 1 3 3     ck  c
    // j .
    // i .           1
    //   i        1  3
    //     i      2
    //   j         
    //     j      1  4
    //                          6-4=2

The problem is more simple if we invert it: count subarrays with less than k maximums. Then it is just a two-pointer problem: increase by one, then shrink until condition < k met.

Another way, is to solve problem at face: left border is the count we need - all subarrays before our j..i will have k max elements if j..i have them.

Approach

Let’s implement both.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


  fun countSubarrays(nums: IntArray, k: Int): Long {
    val n = nums.size.toLong()
    val m = nums.max(); var ck = 0; var j = 0
    return n * (n + 1) / 2 + nums.indices.sumOf { i ->
      if (nums[i] == m) ck++
      while (ck >= k) if (nums[j++] == m) ck--
      -(i - j + 1).toLong()
    }
  }


  pub fn count_subarrays(nums: Vec<i32>, k: i32) -> i64 {
    let (mut j, mut curr, m) = (0, 0, *nums.iter().max().unwrap());
    (0..nums.len()).map(|i| {
      if nums[i] == m { curr += 1 }
      while curr >= k { if nums[j] == m { curr -= 1 }; j += 1 }
      j as i64
    }).sum()
  }

28.03.2024

2958. Length of Longest Subarray With at Most K Frequency medium blog post substack youtube 2024-03-28_09-04.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/552

Problem TLDR

Max subarray length with frequencies <= k #medium

Intuition

There is a known sliding window pattern: right pointer will increase the frequency and left pointer will decrease it. Not try to expand as much as possible, then shrink until conditions are met.

Approach

  • move the right pointer one position at a time
  • we can use maxOf in Kotlin or max in Rust

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


  fun maxSubarrayLength(nums: IntArray, k: Int): Int {
    val freq = mutableMapOf<Int, Int>(); var j = 0
    return nums.indices.maxOf { i ->
      freq[nums[i]] = 1 + (freq[nums[i]] ?: 0)
      while (freq[nums[i]]!! > k) 
        freq[nums[j]] = freq[nums[j++]]!! - 1
      i - j + 1
    }
  }


    pub fn max_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
      let (mut freq, mut j) = (HashMap::new(), 0);
      (0..nums.len()).map(|i| {
        *freq.entry(nums[i]).or_insert(0) += 1;
        while freq[&nums[i]] > k {
          *freq.get_mut(&nums[j]).unwrap() -= 1; j += 1
        }
        i - j + 1
      }).max().unwrap() as i32
    }

27.03.2024

713. Subarray Product Less Than K medium blog post substack youtube 2024-03-27_09-18.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/551

Problem TLDR

Subarrays count with product less than k #medium

Intuition

Let’s try to use two pointers and move them only once:

  // 10 5 2 6 1 1 1                    cnt
  // i                    10           1
  // j          
  // *  j                 50 +5        3
  //    * j               (100) +2     4
  //    i                 10           5
  //    * * j             60 +6        7
  //    * * * j           60 +1        9
  //    * * * * j         60 +1        11
  //    * * * * * j       60 +1        13
  //      i * * * *       12 +1        15
  //        i * * *       6 +1         17
  //          i * *       1 +1         19
  //            i *       1 +1         21
  //              i       1 +1         23

As we notice, this way gives the correct answer. Expand the first pointer while p < k, then shrink the second pointer.

Approach

Next, some tricks:

  • move the right pointer once at a time
  • move the second until conditions are met
  • adding (i - j) helps to avoid moving the left pointer
  • if we handle the corner cases of k = 0 and k = 1, we can use some optimizations: nums[j] will always be less than k after while loop; and i will always be less than i in a while loop.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


  fun numSubarrayProductLessThanK(nums: IntArray, k: Int): Int {
    var i = 0; var j = 0; var res = 0; var p = 1
    if (k < 2) return 0
    for (j in nums.indices) {
      p *= nums[j]
      while (p >= k) p /= nums[i++]
      res += j - i + 1
    }
    return res
  }


  pub fn num_subarray_product_less_than_k(nums: Vec<i32>, k: i32) -> i32 {
    if k < 2 { return 0 }
    let (mut j, mut p, mut res) = (0, 1, 0);
    for i in 0..nums.len() {
      p *= nums[i];
      while p >= k { p /= nums[j]; j += 1 }
      res += i - j + 1
    }
    res as i32
  }

26.03.2024

41. First Missing Positive hard blog post substack youtube 2024-03-26_09-20.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/550

Problem TLDR

First number 1.. not presented in the array, O(1) space #hard

Intuition

Let’s observe some examples. The idea is to use the array itself, as there is no restriction to modify it:

  /*
  1 -> 2 -> 3 ...

  0 1 2
  1 2 0
  *      0->1->2->0
  0 1 2

  0 1  2 3
  3 4 -1 1
  *         0 -> 3, 3 -> 1, 1 -> 4
  0 1    3 4
       *     2 -> -1

  7 8 9 11 12  1->

   */

We can use the indices of array: every present number must be placed at it’s index. As numbers are start from 1, we didn’t care about anything bigger than nums.size.

Approach

  • careful with of-by-one’s, 1 must be placed at 0 index and so on.

Complexity

  • Time complexity: \(O(n)\), at most twice if all numbers are present in array

  • Space complexity: \(O(1)\)

Code


  fun firstMissingPositive(nums: IntArray): Int {
    for (i in nums.indices)
      while ((nums[i] - 1) in 0..<nums.size && nums[nums[i] - 1] != nums[i]) 
        nums[nums[i] - 1] = nums[i].also { nums[i] = nums[nums[i] - 1] }
    return nums.indices.firstOrNull { nums[it] != it + 1 }?.inc() ?: nums.size + 1
  }


  pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
    let n = nums.len() as i32;
    for i in 0..nums.len() {
      let mut j = nums[i] - 1;
      while 0 <= j && j < n && nums[j as usize] != j + 1 {
        let next = nums[j as usize] - 1;
        nums[j as usize] = j + 1;
        j = next
      }
    }
    for i in 0..n { if nums[i as usize] != i + 1 { return i + 1 }}
    n + 1
  }

25.03.2024

442. Find All Duplicates in an Array medium blog post substack youtube 2024-03-25_09-19.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/549

Problem TLDR

All duplicate numbers of 1..n using O(1) memory #medium

Intuition

There are no restrictions not to modify the input array, so let’s flat all visited numbers with a negative sign:


  // 1 2 3 4 5 6 7 8
  // 4 3 2 7 8 2 3 1
  // *     -
  //   * -
  //   - *
  //       *     -
  //         *     -
  //     -     *       --2
  //   -         *     --3
  // -             *

Inputs are all positive, the corner cases of negatives and zeros are handled.

Approach

  • don’t forget to abs
  • Rust didn’t permit to iterate and modify at the same time, use pointers

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


  fun findDuplicates(nums: IntArray) = buildList {
    for (x in nums) {
      if (nums[abs(x) - 1] < 0) add(abs(x))
      nums[abs(x) - 1] *= -1
    }
  }


  pub fn find_duplicates(mut nums: Vec<i32>) -> Vec<i32> {
    let mut res = vec![];
    for j in 0..nums.len() {
      let i = (nums[j].abs() - 1) as usize;
      if nums[i] < 0 { res.push(nums[j].abs()) }
      nums[i] *= -1
    }
    res
  }

24.03.2024

287. Find the Duplicate Number medium blog post substack youtube 2024-03-24_11-13_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/548

Problem TLDR

Duplicate single number in 1..n array, no extra memory #medium

Intuition

The idea of existing cycle would come to mind after some hitting your head against the wall. The interesting fact is we must find the node that is not a port of the cycle: so the meeting point will be our answer: 2024-03-24_10-35.jpg Now the clever trick is we can treat node 0 as this external node: 2024-03-24_10-55.jpg This will coincidentally make our code much cleaner, I think this was the intention of the question authors.

Approach

Draw some circles and arrows, walk the algorithm with your hands. To find the meeting point you must reset one pointer to the start.

  • The Rust’s do-while-do loop is perfectly legal https://programming-idioms.org/idiom/78/do-while-loop/795/rust

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


  fun findDuplicate(nums: IntArray): Int {
    var fast = 0; var slow = 0
    do {
      fast = nums[nums[fast]]
      slow = nums[slow]
    } while (fast != slow)
    slow = 0
    while (fast != slow) {
      fast = nums[fast]
      slow = nums[slow]
    }
    return slow
  }


  pub fn find_duplicate(nums: Vec<i32>) -> i32 {
    let (mut tortoise, mut hare) = (0, 0); 
    while {
      hare = nums[nums[hare as usize] as usize];
      tortoise = nums[tortoise as usize];
      hare != tortoise
    }{}
    hare = 0;
    while (hare != tortoise) {
      hare = nums[hare as usize];
      tortoise = nums[tortoise as usize]
    }
    tortoise
  }

23.03.2024

143. Reorder List medium blog post substack youtube 2024-03-23_11-24.jpg

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/547

Problem TLDR

Reorder Linked List 1->2->3->4->5 -> 1->5->2->4->3 #medium

Intuition

There are no special hints here. However, the optimal solution will require some tricks:

  • use Tortoise And Hare algorithm to find the middle
  • reverse the second half
  • merge two lists

Approach

  • Tortoise And Hare: check fast.next != null to stop right at the middle
  • merge lists cleverly: always one into another and swap the points (don’t do this on the interview however, not from the start at least)
  • Rust: just gave up and implemented clone()-solution, sorry

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\), O(n) for my Rust solution. There are O(1) solutions exists on the leetcode.

Code


  fun reorderList(head: ListNode?): Unit {
    var s = head; var f = s
    while (f?.next != null) {
      f = f?.next?.next
      s = s?.next
    }
    f = null
    while (s != null) {
      val next = s.next
      s.next = f
      f = s
      s = next
    }
    s = head
    while (s != null) {
      val next = s.next
      s.next = f
      s = f
      f = next
    }
  }


  pub fn reorder_list(mut head: &mut Option<Box<ListNode>>) {
    let (mut f, mut s, mut c) = (head.clone(), head.clone(), 0);
    while f.is_some() && f.as_mut().unwrap().next.is_some()  {
      f = f.unwrap().next.unwrap().next;
      s = s.unwrap().next; c += 1
    }
    if c < 1 { return }
    let mut prev = None;
    while let Some(mut s_box) = s {
      let next = s_box.next;
      s_box.next = prev;
      prev = Some(s_box);
      s = next;
    }
    let mut s = head;
    while let Some(mut s_box) = s.take() {
      let next = s_box.next;
      if prev.is_none() && !f.is_some() || next.is_none() && f.is_some()  { 
        s_box.next = None;
        return;
      }
      s_box.next = prev;
      s = &mut s.insert(s_box).next;
      prev = next;
    }
  }

22.03.2024

234. Palindrome Linked List easy blog post substack youtube 2024-03-22_10-03.jpg

Problem TLDR

Is Linked List a palindrome #easy

Intuition

Find the middle using tortoise and hare algorithm and reverse it simultaneously.

Approach

  • the corners case is to detect odd or even count of nodes and do the extra move
  • gave up on the Rust solution without clone()

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\), O(n) in Rust

Code


  fun isPalindrome(head: ListNode?): Boolean {
    var fast = head; var slow = head
    var prev: ListNode? = null
    while (fast?.next != null) {
      fast = fast?.next?.next
      val next = slow?.next
      slow?.next = prev
      prev = slow
      slow = next
    }
    if (fast != null) slow = slow?.next
    while (prev != null && prev?.`val` == slow?.`val`)
      prev = prev?.next.also { slow = slow?.next }
    return prev == null
  }


  pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
    let (mut fast, mut slow, mut prev) = (head.clone(), head, None);
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        fast = fast.unwrap().next.unwrap().next;
        let mut slow_box = slow.unwrap();
        let next = slow_box.next;
        slow_box.next = prev;
        prev = Some(slow_box);
        slow = next
    }
    if fast.is_some() { slow = slow.unwrap().next }
    while let Some(prev_box) = prev {
      let slow_box = slow.unwrap();
      if prev_box.val != slow_box.val { return false }
      prev = prev_box.next; slow = slow_box.next
    }; true
  }

21.03.2024

206. Reverse Linked List easy blog post substack youtube 2024-03-21_09-47.jpg

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/545

Problem TLDR

Reverse a Linked List #easy

Intuition

We need at least two pointers to store current node and previous.

Approach

In a recursive approach:

  • treat result as a new head
  • erase the link to the next
  • next.next must point to the current

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\) or log(n) for the recursion

Code


  fun reverseList(head: ListNode?): ListNode? =
    head?.next?.let { next ->
      head.next = null
      reverseList(next).also { next?.next = head }
    } ?: head


  pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut curr = head; let mut prev = None;
    while let Some(mut curr_box) = curr {
      let next = curr_box.next;
      curr_box.next = prev;
      prev = Some(curr_box);
      curr = next;
    }
    prev
  }

Bonus: just a single pointer solution


  fun reverseList(head: ListNode?): ListNode? {
    var prev = head
    while (head?.next != null) {
      val next = head?.next?.next
      head?.next?.next = prev
      prev = head?.next
      head?.next = next
    }
    return prev
  }

2024-03-21_13-02.jpg

20.03.2024

1669. Merge In Between Linked Lists medium blog post substack youtube 2024-03-20_09-48.jpg

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/544

Problem TLDR

Replace a segment in a LinkedList #medium

Intuition

Just careful pointers iteration.

Approach

  • use dummy to handle the first node removal
  • better to write a separate cycles
  • Rust is hard

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


  fun mergeInBetween(list1: ListNode?, a: Int, b: Int, list2: ListNode?) = 
    ListNode(0).run {
      next = list1
      var curr: ListNode? = this
      for (i in 1..a) curr = curr?.next
      var after = curr?.next
      for (i in a..b) after = after?.next
      curr?.next = list2
      while (curr?.next != null) curr = curr?.next
      curr?.next = after
      next
    }


  pub fn merge_in_between(list1: Option<Box<ListNode>>, a: i32, b: i32, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode::new(0));
    dummy.next = list1;
    let mut curr = &mut dummy;
    for _ in 0..a { curr = curr.next.as_mut().unwrap() }
    let mut after = &mut curr.next;
    for _ in a..=b { after = &mut after.as_mut().unwrap().next }
    let after_b = after.take(); // Detach the rest of the list after `b`, this will allow the next line for the borrow checker
    curr.next = list2;
    while let Some(ref mut next) = curr.next { curr = next; }
    curr.next = after_b;
    dummy.next
  }

19.03.2024

621. Task Scheduler medium blog post substack youtube 2024-03-19_10-10.jpg https://youtu.be/8t1KNa9iZjA

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/543

Problem TLDR

Count CPU cycles if task can’t run twice in n cycles #medium

Intuition

Let’s try to understand the problem first, by observing the example:

    // 0 1 2 3 4 5 6 7
    // a a a b b b c d n = 3
    // a . . . a . . . a
    //   b . . . b .