LeetCode Entry

1526. Minimum Number of Increments on Subarrays to Form a Target Array

30.10.2025 hard 2025 kotlin rust

Min +1 range increases to make target from zeros

1526. Minimum Number of Increments on Subarrays to Form a Target Array hard blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1158

Problem TLDR

Min +1 range increases to make target from zeros #hard

Intuition

    // *********  1
    // **  *****  2, 3
    // **  ** **  4, 5, 6
    //     *      7
    // 331143233

    // 6 7 7 2 1 2 2 1 3
    // 6                   6 levels
    //   7                 +1 level, (6..1 levels continue)
    //     7               +0 levels, (7..1 levels continue)
    //       2             -5 levels (7..3 stop, 2..1 continue) +5 ops
    //         1           -1        (2..2 stop, 1..1 continue) +1 ops
    //           2         +1        (1..2 continue)
    //             2       +0
    //               1     -1        (2..2 stop, 1..1 continue) +1 ops
    //                 3   +2        1..3 continue
    //                  end          (1..3 stop) +2 ops and +1 for level 1

Optimal strategy is the Tetris game: remove islands from the bottom. The number of ops is the number of islands. The number of islands is the number of decreases.

Approach

• draw the picture
• assume algorithm is linear, try to gain as much information at each step as possible

Complexity

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

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

Code

// 58ms
    fun minNumberOperations(t: IntArray) =
        t.zip(t.drop(1)+0).sumOf { (a,b) -> max(0, a-b)}

// 0ms
    pub fn min_number_operations(t: Vec<i32>) -> i32 {
        t[0] + t.windows(2).map(|w| 0.max(w[1]-w[0])).sum::<i32>()
    }