Hop Cost - Google Top Interview Questions

                        Solution in C++ :

const int NTREE = 1024;

void update(vector<int>& tree, int pos, int val) {
    pos += NTREE;
    tree[pos] = val;
    pos /= 2;
    while (pos) {
        tree[pos] = min(tree[2 * pos], tree[2 * pos + 1]);
        pos /= 2;
    }
}

int query(vector<int>& tree, int l, int r) {
    int result = INT_MAX;
    l += NTREE;
    r += NTREE;

    while (l <= r) {
        if (l % 2 == 1) result = min(result, tree[l++]);
        if (r % 2 == 0) result = min(result, tree[r--]);

        l /= 2;
        r /= 2;
    }

    return result;
}

int solve(vector<int>& nums0, vector<int>& nums1, int dist, int cost) {
    int N = nums0.size();
    vector<int> tree0, tree1;
    tree0.resize(2 * NTREE);
    tree1.resize(2 * NTREE);

    for (int i = 0; i < 2 * NTREE; i++) tree0[i] = tree1[i] = INT_MAX;

    update(tree0, 0, nums0[0]);
    update(tree1, 0, nums1[0]);

    for (int i = 1; i < N; i++) {
        int min0 = query(tree0, i - dist, i - 1);
        int min1 = query(tree1, i - dist, i - 1);

        int dp0 = min(min0, min1 + cost) + nums0[i];
        int dp1 = min(min1, min0 + cost) + nums1[i];

        update(tree0, i, dp0);
        update(tree1, i, dp1);
    }

    return min(query(tree0, N - 1, N - 1), query(tree1, N - 1, N - 1));
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums0, int[] nums1, int dist, int cost) {
        int n = nums0.length, a0[] = nums0.clone(), a1[] = nums1.clone();
        for (int i = 1; i < n; i++) {
            a0[i] += a0[i - 1];
            a1[i] += a1[i - 1];
            for (int j = i - 1; j >= 0 && j >= i - dist; j--) {
                a1[i] = Math.min(a1[i], Math.min(a1[j], a0[j] + cost) + nums1[i]);
                a0[i] = Math.min(a0[i], Math.min(a0[j], a1[j] + cost) + nums0[i]);
            }
        }
        return Math.min(a0[n - 1], a1[n - 1]);
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums0, nums1, dist, cost):
        n = len(nums0)
        if n == 0:
            return 0
        dp0, dp1 = [0] * n, [0] * n
        monoq0, monoq1 = deque(), deque()
        dp0[0] = nums0[0]
        dp1[0] = nums1[0]
        monoq0.append(nums0[0])
        monoq1.append(nums1[0])
        for i in range(1, n):
            # calculate best costs at current index
            dp0[i] = nums0[i] + min(monoq0[0], monoq1[0] + cost)
            dp1[i] = nums1[i] + min(monoq0[0] + cost, monoq1[0])

            # update monoqueue for dp0
            while len(monoq0) > 0 and monoq0[-1] > dp0[i]:
                monoq0.pop()
            monoq0.append(dp0[i])
            if i >= dist and monoq0[0] == dp0[i - dist]:
                monoq0.popleft()

            # update monoqueue for dp1
            while len(monoq1) > 0 and monoq1[-1] > dp1[i]:
                monoq1.pop()
            monoq1.append(dp1[i])
            if i >= dist and monoq1[0] == dp1[i - dist]:
                monoq1.popleft()

        return min(dp0[n - 1], dp1[n - 1])