Abstract / Summary

You must hire exactly k workers paying each at least their minimum wage while keeping all wages proportional to minimize total cost.

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 44% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Heap (Priority Queue)
• Simulation
• Two Pointers

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 implementation solves the problem of selecting k workers with the minimum total hiring cost from a list costs. It treats the first and last candidates elements as two independent pools that can be accessed via min-heaps, while the middle segment is processed sequentially. The algorithm proceeds in three logical phases: a quick-path for small inputs, a partitioning step that builds the two heaps, and an iterative hiring loop that draws from the cheaper side of the two pools. When the middle segment is exhausted, the remaining required hires are taken from the combined sorted contents of the two heaps.

Quick-path for small inputs

When the total number of workers does not exceed twice the candidate window, the whole list can be sorted once and the cheapest k costs summed directly.

if len(costs) <= candidates + candidates:
    s = sorted(costs)
    return sum(s[:k])

This branch avoids any heap construction and guarantees the optimal result for the degenerate case where the left and right windows would overlap.

Partitioning the input into three sections

For larger inputs the list is split into three parts: the left window, the middle segment, and the right window. The left and right windows are turned into min-heaps, enabling constant-time access to the smallest available cost in each pool.

left  = costs[:candidates]
mid   = costs[candidates:-candidates]
right = costs[-candidates:]
heapify(left)
heapify(right)

The middle segment mid remains a plain list because elements are drawn from its front or back in a deterministic order, which avoids the overhead of heap operations for that region.

Main hiring loop that consumes the middle segment

The core loop runs while fewer than k workers have been hired and there are still elements in mid. At each iteration the algorithm compares the smallest elements of the two heaps. If the left heap’s minimum is less than or equal to the right heap’s minimum, the left heap is updated by replacing its root with the next element taken from the front of mid. Otherwise the right heap is updated with the element taken from the back of mid. The replaced value, which is the cheapest available at that moment, is appended to the hired collection.

while len(hired) < k and mid:
    if left[0] <= right[0]:
        hired.append(heapreplace(left,  mid.pop(0)))
    else:
        hired.append(heapreplace(right, mid.pop(-1)))

The use of heapreplace performs a pop-and-push in a single operation, keeping the heap size constant and preserving the min-heap property efficiently. The mid.pop(0) and mid.pop(-1) calls remove elements from opposite ends, reflecting the fact that the left side of the original list supplies candidates from the front while the right side supplies from the back.

Final selection when the middle segment is exhausted

If the loop finishes because mid is empty but fewer than k workers have been hired, the remaining hires are taken from the union of the two heaps. At this point both heaps contain only the candidates that have never been selected, and they are merged, sorted, and the cheapest needed number are added to hired.

need = k - len(hired)
if need > 0:  # len(mid) == 0
    both = sorted(left + right)
    hired += both[:need]

Sorting the concatenated heaps is acceptable here because the total number of remaining elements is bounded by 2 * candidates, which is typically much smaller than the original list size.

Edge-case handling

The algorithm gracefully handles several boundary conditions:

• When the total number of workers is less than or equal to 2 * candidates, the early return path ensures that overlapping windows do not cause duplicate consideration of the same element.
• If k is smaller than the size of either heap, the main loop may terminate before any element from mid is used, and the final selection step will simply pick the smallest k values from the combined heaps.
• Equality between the smallest elements of the two heaps (left[0] == right[0]) is resolved by preferring the left heap, which preserves deterministic behavior without affecting optimality.
• When mid becomes empty, the condition need > 0 triggers the fallback to a sorted merge, guaranteeing that the exact number of required hires is always produced.
• The use of heapreplace ensures that even when the heap contains a single element, the operation correctly replaces it and returns the removed minimum, avoiding special-case code for singleton heaps.

Performance optimizations observed

The code leverages several techniques to keep the runtime low:

• Early sorting of the entire list is avoided for the common case; only the two boundary windows are heapified, which is an O(candidates) operation.
• The middle segment is processed with simple list pops from either end, which are O(1) for the back and amortized O(1) for the front due to Python’s list implementation when used as a deque-like structure.
• heapreplace combines a pop and a push into a single heap operation, reducing the constant factor compared to separate heappop and heappush calls.
• The final merge sorts at most 2 * candidates elements, keeping the cost bounded regardless of the original list length.
• By maintaining the heap sizes constant throughout the main loop, the algorithm avoids the growth of heap structures and the associated overhead of dynamic resizing.

Overall, the solution balances direct sorting for small inputs with heap-based incremental selection for larger inputs, ensuring that the most expensive operations are limited to small, well-bounded subsets of the data.

Imagine you have a long line of toys and you want to pick a few of them to go on an adventure. The code starts by looking at all the toys to see if there are only a few of them. If there are not many, it simply picks the cheapest toys from the whole group.

When there are many toys, the code splits them into three parts. One part is at the very front of the line, one part is at the very back, and the rest are stuck in the middle. It keeps a close eye on the front group and the back group to see which ones are the least expensive.

To pick the toys, it looks at the front group and the back group and grabs the smallest one to join the adventure. Once a toy is picked, a new toy from the middle of the line steps up to fill the empty spot. This happens over and over again until the adventure group is full or the middle of the line is empty.

If the adventure group still needs more toys, the code puts all the remaining toys from the front and back together and picks the cheapest ones left until the group is complete. It is very much like a game of selecting the perfect team by constantly comparing the toys at the ends of the line.

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

not analyzed yet

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
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

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