Total Cost to Hire K Workers — Two-Pointer Heap from Both Ends

Problem Statement#

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker. You are also given two integers k and candidates. In each hiring round, you choose and hire exactly one worker from the candidates pool. The candidates pool consists of the first candidates workers and the last candidates workers (if they aren't already hired). Among the candidates, hire the one with the lowest cost. If there's a tie, hire the one with the smaller index.

Perform exactly k hiring rounds and return the total cost to hire exactly k workers.

Constraints:

• 1 <= costs.length <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= k, candidates <= costs.length

Examples:

Example 1:
Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: In round 1, the first 4 candidates are [17,12,10,2], last 4 are [7,2,11,20].
  Cheapest among {2,7,2,11,...} → cost=2 at index 3 (first 4). Total=2.
  Round 2: first [17,12,10], last 4 [7,2,11,20]. Cheapest → 2 at index 5. Total=4.
  Round 3: first [17,12,10], last [7,11,20,8]. Cheapest → 7. Total=11.
 
Example 2:
Input: costs = [1,2,4,1], k = 3, candidates = 3
Output: 4

Why This Problem Matters#

Total Cost to Hire K Workers is a medium problem that appeared in LeetCode's 2023 weekly contests and quickly became a common interview question at Amazon and Google. It tests the two-sided heap pattern: maintaining two separate heaps for the left and right ends of an array, expanding inward as elements are consumed.

Amazon uses this problem because it directly models a staffing scenario their own recruiters face: given a pool of candidates ordered by some criterion, the most cost-effective candidates tend to be at the extremes (either very senior or very junior), and you want to hire greedily while accounting for candidates joining the pool as others are hired.

The problem is tricky because the "candidates pool" dynamically expands inward as workers are hired. Candidates who were not initially in the pool become available. Managing this expansion with two pointers (l and r) while maintaining two heaps is the core challenge.

This pattern — two heaps expanding toward each other — appears in "Trapping Rain Water," "Container with Most Water," and is a building block for more complex sliding window problems. Mastering this problem also prepares you for the harder "Minimum Deviation in Array" and "Maximum Performance of a Team."

The Core Insight#

Maintain two min-heaps:

• Left heap: the first candidates workers (indices 0 to candidates-1).
• Right heap: the last candidates workers (indices n-candidates to n-1).

Two pointers l and r mark the next "unexplored" positions from the left and right:

• l starts at candidates (next position to add to left heap).
• r starts at n - candidates - 1 (next position to add to right heap).

Each round:

1. Compare the top of both heaps. Pick the cheaper one (tie: smaller index wins → prefer left).
2. If the chosen worker came from the left heap and l <= r, add costs[l] to the left heap and advance l.
3. If from the right heap and l <= r, add costs[r] to the right heap and decrease r.

Continue for k rounds.

Key insight: As workers are hired from one end, new workers "slide in" from that end to replenish the candidates pool — exactly modeling the problem's description.

Visual Dry Run#

costs = [17,12,10,2,7,2,11,20,8], k=3, candidates=4, n=9
 
Initial:
  Left heap (first 4): [17,12,10,2] → min-heap: [2,12,17,10] → top=2 (idx=3)
  Right heap (last 4): [7,2,11,20] → min-heap: [2,7,11,20] → top=2 (idx=5 by cost order)
  Wait: right heap stores (cost, index): [(2,5),(7,4),(11,6),(20,7)]
  l=4, r=4 (n - candidates - 1 = 9 - 4 - 1 = 4)
 
Round 1: left_top=(2,3), right_top=(2,5). Tie → prefer left (smaller index).
  Hire index 3, cost=2. Total=2.
  l=4 ≤ r=4: push (costs[4],4) = (7,4) to left heap.
  l=5, r=4 (l>r now, no more expansion).
  Left heap: [(7,4),(12,1),(17,0),(10,2)]
 
Round 2: left_top=(7,4), right_top=(2,5). Right is cheaper.
  Hire index 5, cost=2. Total=4.
  l=5 > r=4: no expansion.
 
Round 3: left_top=(7,4), right_top=(7,4)?
  Hmm: right heap after removing (2,5): [(7,4),(11,6),(20,7),(8,8)]
  Wait: r=4 and l=5 > r, so right doesn't expand either.
  left_top=(7,4), right_top=(7,4). Same cost AND same index!? 
  Actually right heap: [(7,4),(11,6),(20,7),(8,8)] → but idx 4 is already in left heap too?
  
  Careful: the problem says pool = first p + last p, no overlap if 2p ≤ n.
  With n=9, p=4: first 4 = [0,1,2,3], last 4 = [5,6,7,8]. l=4, r=4 means workers meet.
  When l=r=4, only one of them gets idx 4 — the code handles this with l <= r check.
  
  After round 2: left heap top = (7,4). Right heap top = (7,?).
  Right heap initial had indices 5,6,7,8. After hiring (2,5): [(7,4)? No, only if expanded].
  r=4 never added anything to right (l>r immediately). Right heap: [(7,?),(11,6),(20,7),(8,8)].
  Correct right heap initial: costs[5..8] = [2,11,20,8] with indices [5,6,7,8].
  After hiring (2,5): right heap = [(7,?),(11,6),(8,8),(20,7)].
  
  Round 3: left_top=(7,4), right_top=(7,4)? No — right has no idx=4.
  right_top=(8,8). left_top=(7,4). Hire from left: cost=7. Total=11. ✓

Solution (Optimal)#

import heapq
 
def totalCost(costs, k, candidates):
    n = len(costs)
    
    # Build initial heaps with (cost, index) pairs
    left_heap = [(costs[i], i) for i in range(min(candidates, n))]
    right_heap = [(costs[i], i) for i in range(max(n - candidates, candidates), n)]
    heapq.heapify(left_heap)
    heapq.heapify(right_heap)
    
    # Pointers for next unexplored positions
    l = candidates
    r = n - candidates - 1
    
    total = 0
    
    for _ in range(k):
        left_top = left_heap[0] if left_heap else (float('inf'), float('inf'))
        right_top = right_heap[0] if right_heap else (float('inf'), float('inf'))
        
        # Pick cheaper (tie: smaller index → prefer left since left indices < right indices)
        if left_top[0] <= right_top[0]:
            cost, idx = heapq.heappop(left_heap)
            total += cost
            # Expand left side if pointers haven't crossed
            if l <= r:
                heapq.heappush(left_heap, (costs[l], l))
                l += 1
        else:
            cost, idx = heapq.heappop(right_heap)
            total += cost
            # Expand right side if pointers haven't crossed
            if l <= r:
                heapq.heappush(right_heap, (costs[r], r))
                r -= 1
    
    return total

function totalCost(costs, k, candidates) {
    const n = costs.length;
    
    // Sorted arrays as min-heaps: [cost, index]
    const leftHeap = [];
    const rightHeap = [];
    
    const heapPush = (heap, item) => {
        let lo = 0, hi = heap.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (heap[mid][0] < item[0] || (heap[mid][0] === item[0] && heap[mid][1] < item[1]))
                lo = mid + 1;
            else hi = mid;
        }
        heap.splice(lo, 0, item);
    };
    
    // Initialize heaps
    for (let i = 0; i < candidates && i < n; i++) {
        heapPush(leftHeap, [costs[i], i]);
    }
    for (let i = Math.max(n - candidates, candidates); i < n; i++) {
        heapPush(rightHeap, [costs[i], i]);
    }
    
    let l = candidates;
    let r = n - candidates - 1;
    let total = 0;
    
    for (let round = 0; round < k; round++) {
        const lv = leftHeap[0] || [Infinity, Infinity];
        const rv = rightHeap[0] || [Infinity, Infinity];
        
        if (lv[0] <= rv[0]) {
            total += leftHeap.shift()[0];
            if (l <= r) { heapPush(leftHeap, [costs[l], l]); l++; }
        } else {
            total += rightHeap.shift()[0];
            if (l <= r) { heapPush(rightHeap, [costs[r], r]); r--; }
        }
    }
    
    return total;
}

Complexity Analysis:

• Time: O((k + candidates) × log(candidates)) — each hiring round does O(log candidates) heap operations; initialization is O(candidates × log(candidates))
• Space: O(candidates) — each heap holds at most candidates elements

Common Mistakes#

• Overlap between left and right heaps. When 2 * candidates >= n, the two initial candidate windows overlap. Handle this by initializing right heap from max(n - candidates, candidates) to avoid adding the same indices to both heaps.
• Not checking l <= r before expanding. When the two pointers cross, no new workers should be added. Expanding past this causes duplicate hires or index-out-of-bounds.
• Tie-breaking incorrectly. When left and right tops have equal cost, hire the one with the smaller index. Since left indices are always smaller than right indices at any point, prefer left whenever costs are equal.
• Forgetting to track indices. The heap must store (cost, index) pairs, not just costs. Without indices, tie-breaking is impossible.
• Initializing r incorrectly. r = n - candidates - 1 is the index of the rightmost position not yet in the right heap (one position to the left of the initial right heap range).

Follow-up Questions#

1. What if candidates >= n/2? The left and right pools overlap. Does the algorithm handle this correctly?
2. What if k > n? This is impossible — you can't hire more workers than exist. The constraints guarantee k ≤ n.
3. Prove the greedy is optimal: why does always hiring the cheapest available worker minimize total cost?
4. What if there's a budget constraint instead of a fixed k? Maximize the number of workers hired within budget B.
5. What if the order of hiring matters (e.g., later hires cost more due to inflation)? How does the algorithm change?
6. Can you solve this with a single heap instead of two? What would you need to track?

Key Takeaways#

• Maintain two min-heaps, one for the left candidates and one for the right candidates; expand inward as workers are hired by advancing pointer l and retreating pointer r.
• When 2 * candidates >= n, the windows overlap — initialize the right heap from max(n - candidates, candidates) to avoid adding the same index to both heaps.
• Stop expanding when l > r; once the pointers cross, no new workers are available to refill the pools.
• Tie-breaking: when both heap tops have equal cost, prefer the left heap because left indices are always smaller than right indices at any point.
• Time is O((k + candidates) log(candidates)); space is O(candidates) since each heap holds at most candidates elements.
• Amazon designed this problem around real staffing scenarios — always explain the physical meaning: left and right candidate pools expand inward as each hire is made.
• The two-pointer expanding-inward pattern also appears in Trapping Rain Water and Container with Most Water — worth noting as a related structural insight.