problemmediumalgorithms

Minimum adjustment cost

MediumUpdated: Sep 27, 2025
Practice on:
LintCode

Problem

Given an integer array A and an integer target, adjust each integer so that the absolute difference between every pair of adjacent integers is not greater than target. Let B be the adjusted array. Minimize the total adjustment cost defined as the sum of |A[i] - B[i]| over all indices i.

Return the minimum achievable adjustment cost.

Examples

Example 1

Input: A = [1, 4, 2, 3], target = 1
Output: 2
Explanation: One optimal adjusted array is B = [2, 3, 2, 3]; total cost = |1-2|+|4-3|+|2-2|+|3-3| = 2.

Constraints

  • You may assume each original number A[i] is a positive integer and not greater than 100.
Similar Problems

Solution

Method 1 - Naive Recursion

Intuition

  • At index i, if we decide to set B[i] = v, then for the next index i+1 we may only choose values v' such that |v' - v| <= target.
  • A naive recursive solution tries all valid adjusted values for each position and keeps the minimum accumulated cost. This explores the full search tree without caching, leading to exponential time.

Approach

Let solve(i, prev) be the minimum additional cost to adjust positions i..n-1 given that the previous adjusted value is prev (for i > 0). For i = 0, there is no previous value constraint, so we simply try all values v in [1..100] as starting points.

  1. If i == n, return 0 (no cost beyond end).
  2. Determine candidate range for v:
    • If i == 0: v from 1..100.
    • Else: v from max(1, prev - target) to min(100, prev + target).
  3. For each v in the range, cost = abs(A[i] - v) + solve(i+1, v); take the minimum.
  4. Return that minimum.

Edge cases:

  • Empty array → cost 0.
  • Single element → min_{v in 1..100} |A[0] - v| (achieved at v = A[0]).

Code

This version is for conceptual clarity only; it will time out for larger inputs due to exponential growth.

C++
#include <vector>
#include <cmath>
#include <limits>
using namespace std;

class Solution {
    const int MAXV = 100;
    int n, target;
    const vector<int>* arr;
    int dfs(int i, int prev) {
        if (i == n) return 0;
        int lo = 1, hi = MAXV;
        if (i > 0) {
            lo = max(1, prev - target);
            hi = min(MAXV, prev + target);
        }
        int best = numeric_limits<int>::max();
        for (int v = lo; v <= hi; ++v) {
            int cost = abs((*arr)[i] - v) + dfs(i + 1, v);
            if (cost < best) best = cost;
        }
        return best;
    }
public:
    int minAdjustmentCost(const vector<int>& A, int tgt) {
        arr = &A; target = tgt; n = (int)A.size();
        if (n == 0) return 0;
        return dfs(0, 0);
    }
};
Go
package main

import "math"

type solverRec struct { A []int; n, target int }

func (s *solverRec) dfs(i, prev int) int {
    if i == s.n { return 0 }
    lo, hi := 1, 100
    if i > 0 {
        if prev - s.target > lo { lo = prev - s.target }
        if prev + s.target < hi { hi = prev + s.target }
    }
    best := math.MaxInt32
    for v := lo; v <= hi; v++ {
        cost := abs(s.A[i]-v) + s.dfs(i+1, v)
        if cost < best { best = cost }
    }
    return best
}

func minAdjustmentCostRecursive(A []int, target int) int {
    if len(A) == 0 { return 0 }
    s := &solverRec{A: A, n: len(A), target: target}
    return s.dfs(0, 0)
}

func abs(a int) int { if a<0 { return -a }; return a }
Java
import java.util.*;

class Solution {
    private int n, target;
    private List<Integer> A;
    private int dfs(int i, int prev) {
        if (i == n) return 0;
        int lo = 1, hi = 100;
        if (i > 0) {
            lo = Math.max(1, prev - target);
            hi = Math.min(100, prev + target);
        }
        int best = Integer.MAX_VALUE;
        for (int v = lo; v <= hi; v++) {
            int cost = Math.abs(A.get(i) - v) + dfs(i + 1, v);
            best = Math.min(best, cost);
        }
        return best;
    }
    public int minAdjustmentCost(ArrayList<Integer> arr, int tgt) {
        A = arr; target = tgt; n = A.size();
        if (n == 0) return 0;
        return dfs(0, 0);
    }
}
Python
from typing import List

class Solution:
    def minAdjustmentCost(self, A: List[int], target: int) -> int:
        n = len(A)
        if n == 0:
            return 0
        MAXV = 100
        from math import inf
        def dfs(i: int, prev: int) -> int:
            if i == n:
                return 0
            if i == 0:
                lo, hi = 1, MAXV
            else:
                lo = max(1, prev - target)
                hi = min(MAXV, prev + target)
            best = inf
            for v in range(lo, hi + 1):
                best = min(best, abs(A[i] - v) + dfs(i + 1, v))
            return best
        return dfs(0, 0)

Complexity

  • ⏰ Time complexity: O( (2*target+1)^n ) in the worst case (exponential) — every level branches over up to 2*target+1 values.
  • 🧺 Space complexity: O(n) recursion depth (call stack) ignoring output; no memo table.

Method 2 - Top-Down DP (Memoization)

Intuition

  • The pure recursion repeats subproblems: the minimum cost for suffix i given previous adjusted value prev appears many times.
  • Cache (i, prev) results to avoid recomputation. This reduces exponential growth to polynomial O(n * V * T) where V=100 and T bounds the neighbor range (2*target+1).

Approach

  1. Use a 2D memo table memo[i][prev] initialized to -1 meaning unknown (treat prev in 0..100; we use prev=0 only for the first position as a sentinel meaning "no previous").
  2. Recurrence identical to Method 1, but before computing we check cache.
  3. Return cached value once computed.

Code

C++
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

class Solution {
    const int MAXV = 100;
    int n, target; const vector<int>* A;
    vector<vector<int>> memo; // memo[i][prev]
    int dfs(int i, int prev) {
        if (i == n) return 0;
        if (memo[i][prev] != -1) return memo[i][prev];
        int lo = 1, hi = MAXV;
        if (i > 0) { lo = max(1, prev - target); hi = min(MAXV, prev + target); }
        int best = numeric_limits<int>::max();
        for (int v = lo; v <= hi; ++v) {
            int cost = abs((*A)[i] - v) + dfs(i + 1, v);
            if (cost < best) best = cost;
        }
        return memo[i][prev] = best;
    }
public:
    int minAdjustmentCost(const vector<int>& arr, int tgt) {
        A = &arr; target = tgt; n = (int)arr.size();
        if (n == 0) return 0;
        memo.assign(n, vector<int>(MAXV + 1, -1));
        return dfs(0, 0);
    }
};
Go
package main

import "math"

type solverMemo struct { A []int; n, target int; memo [][]int }

func (s *solverMemo) dfs(i, prev int) int {
    if i == s.n { return 0 }
    if s.memo[i][prev] != -1 { return s.memo[i][prev] }
    lo, hi := 1, 100
    if i > 0 { if prev - s.target > lo { lo = prev - s.target }; if prev + s.target < hi { hi = prev + s.target } }
    best := math.MaxInt32
    for v := lo; v <= hi; v++ {
        cost := abs(s.A[i]-v) + s.dfs(i+1, v)
        if cost < best { best = cost }
    }
    s.memo[i][prev] = best
    return best
}

func minAdjustmentCostMemo(A []int, target int) int {
    if len(A) == 0 { return 0 }
    memo := make([][]int, len(A))
    for i := range memo { memo[i] = make([]int, 101); for v := 0; v <= 100; v++ { memo[i][v] = -1 } }
    s := &solverMemo{A: A, n: len(A), target: target, memo: memo}
    return s.dfs(0, 0)
}

func abs(a int) int { if a<0 { return -a }; return a }
Java
import java.util.*;

class Solution {
    private int n, target; private List<Integer> A;
    private int[][] memo; // memo[i][prev]
    private int dfs(int i, int prev) {
        if (i == n) return 0;
        if (memo[i][prev] != -1) return memo[i][prev];
        int lo = 1, hi = 100;
        if (i > 0) { lo = Math.max(1, prev - target); hi = Math.min(100, prev + target); }
        int best = Integer.MAX_VALUE;
        for (int v = lo; v <= hi; v++) {
            int cost = Math.abs(A.get(i) - v) + dfs(i + 1, v);
            best = Math.min(best, cost);
        }
        return memo[i][prev] = best;
    }
    public int minAdjustmentCost(ArrayList<Integer> arr, int tgt) {
        A = arr; target = tgt; n = A.size();
        if (n == 0) return 0;
        memo = new int[n][101];
        for (int i = 0; i < n; i++) Arrays.fill(memo[i], -1);
        return dfs(0, 0);
    }
}
Python
from typing import List
from functools import lru_cache

class Solution:
    def minAdjustmentCost(self, A: List[int], target: int) -> int:
        n = len(A)
        if n == 0:
            return 0
        MAXV = 100
        @lru_cache(None)
        def dfs(i: int, prev: int) -> int:
            if i == n:
                return 0
            if i == 0:
                lo, hi = 1, MAXV
            else:
                lo = max(1, prev - target)
                hi = min(MAXV, prev + target)
            best = 10**12
            for v in range(lo, hi + 1):
                best = min(best, abs(A[i] - v) + dfs(i + 1, v))
            return best
        return dfs(0, 0)

Complexity

  • ⏰ Time complexity: O(n * V * T) — at most n * (V+1) states and each iterates up to 2*target+1 values (bounded by V). With V=100, effectively O(n * target).
  • 🧺 Space complexity: O(n * V) for memo table (or recursion cache) plus O(n) stack depth.

Method 3 - Bottom-up 2D DP

Intuition

  • For each position i and a possible adjusted value v (1..100), consider the minimum cost to make A[0..i] valid with B[i] = v.
  • Let dp[i][v] be this minimum cost. To compute it we look at all possible previous adjusted values pv such that |v - pv| <= target and take dp[i-1][pv] + |A[i] - v|.

Approach

  1. Let n = len(A), and let values range v be 1..100 (per problem constraint).
  2. Initialize dp[0][v] = |A[0] - v| for all v.
  3. For each i from 1 to n-1, and for each v in 1..100:
    • Set dp[i][v] = min(dp[i-1][pv] + |A[i] - v|) for all pv in 1..100 with |v - pv| <= target.
  4. Answer is min(dp[n-1][v]) over v = 1..100.

Edge cases:

  • If A is empty, return 0.
  • The per-value range is bounded (1..100), so the inner loops are constant-bounded.

Code

C++
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

class Solution {
public:
    int minAdjustmentCost(const vector<int>& A, int target) {
        int n = A.size();
        if (n == 0) return 0;
        const int MAXV = 100;
        const int INF = numeric_limits<int>::max() / 4;
        vector<vector<int>> dp(n, vector<int>(MAXV + 1, INF));
        for (int v = 1; v <= MAXV; ++v) dp[0][v] = abs(A[0] - v);
        for (int i = 1; i < n; ++i) {
            for (int v = 1; v <= MAXV; ++v) {
                for (int pv = max(1, v - target); pv <= min(MAXV, v + target); ++pv) {
                    dp[i][v] = min(dp[i][v], dp[i-1][pv] + abs(A[i] - v));
                }
            }
        }
        int ans = INF;
        for (int v = 1; v <= MAXV; ++v) ans = min(ans, dp[n-1][v]);
        return ans;
    }
};
Go
package main

import "math"

func minAdjustmentCost(A []int, target int) int {
    n := len(A)
    if n == 0 { return 0 }
    const MAXV = 100
    INF := int(math.MaxInt32 / 4)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, MAXV+1)
        for v := 1; v <= MAXV; v++ { dp[i][v] = INF }
    }
    for v := 1; v <= MAXV; v++ { dp[0][v] = abs(A[0]-v) }
    for i := 1; i < n; i++ {
        for v := 1; v <= MAXV; v++ {
            for pv := max(1, v-target); pv <= min(MAXV, v+target); pv++ {
                if dp[i-1][pv] + abs(A[i]-v) < dp[i][v] {
                    dp[i][v] = dp[i-1][pv] + abs(A[i]-v)
                }
            }
        }
    }
    ans := INF
    for v := 1; v <= MAXV; v++ { if dp[n-1][v] < ans { ans = dp[n-1][v] } }
    return ans
}

func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
Java
import java.util.*;

class Solution {
    public int minAdjustmentCost(ArrayList<Integer> A, int target) {
        if (A == null || A.size() == 0) return 0;
        final int MAXV = 100;
        final int INF = Integer.MAX_VALUE / 4;
        int n = A.size();
        int[][] dp = new int[n][MAXV + 1];
        for (int i = 0; i < n; i++) Arrays.fill(dp[i], INF);
        for (int v = 1; v <= MAXV; v++) dp[0][v] = Math.abs(A.get(0) - v);
        for (int i = 1; i < n; i++) {
            for (int v = 1; v <= MAXV; v++) {
                for (int pv = Math.max(1, v - target); pv <= Math.min(MAXV, v + target); pv++) {
                    dp[i][v] = Math.min(dp[i][v], dp[i-1][pv] + Math.abs(A.get(i) - v));
                }
            }
        }
        int ans = INF;
        for (int v = 1; v <= MAXV; v++) ans = Math.min(ans, dp[n-1][v]);
        return ans;
    }
}
Python
from typing import List

class Solution:
    def minAdjustmentCost(self, A: List[int], target: int) -> int:
        n = len(A)
        if n == 0:
            return 0
        MAXV = 100
        INF = 10**9
        dp = [[INF] * (MAXV + 1) for _ in range(n)]
        for v in range(1, MAXV + 1):
            dp[0][v] = abs(A[0] - v)
        for i in range(1, n):
            for v in range(1, MAXV + 1):
                for pv in range(max(1, v - target), min(MAXV, v + target) + 1):
                    dp[i][v] = min(dp[i][v], dp[i-1][pv] + abs(A[i] - v))
        return min(dp[n-1][1:])

Complexity

  • ⏰ Time complexity: O(n * V * T) where n = len(A), V = 100 is the bounded value range, and T = target (more precisely the inner loop iterates up to 2*target+1 values). So worst-case O(n * V * T) which is effectively O(n * target) with constant V=100.
  • 🧺 Space complexity: O(n * V) for the 2D dp table. (Can be optimized to O(V) — see Method 2.)

Method 4 - Dynamic Programming (Space-optimized, rolling array)

Intuition

  • Only the previous row dp[i-1][*] is needed to compute dp[i][*], so we can keep two 1D arrays and roll them to reduce memory.

Approach

  1. Use two arrays prev[v] and cur[v] of size V+1 (V = 100).
  2. Initialize prev[v] = |A[0] - v|.
  3. For each i from 1 to n-1, compute cur[v] = min(prev[pv] + |A[i] - v|) for pv in v-target..v+target.
  4. Swap prev and cur at each step.

Code

C++
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

class Solution {
public:
    int minAdjustmentCost(const vector<int>& A, int target) {
        int n = A.size();
        if (n == 0) return 0;
        const int MAXV = 100;
        const int INF = numeric_limits<int>::max() / 4;
        vector<int> prev(MAXV + 1, INF), cur(MAXV + 1, INF);
        for (int v = 1; v <= MAXV; ++v) prev[v] = abs(A[0] - v);
        for (int i = 1; i < n; ++i) {
            fill(cur.begin(), cur.end(), INF);
            for (int v = 1; v <= MAXV; ++v) {
                for (int pv = max(1, v - target); pv <= min(MAXV, v + target); ++pv) {
                    cur[v] = min(cur[v], prev[pv] + abs(A[i] - v));
                }
            }
            prev.swap(cur);
        }
        int ans = INF;
        for (int v = 1; v <= MAXV; ++v) ans = min(ans, prev[v]);
        return ans;
    }
};
Go
package main

import "math"

func minAdjustmentCost(A []int, target int) int {
    n := len(A)
    if n == 0 { return 0 }
    const MAXV = 100
    INF := int(math.MaxInt32 / 4)
    prev := make([]int, MAXV+1)
    cur := make([]int, MAXV+1)
    for v := 1; v <= MAXV; v++ { prev[v] = abs(A[0]-v) }
    for i := 1; i < n; i++ {
        for v := 1; v <= MAXV; v++ { cur[v] = INF }
        for v := 1; v <= MAXV; v++ {
            for pv := max(1, v-target); pv <= min(MAXV, v+target); pv++ {
                if prev[pv] + abs(A[i]-v) < cur[v] {
                    cur[v] = prev[pv] + abs(A[i]-v)
                }
            }
        }
        prev, cur = cur, prev
    }
    ans := INF
    for v := 1; v <= MAXV; v++ { if prev[v] < ans { ans = prev[v] } }
    return ans
}

func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
Java
import java.util.*;

class Solution {
    public int minAdjustmentCost(ArrayList<Integer> A, int target) {
        if (A == null || A.size() == 0) return 0;
        final int MAXV = 100;
        final int INF = Integer.MAX_VALUE / 4;
        int n = A.size();
        int[] prev = new int[MAXV + 1];
        int[] cur = new int[MAXV + 1];
        Arrays.fill(prev, INF);
        for (int v = 1; v <= MAXV; v++) prev[v] = Math.abs(A.get(0) - v);
        for (int i = 1; i < n; i++) {
            Arrays.fill(cur, INF);
            for (int v = 1; v <= MAXV; v++) {
                for (int pv = Math.max(1, v - target); pv <= Math.min(MAXV, v + target); pv++) {
                    cur[v] = Math.min(cur[v], prev[pv] + Math.abs(A.get(i) - v));
                }
            }
            int[] tmp = prev; prev = cur; cur = tmp;
        }
        int ans = INF;
        for (int v = 1; v <= MAXV; v++) ans = Math.min(ans, prev[v]);
        return ans;
    }
}
Python
from typing import List

class Solution:
    def minAdjustmentCost(self, A: List[int], target: int) -> int:
        n = len(A)
        if n == 0:
            return 0
        MAXV = 100
        INF = 10**9
        prev = [INF] * (MAXV + 1)
        cur = [INF] * (MAXV + 1)
        for v in range(1, MAXV + 1):
            prev[v] = abs(A[0] - v)
        for i in range(1, n):
            for v in range(1, MAXV + 1):
                cur[v] = INF
            for v in range(1, MAXV + 1):
                for pv in range(max(1, v - target), min(MAXV, v + target) + 1):
                    cur[v] = min(cur[v], prev[pv] + abs(A[i] - v))
            prev, cur = cur, prev
        return min(prev[1:])

Complexity

  • ⏰ Time complexity: O(n * V * T) where n = len(A), V = 100 (bounded value range), and T ≈ target (inner scan over 2*target+1 values). With V constant this is effectively O(n * target).
  • 🧺 Space complexity: O(V) for the space-optimized version (Method 2) and O(n * V) for the full 2D DP (Method 1).

Continue Practicing

Coin Change with Fewest Number of Coins Given Infinite SupplyMedium

Comments