Total Cost to Hire K Workers — Medium Problem & Solution

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…

Difficulty: Medium
Topics: Arrays, Two Pointers, Simulation, Heap
Asked at: Amazon, Google, 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^5
1 <= costs[i] <= 10^5
1 <= k, candidates <= costs.length

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 candidates workers and the right heap with the last candidates, 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 k times.

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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue