Minimum Cost to Move Between Indices | Leetcode 3919

class Solution {
public:
    vector<int> minCost(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        
        // Step-1: Calculate Prefix_Sum
        vector<int> prefix_sum(n+1);
        prefix_sum[1] = 1;
        int curr_cost;
        for(int i=1;i<n-1;++i){
            if(abs(nums[i]-nums[i+1])<abs(nums[i]-nums[i-1]))
                curr_cost = 1;
            else
                curr_cost = abs(nums[i]-nums[i+1]);
            prefix_sum[i+1] = prefix_sum[i] + curr_cost;
        }
            
        // Step-2: Calculate reverse Prefix_Sum
        vector<int> rev_prefix_sum(n+1);
        rev_prefix_sum[n-1] = 1;
        for(int i=n-2;i>0;--i){
            if(abs(nums[i]-nums[i-1])<=abs(nums[i]-nums[i+1]))
                curr_cost = 1;
            else
                curr_cost = abs(nums[i]-nums[i-1]);
            rev_prefix_sum[i] += rev_prefix_sum[i+1] + curr_cost;
        }
        //Step-3: Compute each query
        vector<int> tot_cost;
        for(auto& query: queries){
            int cost = 0;
            if(query[0]<query[1])
                cost = prefix_sum[query[1]]-prefix_sum[query[0]];
            else
                cost = rev_prefix_sum[query[1]+1]-rev_prefix_sum[query[0]+1];
            tot_cost.push_back(cost);
        }
        return tot_cost;
    }
};
/*
//JAVA
class Solution {
    public int[] minCost(int[] nums, int[][] queries) {
        int n = nums.length;
        
        // Step-1: Calculate Prefix_Sum
        int[] prefix_sum = new int[n + 1];
        prefix_sum[1] = 1;
        int curr_cost;
        for (int i = 1; i < n - 1; ++i) {
            if (Math.abs(nums[i] - nums[i + 1]) < Math.abs(nums[i] - nums[i - 1])) {
                curr_cost = 1;
            } else {
                curr_cost = Math.abs(nums[i] - nums[i + 1]);
            }
            prefix_sum[i + 1] = prefix_sum[i] + curr_cost;
        }
            
        // Step-2: Calculate reverse Prefix_Sum
        int[] rev_prefix_sum = new int[n + 1];
        rev_prefix_sum[n - 1] = 1;
        for (int i = n - 2; i > 0; --i) {
            if (Math.abs(nums[i] - nums[i - 1]) <= Math.abs(nums[i] - nums[i + 1])) {
                curr_cost = 1;
            } else {
                curr_cost = Math.abs(nums[i] - nums[i - 1]);
            }
            // Literal translation of your += 
            rev_prefix_sum[i] += rev_prefix_sum[i + 1] + curr_cost;
        }
        
        // Step-3: Compute each query
        int[] tot_cost = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int cost = 0;
            int start = queries[i][0];
            int end = queries[i][1];
            
            if (start < end) {
                cost = prefix_sum[end] - prefix_sum[start];
            } else {
                cost = rev_prefix_sum[end + 1] - rev_prefix_sum[start + 1];
            }
            tot_cost[i] = cost;
        }
        
        return tot_cost;
    }
}

#Python
from typing import List

class Solution:
    def minCost(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        
        # Step-1: Calculate Prefix_Sum
        prefix_sum = [0] * (n + 1)
        prefix_sum[1] = 1
        
        for i in range(1, n - 1):
            if abs(nums[i] - nums[i + 1]) < abs(nums[i] - nums[i - 1]):
                curr_cost = 1
            else:
                curr_cost = abs(nums[i] - nums[i + 1])
            prefix_sum[i + 1] = prefix_sum[i] + curr_cost
            
        # Step-2: Calculate reverse Prefix_Sum
        rev_prefix_sum = [0] * (n + 1)
        rev_prefix_sum[n - 1] = 1
        
        # Iterating backwards from n-2 down to 1
        for i in range(n - 2, 0, -1):
            if abs(nums[i] - nums[i - 1]) <= abs(nums[i] - nums[i + 1]):
                curr_cost = 1
            else:
                curr_cost = abs(nums[i] - nums[i - 1])
            # Literal translation of your +=
            rev_prefix_sum[i] += rev_prefix_sum[i + 1] + curr_cost
            
        # Step-3: Compute each query
        tot_cost = []
        for query in queries:
            start, end = query[0], query[1]
            if start < end:
                cost = prefix_sum[end] - prefix_sum[start]
            else:
                cost = rev_prefix_sum[end + 1] - rev_prefix_sum[start + 1]
            tot_cost.append(cost)
            
        return tot_cost
*/