Total Cost to Hire K Workers

Medium
969.

Total Cost to Hire K Workers

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} costs
 * @param {number} k
 * @param {number} candidates
 * @return {number}
 */
var totalCost = function(costs, k, candidates) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Total Cost to Hire K Workers

  1. Hint 1

    Keep two pools: one growing in from the left, one from the right.

  2. Hint 2

    Each session hires the smaller of the two pools' minima, with the left pool winning ties.

  3. 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

  1. Fill the left heap with the first candidates workers and the right heap with the last candidates, stopping if the pointers cross.
  2. Each session, compare the heaps' minima; the left wins ties, since its workers have smaller indices.
  3. Pop the winner, add its cost, and refill that heap from its pointer if any workers remain in the middle.
  4. 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

Java

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