Abstract / Summary

Make all numbers in the array the same by adding or subtracting one from any element each step find the least steps needed

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 39% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Prefix Sum
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that, given an array of integers and a list of target values, computes for each target the minimum total number of increment or decrement operations required to make every element of the array equal to that target. The algorithm relies on sorting the input array and constructing a prefix-sum structure to enable fast aggregation of values on either side of any target. By leveraging binary search, each query is answered in logarithmic time relative to the size of the input array.

Preprocessing: sorting and prefix sum

The first phase prepares the data for efficient query resolution. The array is sorted in ascending order, which establishes a deterministic ordering that binary search can exploit. Immediately after sorting, a running total is accumulated to produce a prefix-sum list where each entry represents the sum of all elements up to that index.

size = len(nums)
nums.sort()

prefix = []
total  = 0
for n in nums:
    total += n
    prefix.append(total)

The variable total holds the sum of the entire array and is reused later, avoiding recomputation.

Query loop and trivial edge cases

The method iterates over each query value q. Two simple boundary conditions are handled first: when the target is less than or equal to the smallest element, and when it is greater than or equal to the largest element. In these scenarios the answer reduces to a straightforward arithmetic expression involving the total sum and the array size.

for q in queries:
    if q <= nums[0]:
        yield total - size * q
        continue
    if q >= nums[-1]:
        yield size * q - total
        continue

These early exits prevent unnecessary binary search and arithmetic when the answer is deterministic.

Locating the split point with binary search

For targets that lie strictly between the minimum and maximum values, the algorithm determines the index pos where q would be inserted to maintain sorted order. This index separates the array into two halves: elements smaller than q on the left and elements greater than or equal to q on the right.

pos = bisect_left(nums, q)

The use of bisect_left guarantees that all elements at indices < pos are strictly less than q, while those at >= pos are not less than q.

Computing the cost for the left side

The sum of elements on the left side is retrieved from the prefix-sum list. The desired total for those positions, if they were all equal to q, is q * pos. The difference between this desired total and the actual sum yields the number of increment operations needed.

lower = prefix[pos - 1]
same  = q * pos
left  = same - lower

When pos is zero, the preceding block is never reached because the earlier boundary check would have captured the case.

Computing the cost for the right side

The sum of elements on the right side is derived by subtracting the left-side sum from the overall total. The target total for the right side, if all elements matched q, is q * (size - pos). The difference between the actual right-side sum and this target total yields the number of decrement operations required.

higher = total - lower
same   = q * (size - pos)
right  = higher - same

The variable higher represents the aggregate of all elements from pos onward, while same reflects the hypothetical uniform value.

Combining left and right contributions

The final answer for a given query is the sum of the left-side increments and the right-side decrements. This value is emitted via a generator, allowing the caller to iterate lazily over results.

yield left + right

Edge cases explicitly addressed

The code gracefully handles several boundary conditions:

• When the query equals the smallest element, the first conditional branch treats it as the “smaller than any number” case, returning zero cost because the array already satisfies the target.
• When the query equals the largest element, the second conditional branch similarly returns zero cost.
• When the array contains duplicate values, the binary search still correctly identifies the split point, and the prefix-sum lookup remains valid because the prefix list accumulates duplicates naturally.
• When the array consists of a single element, both boundary checks collapse to the same condition, and the subsequent calculations correctly compute a zero cost for any query equal to that element.

Performance optimizations observed

The algorithm avoids recomputing the total sum for each query by storing it once during preprocessing. The prefix-sum array enables constant-time retrieval of cumulative sums for any sub-range, eliminating the need for linear scans inside the query loop. By employing binary search (bisect_left), the position of each query is found in logarithmic time, ensuring that the overall query processing scales efficiently with the number of queries. The use of a generator (yield) allows results to be produced on demand without allocating an intermediate list, reducing memory overhead when the caller consumes the output incrementally.

Imagine a long row of building blocks with different heights sitting on the floor. The goal is to make every single block the exact same height as a target number that someone picks. This code is like a clever helper that finds the fastest way to change all those blocks to match the target.

First, the helper lines up all the blocks from shortest to tallest. This makes it much easier to see how much work needs to be done. Then, it adds up all the heights as it goes along to keep a running total. This is kind of like counting how many total inches of wood there are in the whole pile.

When a target number is given, the helper looks at it. If the target is smaller than the shortest block, it knows exactly how much it needs to trim off every single block to bring them down. If the target is taller than the biggest block, it knows exactly how much it needs to grow every single block to reach the goal.

When the target sits somewhere in the middle of the heights, the helper splits the pile into two groups. The blocks that are shorter than the target need to grow, and the blocks that are taller need to shrink. By using the running total from earlier, the helper quickly calculates how much moving parts it takes to turn all those tiny piles into a row of equal towers. It does this over and over again for every new target requested.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java	C++		Python	TS
	WalkCCC	Java	C++		Python
	leetcode.ca	Java	C++	Go	Python	TS
	Progiez	Java	C++		Python
github	charles-wangkai	Java
	fsq		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality