Problem statement

https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/

Solution

If we consider our heights as columns on a square grid, we can notice that one operation corresponds to laying out continuous row of bricks. To find out number of rows, we can count number of left edges of these rows.

Complexity

It is just O(n) for time and O(1) for space.

Code

class Solution:
    def minNumberOperations(self, A):
        return sum(max(b - a, 0) for b, a in zip(A, [0] + A))

Solution 2

There is a solution with segment tree: we need to answer the following queries: Given range [r, l], find the index of smallest element (any smallest element is good). Then we separate list into two parts and run it recursively. Note, that we need index, not value.

Complexity

Time complexity is potentially O(n log n).

Code

class SegmentTree:
    def __init__(self, n, arr):
        self.nums = [n for _ in range(1<<(n.bit_length() + 1))] 
        self.arr = arr + [float("inf")]
        self.n = n

    def build(self, t, l, r):
        if l == r: 
            self.nums[t] = l
        else:
            mid = (l + r)//2
            self.build(2*t, l, mid)
            self.build(2*t+1, mid+1, r)
            L, R = self.nums[2*t], self.nums[2*t + 1]
            self.nums[t] = L if self.arr[L] <= self.arr[R] else R

    def query(self, t, l, r, ql, qr):
        if l > qr or r < ql: return self.n
        if l >= ql and r <= qr: return self.nums[t]
        m = (l + r)//2
        L, R = self.query(2*t, l, m, ql, qr), self.query(2*t+1, m+1, r, ql, qr)
        L, R = min(L, self.n), min(R, self.n)
        return L if self.arr[L] <= self.arr[R] else R

    def find(self, val, l, r):
        if l > r: return 0
        q = self.query(1, 0, self.n - 1, l, r)
        v = self.arr[q] - val
        return v + self.find(self.arr[q], l, q-1) + self.find(self.arr[q], q+1, r)

class Solution:
    def minNumberOperations(self, A):
        n = len(A)
        Tree = SegmentTree(n, A)
        Tree.build(1, 0, n-1)
        return Tree.find(0, 0, n-1)

Solution 3

There is also solution, using sparse table data structure. The idea is to build table, then we can answer queries in O(1) time

Complexity

Time complexity to build sparse table is O(n log n). Then when it built, function query will work in O(1), and find will be potentially run n times. Space complexity is O(n log n) as well.

Code

class Solution:
    def minNumberOperations(self, arr):
        n, logs = len(arr), [0]*(len(arr) + 1)
        K = n.bit_length()
        for i in range(2, n+1):
            logs[i] = logs[i//2] + 1

        st = [[(s, i) for i, s in enumerate(arr)]]
        for j in range(1, K):
            st.append([min(st[-1][i], st[-1][i + (1<<(j-1))]) for i in range(n+1 - (1<<j))])
            
        def query(L, R):
            j = logs[R - L + 1];
            return min(st[j][L], st[j][R + 1 - (1 << j)])
            
        def find(val, l, r):
            if l > r: return 0
            q, ind = query(l, r)
            return q - val + find(q, l, ind-1) + find(q, ind + 1, r) 
            
        return find(0, 0, n-1)