Total Cost to Hire K Workers
Problem
Given an array costs representing the cost of hiring each worker, an integer k representing the number of workers to hire, and an integer candidates representing the number of candidates to consider from each end of the array, return the minimum total cost to hire exactly k workers by always choosing the lowest cost worker from the candidate pools at the front and back.
- 1 ≤ costs.length ≤ 10⁵
- 1 ≤ costs[i] ≤ 10⁵
- 1 ≤ k, candidates ≤ costs.length
- candidates ≤ costs.length / 2
Example
costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 411Initially, the candidate pools are the first 4 workers [17,12,10,2] and the last 4 workers [2,11,20,8]. The algorithm pushes these candidates into a min-heap with their costs and indices. The lowest cost worker is 2 at index 3 (front pool), so hire them and add 2 to total. Then, the front pool pointer moves forward to index 4, and the worker at index 4 (cost 7) is pushed into the heap. Next, the lowest cost is 2 at index 5 (back pool), hire and add 2 to total. The back pool pointer moves backward to index 7, and the worker at index 7 (cost 20) is pushed into the heap. Finally, the lowest cost is 7 at index 4, hire and add 7 to total. The total cost is 2 + 2 + 7 = 11.
Approach
Straightforward Solution
A naive approach would repeatedly scan the front and back candidate pools to find the minimum cost worker, resulting in O(k * candidates) time complexity, which is too slow for large inputs.
Core Observation
At each hiring session, only workers from the front and back candidate pools are eligible. Maintaining a min-heap of these visible candidates allows efficient selection while pointers track the next unseen workers on each side.
Path to Optimal
PreviewThe key insight is to use a min-heap to maintain the current candidate pools from both ends. Initially, push the first candidates and last candidates workers into the heap…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a min-heap to store tuples of (cost, index) for the current candidate pools. Initialize pointers front_end and back_start to track the boundaries of the candidate pools…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(k log candidates)
Each of the k hiring steps involves a heap pop and potentially a heap push, each O(log candidates), because the heap only stores workers from the current candidate pools.
Space
O(candidates)
The heap stores up to 2 * candidates elements initially and can grow up to O(n) in the worst case as pointers move inward, but never more than n elements total.
Pattern Spotlight
Heap / Priority Queue (Dynamic Candidate Pool Management)
When repeatedly selecting the minimum element from dynamically changing subsets at both ends of a sequence, maintain a min-heap of candidates from each side and update it incrementally as pointers move inward to achieve efficient selection.
Solution
| 1 | import heapq |
| 2 | |
| 3 | class Solution: |
| 4 | def totalCost(self, costs, k, candidates): |
| 5 | |
| 6 | n = len(costs) |
| 7 | heap = [] |
| 8 | |
| 9 | front_end = candidates - 1 |
| 10 | back_start = max(candidates, n - candidates) |
| 11 | |
| 12 | for i in range(candidates): |
| 13 | heapq.heappush(heap, (costs[i], i)) |
| 14 | |
| 15 | for i in range(back_start, n): |
| 16 | heapq.heappush(heap, (costs[i], i)) |
| 17 | |
| 18 | total = 0 |
| 19 | |
| 20 | for _ in range(k): |
| 21 | |
| 22 | cost, i = heapq.heappop(heap) |
| 23 | total += cost |
| 24 | |
| 25 | if i <= front_end: |
| 26 | front_end += 1 |
| 27 | if front_end < back_start: |
| 28 | heapq.heappush(heap, (costs[front_end], front_end)) |
| 29 | |
| 30 | else: |
| 31 | back_start -= 1 |
| 32 | if back_start > front_end: |
| 33 | heapq.heappush(heap, (costs[back_start], back_start)) |
| 34 | |
| 35 | return total |
Step-by-Step Solution
Initialize Candidate Pools and Min-Heap with Front and Back Workers
| 6 | n = len(costs) |
| 7 | heap = [] |
| 9 | front_end = candidates - 1 |
| 10 | back_start = max(candidates, n - candidates) |
| 12 | for i in range(candidates): |
| 13 | heapq.heappush(heap, (costs[i], i)) |
| 15 | for i in range(back_start, n): |
| 16 | heapq.heappush(heap, (costs[i], i)) |
Objective
To set up pointers delimiting the candidate pools and populate the min-heap with initial candidates from both ends.
Key Insight
By defining front_end and back_start pointers, the algorithm tracks the boundaries of the candidate pools. Pushing the first candidates workers and the last candidates workers into the min-heap ensures that the heap always contains the current eligible candidates from both ends. This setup enables efficient minimum cost extraction without scanning the entire array.
Interview Quick-Check
Core Logic
The min-heap stores tuples of (cost, index) from both candidate pools, enabling O(log n) extraction of the lowest cost worker.
State & Boundaries
front_end and back_start pointers prevent overlapping candidate pools and track which workers have been pushed into the heap.
Common Pitfalls & Bugs
Incorrectly initializing back_start can cause overlapping candidate pools or missing candidates; using max(candidates, n - candidates) ensures correct separation.
Iteratively Hire Lowest Cost Worker and Update Candidate Pools
To repeatedly select the lowest cost worker from the heap, add their cost to the total, and update the candidate pools by pushing the next eligible worker from the same side.
Return the Accumulated Total Cost After Hiring K Workers
To output the final minimum total cost after completing all k hiring steps.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
cost, i = heapq.heappop(heap)Pop the worker with the lowest cost from the heap.
Extracting the minimum cost worker ensures the hiring decision is optimal at each step.
heapq.heappush(heap, (costs[i], i))Push the current front candidate worker's cost and index into the heap.
Storing both cost and index allows the algorithm to track which side the worker belongs to for future updates.
heapq.heappush(heap, (costs[i], i))Push the current back candidate worker's cost and index into the heap.
Including the index enables the algorithm to distinguish back pool workers and update pointers accordingly.
Full line-by-line criticality + rationale for all 21 lines available on Pro.
Test Your Understanding
Why does the algorithm maintain two pointers and dynamically update the heap instead of pushing all workers at once?
See the answer with Pro.
Related Problems
Heap / Priority Queue pattern
Don't just read it. Drill it.
Reconstruct Total Cost to Hire K Workers from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Total Cost to Hire K Workers drill