Total Cost to Hire K Workers

Med

#2246Time: O(k * n). The outer loop runs `k` times. Inside, finding the candidates involves scanning up to `n` elements in the worst case (if using a boolean array) or `O(candidates)` if using a list but with an `O(n)` removal cost. Both variations lead to an overall complexity that is too slow.Space: O(n). A boolean array or a list is used to keep track of hired/available workers, which requires space proportional to the total number of workers.4 companies

Patterns

Two Pointers

Data structures

Array Heap (Priority Queue)

Companies

BNY Mellon Zomato MathWorks GSA Capital

Prompt

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the i^th worker.

You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:

You will run k sessions and hire exactly one worker in each session.
In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
- For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4^th worker because they have the lowest cost [3,2,7,7,1,2].
- In the second hiring session, we will choose 1^st worker because they have the same lowest cost as 4^th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.
If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
A worker can only be chosen once.

Return the total cost to hire exactly k workers.

Example 1:

Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [17,12,10,2,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
- In the second hiring round we choose the worker from [17,12,10,7,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
- In the third hiring round we choose the worker from [17,12,10,7,11,20,8]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers.
The total hiring cost is 11.

Example 2:

Input: costs = [1,2,4,1], k = 3, candidates = 3
Output: 4
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [1,2,4,1]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers.
- In the second hiring round we choose the worker from [2,4,1]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
- In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [2,4]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.
The total hiring cost is 4.

Constraints:

1 <= costs.length <= 10⁵
1 <= costs[i] <= 10⁵
1 <= k, candidates <= costs.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the hiring process as described in the problem statement. In each of the k hiring sessions, it scans the list of workers to identify the available candidates from the first and last candidates positions. It then finds the one with the minimum cost among this pool (breaking ties by index), adds their cost to the total, and conceptually removes them from the available pool for subsequent rounds.

Algorithm

Initialize totalCost = 0 and a boolean array hired of size n to all false.
Repeat k times to simulate each hiring session: a. Initialize minCost to a very large value and minIndex to -1. b. Identify the pool of candidates. This pool consists of the first candidates unhired workers and the last candidates unhired workers. c. To do this, first scan from the beginning of the costs array. For the first candidates workers found that are not yet hired, compare their cost with minCost. If a worker has a lower cost, or the same cost but a smaller index, update minCost and minIndex. d. Then, scan from the end of the costs array. For the first candidates workers found (from the end) that are not yet hired, perform the same comparison and update minCost and minIndex if a better candidate is found. e. After checking both pools, minCost and minIndex will hold the cost and index of the worker to be hired. f. Add minCost to totalCost. g. Mark the chosen worker as hired by setting hired[minIndex] = true.
After k sessions, return totalCost.

Walkthrough

To implement this simulation, we can use a boolean array, hired, of the same size as costs to keep track of which workers have already been hired. All entries are initially false.

We then loop k times. In each iteration, we need to find the best candidate for the current session. We initialize a minCost variable to infinity and a minIndex to -1. We then perform two scans:

A scan from the beginning of the array to find the first candidates unhired workers. For each of these candidates, we check if they are a better choice than our current minCost/minIndex (lower cost, or same cost with a smaller index).
A similar scan from the end of the array to find the last candidates unhired workers, again updating our best choice if a better candidate is found.

After these two scans, we will have identified the overall best candidate for the session. We add their cost to a running totalCost and mark them as hired in our hired array. This process repeats k times.

1class Solution {2    public long totalCost(int[] costs, int k, int candidates) {3        long totalCost = 0;4        int n = costs.length;5        // Using a list to easily remove hired workers. This is also inefficient.6        java.util.List<int[]> workerList = new java.util.ArrayList<>();7        for (int i = 0; i < n; i++) {8            workerList.add(new int[]{costs[i], i}); // {cost, original_index}9        }10 11        for (int i = 0; i < k; i++) {12            int minCost = Integer.MAX_VALUE;13            int minIndexInList = -1;14            int minOriginalIndex = -1;15 16            // Check first 'candidates' workers17            int limit = Math.min(candidates, workerList.size());18            for (int j = 0; j < limit; j++) {19                int[] worker = workerList.get(j);20                if (worker[0] < minCost || (worker[0] == minCost && worker[1] < minOriginalIndex)) {21                    minCost = worker[0];22                    minOriginalIndex = worker[1];23                    minIndexInList = j;24                }25            }26 27            // Check last 'candidates' workers28            int start = Math.max(0, workerList.size() - candidates);29            for (int j = start; j < workerList.size(); j++) {30                int[] worker = workerList.get(j);31                if (worker[0] < minCost || (worker[0] == minCost && worker[1] < minOriginalIndex)) {32                    minCost = worker[0];33                    minOriginalIndex = worker[1];34                    minIndexInList = j;35                }36            }37 38            if (minIndexInList != -1) {39                totalCost += minCost;40                workerList.remove(minIndexInList);41            }42        }43        return totalCost;44    }45}

Complexity

Time

O(k * n). The outer loop runs `k` times. Inside, finding the candidates involves scanning up to `n` elements in the worst case (if using a boolean array) or `O(candidates)` if using a list but with an `O(n)` removal cost. Both variations lead to an overall complexity that is too slow.

Space

O(n). A boolean array or a list is used to keep track of hired/available workers, which requires space proportional to the total number of workers.

Trade-offs

Pros

Simple to understand and implement as it directly models the rules given in the problem.

Cons

Very inefficient due to repeated full or partial scans of the costs array.
The time complexity of O(k * n) is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.

A much more efficient approach uses two min-priority queues (min-heaps) to manage the candidate pools. One priority queue, leftPQ, will store candidates from the beginning of the array, and another, rightPQ, will store candidates from the end. This structure avoids re-scanning the array in every session, as the heaps can provide the minimum-cost candidate in logarithmic time, which is a significant improvement.

Algorithm

Initialize totalCost = 0, and two pointers left = 0 and right = n - 1.
Create two min-priority queues, leftPQ and rightPQ. The comparator should prioritize lower cost, then lower index.
Populate leftPQ by adding the first candidates workers (costs[0] to costs[candidates-1]). Update left to candidates.
Populate rightPQ by adding the last candidates workers, but only if their index is not already covered by the left pool (i.e., index i >= left). Update right accordingly.
Loop k times: a. Peek at the top elements of both PQs: leftCandidate and rightCandidate. b. If one queue is empty, choose the candidate from the non-empty one. c. If both are non-empty, compare them. If leftCandidate.cost <= rightCandidate.cost, choose the left one. Otherwise, choose the right one. (The tie-breaking by index is implicitly handled if costs are equal, as the left candidate will always have a smaller index). d. Add the chosen candidate's cost to totalCost and poll() from the corresponding PQ. e. If the left and right pointers have not crossed (left <= right): i. If the left candidate was chosen, offer the worker at costs[left] to leftPQ and increment left. ii. If the right candidate was chosen, offer the worker at costs[right] to rightPQ and decrement right.
Return totalCost.

Walkthrough

We maintain two pointers, left and right, to track the boundaries of the workers in the middle of the array that have not yet been considered for the candidate pools. We initialize two min-priority queues to store pairs of [cost, index] to handle tie-breaking correctly.

First, we populate leftPQ with the first candidates workers and rightPQ with the last candidates workers. We must handle the edge case where these two pools overlap from the start (2 * candidates >= costs.length) by ensuring no worker is added to both queues. The left and right pointers are then updated to point just beyond these initial pools.

We then loop k times for the hiring sessions. In each session:

We examine the top elements of both leftPQ and rightPQ.
We select the worker with the lower cost. If costs are equal, we choose the one with the smaller index (which will be the one from leftPQ).
We add the cost of the chosen worker to totalCost and remove them from their priority queue.
If we hired a worker, we add a new candidate to the pool if one is available. For example, if we hired from leftPQ and the left pointer is still less than or equal to the right pointer, we add the worker at index left to leftPQ and increment left. This ensures the candidate pools are always replenished from the available workers.

This process efficiently finds the cheapest worker in each round without expensive scans.

1import java.util.PriorityQueue;2 3class Solution {4    public long totalCost(int[] costs, int k, int candidates) {5        // Min-heap for the first 'candidates' workers, stores {cost, index}6        PriorityQueue<int[]> leftPQ = new PriorityQueue<>((a, b) -> {7            if (a[0] != b[0]) {8                return a[0] - b[0];9            }10            return a[1] - b[1];11        });12 13        // Min-heap for the last 'candidates' workers14        PriorityQueue<int[]> rightPQ = new PriorityQueue<>((a, b) -> {15            if (a[0] != b[0]) {16                return a[0] - b[0];17            }18            return a[1] - b[1];19        });20 21        int left = 0;22        int right = costs.length - 1;23        long totalCost = 0;24 25        // Loop k times to hire k workers26        for (int i = 0; i < k; i++) {27            // Fill the left PQ up to 'candidates' size, if there are workers available28            while (leftPQ.size() < candidates && left <= right) {29                leftPQ.offer(new int[]{costs[left], left});30                left++;31            }32            // Fill the right PQ up to 'candidates' size, if there are workers available33            while (rightPQ.size() < candidates && left <= right) {34                rightPQ.offer(new int[]{costs[right], right});35                right--;36            }37 38            int[] leftCandidate = leftPQ.peek();39            int[] rightCandidate = rightPQ.peek();40 41            if (leftCandidate == null && rightCandidate == null) {42                break; // No more workers to hire43            }44 45            // Decide which candidate to hire46            if (rightCandidate == null || (leftCandidate != null && leftCandidate[0] <= rightCandidate[0])) {47                totalCost += leftCandidate[0];48                leftPQ.poll();49            } else {50                totalCost += rightCandidate[0];51                rightPQ.poll();52            }53        }54 55        return totalCost;56    }57}

Complexity

Time

O((k + candidates) * log(candidates)). A more precise analysis shows that we perform `2*candidates` initial insertions and then `k` poll/offer operations. Each operation on a heap of size `candidates` takes `O(log(candidates))`. Thus, the total time is dominated by these heap operations.

Space

O(candidates). The two priority queues will hold at most `2 * candidates` elements combined, plus any workers from the middle section that are added later. The total space is bounded by the number of candidates.

Trade-offs

Pros

Highly efficient for the given constraints, with a time complexity of O((k + candidates) * log(candidates)).
Effectively uses priority queues to avoid expensive re-scanning of the array.
Scales well with large inputs.

Cons

The implementation is more complex than a direct simulation.
Requires careful management of two data structures, pointers, and edge cases like overlapping candidate pools.

Solutions

Solution

1class Solution {2public3  long totalCost(int[] costs, int k, int candidates) {4    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->{5      if (a[0] == b[0]) {6        return a[1] - b[1];7      }8      return a[0] - b[0];9    });10    int n = costs.length;11    int i = candidates - 1, j = n - candidates;12    for (int h = 0; h < candidates; ++h) {13      q.offer(new int[]{costs[h], h});14    }15    for (int h = n - candidates; h < n; ++h) {16      if (h > i) {17        q.offer(new int[]{costs[h], h});18      }19    }20    long ans = 0;21    while (k-- > 0) {22      var e = q.poll();23      int c = e[0], x = e[1];24      ans += c;25      if (x <= i) {26        if (++i < j) {27          q.offer(new int[]{costs[i], i});28        }29      }30      if (x >= j) {31        if (--j > i) {32          q.offer(new int[]{costs[j], j});33        }34      }35    }36    return ans;37  }38}

1using pii = pair < int , int > ; class Solution { public: long long totalCost ( vector < int >& costs , int k , int candidates ) { priority_queue < pii , vector < pii > , greater < pii >> q ; int n = costs . size (); int i = candidates - 1 , j = n - candidates ; for ( int h = 0 ; h < candidates ; ++ h ) q . push ({ costs [ h ], h }); for ( int h = n - candidates ; h < n ; ++ h ) if ( h > i ) q . push ({ costs [ h ], h }); long long ans = 0 ; while ( k -- ) { auto [ c , x ] = q . top (); q . pop (); ans += c ; if ( x <= i ) { if ( ++ i < j ) { q . push ({ costs [ i ], i }); } } if ( x >= j ) { if ( -- j > i ) { q . push ({ costs [ j ], j }); } } } return ans ; } };

1class Solution:2    def totalCost(self, costs: List[int], k: int, candidates: int) -> int: q = [] n = len(costs) i, j = candidates - 1, n - candidates for h in range(candidates): q . append((costs[h], h)) for h in range(n - candidates, n): if h > i: q . append((costs[h], h)) heapify(q) ans = 0 for _ in range(k): c, x = heappop(q) ans += c if x <= i: i += 1 if i < j: heappush(q, (costs[i], i)) if x >= j: j -= 1 if i < j: heappush(q, (costs[j], j)) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem