Total Cost to Hire K Workers — Problem & Solution
Total Cost to Hire K Workers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Total Cost to Hire K Workers is a medium coding problem on arrays, two pointers and simulation, asked in Amazon, Google, MathWorks and CRED interviews.
- Difficulty: Medium
- Topics: Arrays, Two Pointers, Simulation, Heap
- Asked at: Amazon, Google, MathWorks, CRED
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
costs[i] is what it costs to hire the i-th worker. You run k hiring sessions, and in each one you consider the first candidates and the last candidates workers still unhired.
You hire the cheapest among those considered, breaking ties by the smaller index. If fewer than 2 * candidates workers remain, all of them are considered. Return the total cost.
Example 1
Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: Hire the 2 at index 3, then the 2 at index 5, then the 7.
Example 2
Input: costs = [1,2,4,1], k = 3, candidates = 3
Output: 4
Example 3
Input: costs = [5,5,5], k = 3, candidates = 1
Output: 15
Constraints
1 <= costs.length <= 10^51 <= costs[i] <= 10^51 <= k, candidates <= costs.length
Hints for Total Cost to Hire K Workers
Hint 1
Keep two pools: one growing in from the left, one from the right.
Hint 2
Each session hires the smaller of the two pools' minima, with the left pool winning ties.
Hint 3
After a hire, refill that pool from its side — but only while the two sides have not met.
How to solve Total Cost to Hire K Workers
Two min-heaps, one for each end, with two pointers marking the untouched middle. Each session compares the two heap tops, hires the smaller, and refills from the side that lost a member.
Approach
- Fill the left heap with the first
candidatesworkers and the right heap with the lastcandidates, stopping if the pointers cross. - Each session, compare the heaps' minima; the left wins ties, since its workers have smaller indices.
- Pop the winner, add its cost, and refill that heap from its pointer if any workers remain in the middle.
- Repeat
ktimes.
Why it works
Letting the left pool win ties is exactly the smaller-index rule — everything in the left pool sits before everything in the right one, so no explicit index comparison is needed. The pointers are what stop a worker being considered twice when the two windows would otherwise overlap.
Complexity
- Time —
O((k + candidates) log candidates) - Space —
O(candidates)
Pitfalls
- Overlapping windows can double-count a worker; the pointers must stop the initial fill.
- Ties go to the left pool, not to whichever heap is checked first.
- A pool may empty while the other still has workers; treat it as infinitely expensive.
Reference solution
Python
from typing import List
import heapq
def totalCost(costs: List[int], k: int, candidates: int) -> int:
n = len(costs)
lo, hi = 0, n - 1
left, right = [], []
while len(left) < candidates and lo <= hi:
heapq.heappush(left, costs[lo])
lo += 1
while len(right) < candidates and lo <= hi:
heapq.heappush(right, costs[hi])
hi -= 1
total = 0
for _ in range(k):
lv = left[0] if left else float('inf')
rv = right[0] if right else float('inf')
if lv <= rv:
total += heapq.heappop(left)
if lo <= hi:
heapq.heappush(left, costs[lo])
lo += 1
else:
total += heapq.heappop(right)
if lo <= hi:
heapq.heappush(right, costs[hi])
hi -= 1
return totalJava
public static int totalCost(int[] costs, int k, int candidates) {
int n = costs.length;
int lo = 0, hi = n - 1;
PriorityQueue<Integer> left = new PriorityQueue<>();
PriorityQueue<Integer> right = new PriorityQueue<>();
while (left.size() < candidates && lo <= hi) left.add(costs[lo++]);
while (right.size() < candidates && lo <= hi) right.add(costs[hi--]);
long total = 0;
for (int t = 0; t < k; t++) {
int lv = left.isEmpty() ? Integer.MAX_VALUE : left.peek();
int rv = right.isEmpty() ? Integer.MAX_VALUE : right.peek();
if (lv <= rv) {
total += left.poll();
if (lo <= hi) left.add(costs[lo++]);
} else {
total += right.poll();
if (lo <= hi) right.add(costs[hi--]);
}
}
return (int) total;
}C++
int totalCost(vector<int>& costs, int k, int candidates) {
int n = (int) costs.size();
int lo = 0, hi = n - 1;
priority_queue<int, vector<int>, greater<int>> left, right;
while ((int) left.size() < candidates && lo <= hi) left.push(costs[lo++]);
while ((int) right.size() < candidates && lo <= hi) right.push(costs[hi--]);
long long total = 0;
for (int t = 0; t < k; t++) {
int lv = left.empty() ? INT_MAX : left.top();
int rv = right.empty() ? INT_MAX : right.top();
if (lv <= rv) {
total += lv;
left.pop();
if (lo <= hi) left.push(costs[lo++]);
} else {
total += rv;
right.pop();
if (lo <= hi) right.push(costs[hi--]);
}
}
return (int) total;
}JavaScript
var totalCost = function(costs, k, candidates) {
var n = costs.length;
var lo = 0, hi = n - 1;
var left = [], right = [];
while (left.length < candidates && lo <= hi) left.push(costs[lo++]);
while (right.length < candidates && lo <= hi) right.push(costs[hi--]);
var total = 0;
for (var t = 0; t < k; t++) {
var li = -1, rj = -1, i;
for (i = 0; i < left.length; i++) if (li < 0 || left[i] < left[li]) li = i;
for (i = 0; i < right.length; i++) if (rj < 0 || right[i] < right[rj]) rj = i;
var lv = li >= 0 ? left[li] : Infinity;
var rv = rj >= 0 ? right[rj] : Infinity;
if (lv <= rv) {
total += lv;
left.splice(li, 1);
if (lo <= hi) left.push(costs[lo++]);
} else {
total += rv;
right.splice(rj, 1);
if (lo <= hi) right.push(costs[hi--]);
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique