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

Problem Link

Description

You are given an integer array target. You have an integer array initial of the same size as target with all elements initially zeros.

In one operation you can choose any subarray from initial and increment each value by one.

Return the minimum number of operations to form a target array from initial.

The test cases are generated so that the answer fits in a 32-bit integer.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: target = [3,1,5,4,2,3,4,2]

Output: 9

Explanation: [0,0,0,0,0,0,0,0] -> [1,1,1,1,1,1,1,1] -> [2,1,1,1,1,1,1,1] -> [3,1,1,1,1,1,1,1] -> [3,1,2,2,2,2,2,2] -> [3,1,2,2,2,3,3,2] -> [3,1,2,2,2,3,4,2] -> [3,1,3,3,2,3,4,2] -> [3,1,4,4,2,3,4,2] -> [3,1,5,4,2,3,4,2].

Example 2:

Input: target = [3,1,1,2]

Output: 4

Explanation: [0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2].

Constraints:

  • 1 <= target.length <= 100,000
  • 1 <= target[i] <= 100,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Simulation

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        def rec(l, r, h):
            if l > r:
                return 0

            minIdx = l
            for i in range(l + 1, r + 1):
                if target[i] < target[minIdx]:
                    minIdx = i

            res = target[minIdx] - h
            return res + rec(l, minIdx - 1, target[minIdx]) + rec(minIdx + 1, r, target[minIdx])

        return rec(0, len(target) - 1, 0)

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n) for recursion stack.

2. Segment Tree

INF = float('inf')

class SegmentTree:
    def __init__(self, A):
        self.A = A[:]
        self.n = len(A)
        while (self.n & (self.n - 1)) != 0:
            self.A.append(INF)
            self.n += 1

        self.tree = [0] * (2 * self.n)
        self.build()

    def build(self):
        for i in range(self.n):
            self.tree[self.n + i] = i
        for j in range(self.n - 1, 0, -1):
            a = self.tree[j << 1]
            b = self.tree[(j << 1) | 1]
            self.tree[j] = a if self.A[a] <= self.A[b] else b

    def update(self, i, val):
        self.A[i] = val
        j = (self.n + i) >> 1
        while j >= 1:
            a = self.tree[j << 1]
            b = self.tree[(j << 1) | 1]
            self.tree[j] = a if self.A[a] <= self.A[b] else b
            j >>= 1

    def query(self, ql, qh):
        return self._query(1, 0, self.n - 1, ql, qh)

    def _query(self, node, l, h, ql, qh):
        if ql > h or qh < l:
            return -1
        if l >= ql and h <= qh:
            return self.tree[node]
        mid = (l + h) >> 1
        a = self._query(node << 1, l, mid, ql, qh)
        b = self._query((node << 1) | 1, mid + 1, h, ql, qh)

        if a == -1: return b
        if b == -1: return a
        return a if self.A[a] <= self.A[b] else b

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        seg = SegmentTree(target)
        stack = [(0, len(target) - 1, 0)]
        res = 0

        while stack:
            l, r, h = stack.pop()
            if l > r:
                continue
            minIdx = seg.query(l, r)
            res += target[minIdx] - h
            stack.append((l, minIdx - 1, target[minIdx]))
            stack.append((minIdx + 1, r, target[minIdx]))

        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(n)O(n)

3. Greedy

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        res = target[0]
        for i in range(1, len(target)):
            res += max(target[i] - target[i - 1], 0)
        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)