Problem Overview
LeetCode 2462 Total Cost to Hire K Workers gives you an integer array costs where costs[i] is the hiring cost for the i-th worker. You also receive two integers k and candidates. You must hire exactly k workers through k separate hiring sessions.
In each hiring session you review the first candidates workers and the last candidates workers from the remaining pool. You hire the worker with the lowest cost among all reviewed candidates. If there is a tie in cost, you hire the worker with the smaller index. After hiring, that worker is removed from the pool and the session ends.
The goal is to return the total cost of hiring exactly k workers. The naive approach of re-scanning all candidates for every session would be O(k * candidates) per round, which is too slow for the given constraints. A heap-based approach brings each session down to O(log candidates).
- Given: costs array of length n, integers k (workers to hire) and candidates (window size)
- Each round: look at first candidates and last candidates workers from remaining pool
- Hire the cheapest worker; break ties by choosing the smaller index
- Remove the hired worker from the pool and repeat for k total rounds
- Return the sum of hiring costs across all k rounds
Two-Heap Approach
The efficient solution maintains two separate min-heaps: frontHeap holds the first candidates workers (by index order), and backHeap holds the last candidates workers. Each heap stores (cost, index) pairs so ties on cost are broken by index automatically.
Each hiring round, we compare the minimum of frontHeap with the minimum of backHeap. We hire from whichever side is cheaper, or from the front in case of a tie. After hiring, if there are workers remaining in the middle (between the front and back windows), we refill the depleted heap with the next available worker from that side.
This two-heap structure lets each round run in O(log candidates) time — we never re-scan the entire remaining pool. The total time complexity is O(candidates * log(candidates)) for initialization and O(k * log(candidates)) for all hiring rounds.
Key Insight
The two heaps simulate a hiring manager looking at both ends of the worker queue simultaneously. You always pick the cheapest visible candidate from either end. As workers are hired from one end, you slide the window inward and add the newly exposed worker to that heap.
Initialization
Before the hiring rounds begin, initialize the two heaps by pushing the first candidates workers into frontHeap and the last candidates workers into backHeap. Use left and right pointers to track the boundary between the front window and the back window — left starts after the front window and right starts before the back window.
When candidates * 2 >= n (the two windows overlap or cover all workers), some workers could appear in both heaps. To avoid duplicates, check that left <= right before adding any worker. If the arrays fully overlap, simply use one combined heap or only frontHeap.
After initialization, both heaps are ready with up to candidates elements each. The left pointer marks the next worker available to refill frontHeap, and the right pointer marks the next worker available to refill backHeap. The hiring loop proceeds from there.
- 1Set left = candidates, right = n - 1 - candidates (pointers to the middle region)
- 2Push (costs[i], i) for i in [0, candidates-1] into frontHeap — heapify
- 3Push (costs[j], j) for j in [n-candidates, n-1] into backHeap — heapify
- 4If candidates * 2 >= n, only push distinct workers (check for overlap using left <= right)
- 5Verify left and right pointers are correct: left starts just past the front window, right just before the back window
Hiring Loop
Run k hiring rounds. Each round, peek at the tops of frontHeap and backHeap. If frontHeap is empty or backHeap's top is strictly cheaper, hire from backHeap; otherwise hire from frontHeap (front wins on ties). Add the hired cost to the running total.
After hiring from frontHeap, check if left <= right. If so, push (costs[left], left) into frontHeap and increment left. After hiring from backHeap, check if left <= right. If so, push (costs[right], right) into backHeap and decrement right. This maintains the invariant that each heap always has the best available candidates from its side.
After k iterations, return the accumulated total cost. The loop naturally handles the case where the middle region runs out — once left > right, no refilling happens and the heaps shrink round by round until all k hires are complete.
Overlap Handling
When the front and back windows overlap (all remaining workers are visible from both ends), the two heaps together contain all remaining workers. The left > right condition stops any refilling, and hiring continues from whichever heap has the smaller top until all k rounds finish. The two-heap structure handles this gracefully without special-casing.
Walk-Through Example
Consider costs = [17, 12, 10, 2, 7, 2, 11, 20, 8], k = 3, candidates = 4. n = 9. frontHeap is initialized with indices 0-3: costs [17, 12, 10, 2] → min-heap top is (2, 3). backHeap is initialized with indices 5-8: costs [2, 11, 20, 8] → min-heap top is (2, 5). left = 4, right = 4.
Round 1: frontHeap top = (2, 3), backHeap top = (2, 5). Tie on cost — hire from front. Hire index 3, cost 2. Refill front: push (costs[4], 4) = (7, 4). left becomes 5. Total = 2.
Round 2: frontHeap top = (7, 4), backHeap top = (2, 5). Back is cheaper. Hire index 5, cost 2. Refill back: left (5) > right (4) — no refill. Total = 4. Round 3: frontHeap top = (7, 4), backHeap top = (8, 8). Front is cheaper. Hire index 4, cost 7. Total = 11. Answer: 11.
- 1Init: frontHeap = [(2,3),(10,2),(12,1),(17,0)], backHeap = [(2,5),(8,8),(11,6),(20,7)], left=4, right=4
- 2Round 1: tie at cost=2, hire from front (index 3). Refill front with (7,4). left=5. Total=2
- 3Round 2: back cheaper (2 vs 7), hire from back (index 5, cost=2). left>right, no refill. Total=4
- 4Round 3: front cheaper (7 vs 8), hire from front (index 4, cost=7). Total=11
- 5All 3 rounds complete — return total cost = 11
Code Walkthrough — Python and Java
In Python, use heapq for both heaps. Initialize frontHeap with heapq.heapify on the first candidates (cost, index) pairs. Build backHeap similarly from the tail. The main loop uses heapq.heappop and heapq.heappush. Time complexity: O(candidates * log(candidates)) init + O(k * log(candidates)) loop. Space: O(candidates) for both heaps combined.
In Java, use PriorityQueue<int[]> with a comparator that first compares cost (a[0] vs b[0]) then index (a[1] vs b[1]) for tie-breaking. Populate both queues in initialization loops, then run the k-round hiring loop with offer and poll operations. The logic mirrors the Python version exactly.
Edge cases to handle: when candidates >= n/2, the windows fully overlap — initialize only frontHeap with all workers and skip backHeap entirely. When n <= 2 * candidates, use left > right check from the start to avoid double-inserting any worker. Both languages handle this with the same pointer boundary checks.
Overlap Pitfall
Do not add the same index to both heaps when candidates * 2 >= n. Use left <= right as the guard before pushing any worker into either heap during initialization. Without this check, workers near the middle of the array get hired twice — or push causes index-out-of-bounds errors. Always verify left <= right before touching the middle region.