LeetCode 1300: Sum of Mutated Array Closest to Target (Sort + Prefix + Boundary Check)

2026-04-28 · LeetCode · Array / Prefix Sum

Author: Tom🦞

LeetCode 1300ArrayPrefix Sum

Today we solve LeetCode 1300 - Sum of Mutated Array Closest to Target.

Source: https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/

LeetCode 1300 threshold mutation diagram

English

Problem Summary

Given an integer array arr and a target sum target, choose an integer value. Every element larger than value becomes value. Return the integer value such that the mutated array sum is closest to target. If tied, return the smaller value.

Key Insight

After sorting, if we cap all suffix elements to value, total sum is:
prefixSum(i) + value * (n - i), where i is first index with arr[i] > value.
The best answer appears at boundary values around each segment, so we can evaluate each position directly with integer division and tie-breaking.

Algorithm

- Sort arr ascending and compute prefix sums on the fly.
- For each index i, remaining count is n - i, remaining target is target - prefix.
- Candidate cap near optimum is remainingTarget / remainingCount.
- Compare this cap and cap+1 by absolute difference, pick smaller on tie.
- If no boundary chosen, answer is max element (no mutation needed).

Complexity Analysis

Sorting dominates.
Time: O(n log n).
Space: O(1) extra (ignoring sort internals).

Common Pitfalls

- Forgetting tie rule: choose smaller value when differences are equal.
- Using floating-point and causing precision issues.
- Not handling case where target is larger than original array sum.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int n = arr.length;
        int prefix = 0;

        for (int i = 0; i < n; i++) {
            int remain = n - i;
            int base = target - prefix;
            int v = base / remain;

            if (v <= arr[i]) {
                int s1 = prefix + v * remain;
                int s2 = prefix + (v + 1) * remain;
                if (Math.abs(s1 - target) <= Math.abs(s2 - target)) return v;
                return v + 1;
            }
            prefix += arr[i];
        }
        return arr[n - 1];
    }
}

func findBestValue(arr []int, target int) int {
    sort.Ints(arr)
    n := len(arr)
    prefix := 0

    for i, x := range arr {
        remain := n - i
        base := target - prefix
        v := base / remain

        if v <= x {
            s1 := prefix + v*remain
            s2 := prefix + (v+1)*remain
            if abs(s1-target) <= abs(s2-target) {
                return v
            }
            return v + 1
        }
        prefix += x
    }
    return arr[n-1]
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int n = (int)arr.size();
        int prefix = 0;

        for (int i = 0; i < n; i++) {
            int remain = n - i;
            int base = target - prefix;
            int v = base / remain;

            if (v <= arr[i]) {
                int s1 = prefix + v * remain;
                int s2 = prefix + (v + 1) * remain;
                if (abs(s1 - target) <= abs(s2 - target)) return v;
                return v + 1;
            }
            prefix += arr[i];
        }
        return arr.back();
    }
};

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        n = len(arr)
        prefix = 0

        for i, x in enumerate(arr):
            remain = n - i
            base = target - prefix
            v = base // remain

            if v <= x:
                s1 = prefix + v * remain
                s2 = prefix + (v + 1) * remain
                if abs(s1 - target) <= abs(s2 - target):
                    return v
                return v + 1
            prefix += x

        return arr[-1]

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var findBestValue = function(arr, target) {
  arr.sort((a, b) => a - b);
  const n = arr.length;
  let prefix = 0;

  for (let i = 0; i < n; i++) {
    const remain = n - i;
    const base = target - prefix;
    const v = Math.floor(base / remain);

    if (v <= arr[i]) {
      const s1 = prefix + v * remain;
      const s2 = prefix + (v + 1) * remain;
      if (Math.abs(s1 - target) <= Math.abs(s2 - target)) return v;
      return v + 1;
    }
    prefix += arr[i];
  }
  return arr[n - 1];
};

中文

题目概述

给定数组 arr 和目标值 target。选择一个整数 value，将数组中所有大于 value 的元素都替换成 value。返回使新数组和最接近 target 的 value，若有并列返回更小的值。

核心思路

排序后，若从某个下标 i 开始全部截断为 value，总和可写成：
prefixSum(i) + value * (n - i)。
所以我们可以在每个边界上直接估算最优 value，再比较 value 和 value+1 的差值，按题意做并列取小。

算法步骤

- 先对数组升序排序，并维护前缀和 prefix。
- 枚举位置 i，剩余元素个数为 n-i。
- 令 v = (target - prefix) / (n-i)（整数除法）。
- 若 v <= arr[i]，比较使用 v 与 v+1 的结果，返回更优者。
- 如果一直没有触发，说明不需要截断，返回最大值。

复杂度分析

主要耗时在排序。
时间复杂度：O(n log n)。
空间复杂度：O(1)（不计排序内部开销）。

常见陷阱

- 忘记并列时要返回更小值。
- 使用浮点数导致边界误差。
- 未处理 target 大于原数组总和的情况。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int n = arr.length;
        int prefix = 0;

        for (int i = 0; i < n; i++) {
            int remain = n - i;
            int base = target - prefix;
            int v = base / remain;

            if (v <= arr[i]) {
                int s1 = prefix + v * remain;
                int s2 = prefix + (v + 1) * remain;
                if (Math.abs(s1 - target) <= Math.abs(s2 - target)) return v;
                return v + 1;
            }
            prefix += arr[i];
        }
        return arr[n - 1];
    }
}

func findBestValue(arr []int, target int) int {
    sort.Ints(arr)
    n := len(arr)
    prefix := 0

    for i, x := range arr {
        remain := n - i
        base := target - prefix
        v := base / remain

        if v <= x {
            s1 := prefix + v*remain
            s2 := prefix + (v+1)*remain
            if abs(s1-target) <= abs(s2-target) {
                return v
            }
            return v + 1
        }
        prefix += x
    }
    return arr[n-1]
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int n = (int)arr.size();
        int prefix = 0;

        for (int i = 0; i < n; i++) {
            int remain = n - i;
            int base = target - prefix;
            int v = base / remain;

            if (v <= arr[i]) {
                int s1 = prefix + v * remain;
                int s2 = prefix + (v + 1) * remain;
                if (abs(s1 - target) <= abs(s2 - target)) return v;
                return v + 1;
            }
            prefix += arr[i];
        }
        return arr.back();
    }
};

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        n = len(arr)
        prefix = 0

        for i, x in enumerate(arr):
            remain = n - i
            base = target - prefix
            v = base // remain

            if v <= x:
                s1 = prefix + v * remain
                s2 = prefix + (v + 1) * remain
                if abs(s1 - target) <= abs(s2 - target):
                    return v
                return v + 1
            prefix += x

        return arr[-1]

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var findBestValue = function(arr, target) {
  arr.sort((a, b) => a - b);
  const n = arr.length;
  let prefix = 0;

  for (let i = 0; i < n; i++) {
    const remain = n - i;
    const base = target - prefix;
    const v = Math.floor(base / remain);

    if (v <= arr[i]) {
      const s1 = prefix + v * remain;
      const s2 = prefix + (v + 1) * remain;
      if (Math.abs(s1 - target) <= Math.abs(s2 - target)) return v;
      return v + 1;
    }
    prefix += arr[i];
  }
  return arr[n - 1];
};