Sum of Mutated Array Closest to Target

LeetCode problem #1300

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given an integer array arr and an integer target. You may choose an integer value v and mutate the array as follows:

  • Replace every element x in arr with min(x, v).

Let S(v) be the sum of the mutated array. Your goal is to find the integer v such that S(v) is closest to target.

  • If there are multiple v values that produce sums equally close to target, return the smallest such v.

Input / Output Format

  • Input: arr: List[int], target: int
  • Output: int (the chosen value v)

Constraints

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^5
  • 1 <= target <= 10^5

Examples

Example 1

Input: arr = [4, 9, 3], target = 10
Try values:

  • v = 3 → mutated [3,3,3] sum = 9 (diff 1)
  • v = 4 → mutated [4,4,3] sum = 11 (diff 1)

Both are equally close, return the smaller v.

Output: 3

Example 2

Input: arr = [2, 3, 5], target = 10
If v >= 5, array unchanged, sum = 10 exactly.

Output: 5

Example 3

Input: arr = [60864, 25176, 27249, 21296, 20204], target = 56803
The best v is the one that caps large values so the sum is near 56803. (This is a typical case where binary search is useful.)

Output: 11361

Edge-focused Example 4 (very small target)

Input: arr = [5, 6, 7], target = 1
Even with v = 0 (not allowed in constraints, but v can be 0 in the original problem; LeetCode allows v in [0, max(arr)]), sum would be 0; with v = 1, sum = 3. Closest is v = 0 if allowed; under typical LeetCode interpretation, v can be 0.

Output (LeetCode): 0

Note: LeetCode’s original problem allows v in [0, max(arr)]. Most solutions search that range.

Approach 1: Brute Force

Algorithm Explanation

The mutated sum S(v) is monotonic non-decreasing with respect to v:

  • Increasing v can only increase (or keep) each min(arr[i], v).

A brute force approach:

  1. Iterate v from 0 to max(arr).
  2. Compute S(v) by summing min(x, v) for all x in arr.
  3. Track the v that minimizes abs(S(v) - target), breaking ties by choosing smaller v.

This is straightforward but can be too slow when max(arr) is large (up to 1e5).

Python Implementation

from typing import List

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        mx = max(arr)
        best_v = 0
        best_diff = float('inf')

        for v in range(mx + 1):
            s = 0
            for x in arr:
                s += x if x < v else v

            diff = abs(s - target)
            if diff < best_diff or (diff == best_diff and v < best_v):
                best_diff = diff
                best_v = v

        return best_v

Complexity Analysis

  • Let n = len(arr), M = max(arr)
  • Time: O(n * M)
  • Space: O(1)

Approach 2: Optimized Solution (Binary Search + Prefix Sums)

Better Algorithm Explanation

We want the v where S(v) is closest to target. Since S(v) is monotonic, we can binary search on v.

To compute S(v) fast:

  1. Sort arr.
  2. Build prefix sums prefix[i] = sum(arr[0..i-1]).
  3. For a given v, find the first index idx where arr[idx] > v (upper bound).
    • Elements before idx remain unchanged: sum = prefix[idx]
    • Elements from idx onward become v: contribution = (n - idx) * v
    • So S(v) = prefix[idx] + (n - idx) * v

Binary search finds the smallest v such that S(v) >= target. The best answer is either that v or v-1 (because closest could be just below the crossing point). Compare both and apply tie-breaking.

Python Implementation

from bisect import bisect_right
from typing import List

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

        prefix = [0] * (n + 1)
        for i, x in enumerate(arr, 1):
            prefix[i] = prefix[i - 1] + x

        def mutated_sum(v: int) -> int:
            idx = bisect_right(arr, v)  # first index with arr[idx] > v
            return prefix[idx] + (n - idx) * v

        lo, hi = 0, arr[-1]
        while lo < hi:
            mid = (lo + hi) // 2
            if mutated_sum(mid) < target:
                lo = mid + 1
            else:
                hi = mid

        # lo is the smallest v with S(v) >= target
        cand1 = lo
        cand2 = lo - 1

        def score(v: int):
            return abs(mutated_sum(v) - target)

        if cand2 >= 0 and score(cand2) <= score(cand1):
            return cand2
        return cand1

Java Implementation

import java.util.*;

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

        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];

        java.util.function.IntToLongFunction sum = (int v) -> {
            int idx = upperBound(arr, v); // first > v
            return prefix[idx] + (long)(n - idx) * v;
        };

        int lo = 0, hi = arr[n - 1];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (sum.applyAsLong(mid) < target) lo = mid + 1;
            else hi = mid;
        }

        int cand1 = lo, cand2 = lo - 1;
        long diff1 = Math.abs(sum.applyAsLong(cand1) - target);
        long diff2 = cand2 >= 0 ? Math.abs(sum.applyAsLong(cand2) - target) : Long.MAX_VALUE;

        if (diff2 <= diff1) return cand2;
        return cand1;
    }

    private int upperBound(int[] a, int v) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] <= v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

Go Implementation

package main

import (
	"sort"
)

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

	prefix := make([]int64, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + int64(arr[i])
	}

	mutatedSum := func(v int) int64 {
		// upper bound: first index with arr[idx] > v
		idx := sort.SearchInts(arr, v+1)
		return prefix[idx] + int64(n-idx)*int64(v)
	}

	lo, hi := 0, arr[n-1]
	for lo < hi {
		mid := (lo + hi) / 2
		if mutatedSum(mid) < int64(target) {
			lo = mid + 1
		} else {
			hi = mid
		}
	}

	cand1, cand2 := lo, lo-1
	diff1 := abs64(mutatedSum(cand1) - int64(target))
	diff2 := int64(1<<62)
	if cand2 >= 0 {
		diff2 = abs64(mutatedSum(cand2) - int64(target))
	}
	if diff2 <= diff1 {
		return cand2
	}
	return cand1
}

func abs64(x int64) int64 {
	if x < 0 {
		return -x
	}
	return x
}

JavaScript Implementation

function findBestValue(arr, target) {
  arr.sort((a, b) => a - b);
  const n = arr.length;

  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];

  function upperBound(v) {
    let lo = 0, hi = n;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid] <= v) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  function mutatedSum(v) {
    const idx = upperBound(v);
    return prefix[idx] + (n - idx) * v;
  }

  let lo = 0, hi = arr[n - 1];
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (mutatedSum(mid) < target) lo = mid + 1;
    else hi = mid;
  }

  const cand1 = lo, cand2 = lo - 1;
  const diff1 = Math.abs(mutatedSum(cand1) - target);
  const diff2 = cand2 >= 0 ? Math.abs(mutatedSum(cand2) - target) : Number.POSITIVE_INFINITY;

  return diff2 <= diff1 ? cand2 : cand1;
}

C# Implementation

using System;

public class Solution {
    public int FindBestValue(int[] arr, int target) {
        Array.Sort(arr);
        int n = arr.Length;

        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];

        long MutatedSum(int v) {
            int idx = UpperBound(arr, v);
            return prefix[idx] + (long)(n - idx) * v;
        }

        int lo = 0, hi = arr[n - 1];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (MutatedSum(mid) < target) lo = mid + 1;
            else hi = mid;
        }

        int cand1 = lo, cand2 = lo - 1;
        long diff1 = Math.Abs(MutatedSum(cand1) - target);
        long diff2 = cand2 >= 0 ? Math.Abs(MutatedSum(cand2) - target) : long.MaxValue;

        return diff2 <= diff1 ? cand2 : cand1;
    }

    private int UpperBound(int[] a, int v) {
        int lo = 0, hi = a.Length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] <= v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

Complexity Analysis

  • Sorting: O(n log n)
  • Each mutated_sum(v) query: O(log n) via upper bound
  • Binary search over v in [0, max(arr)]: O(log max(arr))
  • Total: O(n log n + log(max(arr)) * log n)
  • Space: O(n) for prefix sums

Key Insights

  • Monotonic function: S(v) is monotone non-decreasing, enabling binary search on the answer.
  • Only two candidates matter: Once you find the smallest v with S(v) >= target, the best answer is either v or v-1 (closest on either side of the crossing).
  • Prefix sums after sorting let you compute S(v) quickly by splitting the array into:
    • values <= v (unchanged)
    • values > v (capped to v)

Edge Cases

  • target is very small (possibly smaller than len(arr)), pushing the best v toward 0.
  • target is very large (>= sum(arr)), best v should be max(arr) (no mutation needed).
  • Many duplicates in arr.
  • arr length = 1.
  • Tie case where S(v) and S(v+1) are equally close → return smaller v.
  • Large values in arr with small target (heavy capping).

Test Cases

import unittest

class TestSolution(unittest.TestCase):
    def test_examples(self):
        s = Solution()
        self.assertEqual(s.findBestValue([4, 9, 3], 10), 3)
        self.assertEqual(s.findBestValue([2, 3, 5], 10), 5)
        self.assertEqual(s.findBestValue([60864, 25176, 27249, 21296, 20204], 56803), 11361)

    def test_edge_small_target(self):
        s = Solution()
        self.assertEqual(s.findBestValue([5, 6, 7], 1), 0)

    def test_target_ge_sum(self):
        s = Solution()
        self.assertEqual(s.findBestValue([1, 2, 3], 100), 3)

    def test_single_element(self):
        s = Solution()
        self.assertEqual(s.findBestValue([10], 3), 3)
        self.assertEqual(s.findBestValue([10], 10), 10)
        self.assertEqual(s.findBestValue([10], 11), 10)

    def test_tie_break(self):
        s = Solution()
        # v=3 => sum=9 diff=1, v=4 => sum=11 diff=1 => choose 3
        self.assertEqual(s.findBestValue([4, 9, 3], 10), 3)

if __name__ == "__main__":
    unittest.main()

Common Mistakes

  • Not handling tie-breaking correctly (must return the smaller v).
  • Binary searching the wrong condition (need the smallest v with S(v) >= target).
  • Forgetting to check v-1 after binary search.
  • Overflow in languages like Java/C#/Go if using int for sums (use long / int64).
  • Using linear sum computation inside binary search without prefix sums → can time out (O(n log maxA) is okay, but still slower; prefix sums make it robust).

Interview Tips

  • Start by stating that the mutated sum S(v) is monotonic, which suggests binary search on v.
  • Explain how to compute S(v) efficiently:
    • sort + prefix sums + upper bound split.
  • Mention the key correctness detail:
    • binary search gives a “crossing point”; closest answer is among {v, v-1} with tie → smaller v.
  • Be ready to discuss complexity tradeoffs:
    • brute force is simple but too slow for large max(arr).
    • optimized solution is O(n log n + log(maxA) log n) and safe for constraints.