TL;DR
Two min-heaps (front window, back window) with fill pointers: O((k + candidates) log candidates) time, O(candidates) space.
Approach 1 — Brute force: rescan the row every session
The naive translation of the rules: keep the remaining workers in a list; each session, scan the first candidates and last candidates positions for the minimum (front positions first so ties go to the smaller index), hire it, and delete it from the list.
def totalCost(costs: list[int], k: int, candidates: int) -> int:
remaining = list(costs)
total = 0
for _ in range(k):
m = len(remaining)
best_idx = -1
for i in range(m):
if i < candidates or i >= m - candidates:
if best_idx == -1 or remaining[i] < remaining[best_idx]:
best_idx = i
total += remaining.pop(best_idx)
return total
Complexity: each session scans up to 2 * candidates slots and list.pop shifts up to O(n) elements — O(k · (candidates + n)) time, O(n) space.
With k, candidates, and n all up to 10^5, that is on the order of 10^10 operations, far too slow.
Approach 2 — Two min-heaps with fill pointers
Hiring never changes which workers are visible except at the seam: taking someone from the front window slides one new worker in from the left, and taking from the back slides one in from the right. The two windows are therefore two min-heaps refilled from a shrinking middle. A binary min-heap gives O(log n) insert and pop-min, which is the operation this problem repeats.
Pointers i (next unseen from the left) and j (next unseen from the right) guarantee no worker enters both heaps: refilling stops when i > j.
flowchart LR
F["Front window<br/>min-heap<br/>indices 0..i-1"]
M["Unseen middle<br/>indices i..j"]
B["Back window<br/>min-heap<br/>indices j+1..n-1"]
F -->|"pop front pulls costs[i], i++"| M
M -->|"pop back pulls costs[j], j--"| B
import heapq
def totalCost(costs: list[int], k: int, candidates: int) -> int:
n = len(costs)
i, j = 0, n - 1
front: list[int] = []
back: list[int] = []
total = 0
for _ in range(k):
while len(front) < candidates and i <= j:
heapq.heappush(front, costs[i])
i += 1
while len(back) < candidates and i <= j:
heapq.heappush(back, costs[j])
j -= 1
if back and (not front or back[0] < front[0]):
total += heapq.heappop(back)
else:
total += heapq.heappop(front)
return total
Tie-breaking is handled by the strict < on the back heap: when the two minima are equal we pop from front, which always holds smaller original indices than back. (Within one heap, ties among values are interchangeable — the cost is identical either way, so the sum is unaffected.)
Walkthrough of costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4:
- Fill:
front takes indices 0–3 → contains {17,12,10,2} (min 2), i = 4; back takes indices 8,7,6,5 → {8,20,11,2} (min 2), j = 4.
- Session 1:
back[0] = 2 is not < front[0] = 2, so pop front → total = 2. Refill front: i = 4 <= j = 4, push costs[4] = 7, i = 5. Middle exhausted.
- Session 2:
front min is 7, back min is 2 → pop back → total = 4. No refill possible (i > j).
- Session 3:
front min 7 vs back min 8 → pop front → total = 11.
Complexity: at most 2 * candidates + k pushes and k pops, each O(log candidates) → O((k + candidates) log candidates) time, O(candidates) space.
Approach 3 — Degenerate case shortcut: one sort
When 2 * candidates >= n, the two windows cover the entire row from session 1 onward and continue to do so after every hire. The window logic is unnecessary: the answer is the sum of the k cheapest costs.
def two_heaps(costs: list[int], k: int, candidates: int) -> int:
import heapq
i, j = 0, len(costs) - 1
front: list[int] = []
back: list[int] = []
total = 0
for _ in range(k):
while len(front) < candidates and i <= j:
heapq.heappush(front, costs[i])
i += 1
while len(back) < candidates and i <= j:
heapq.heappush(back, costs[j])
j -= 1
if back and (not front or back[0] < front[0]):
total += heapq.heappop(back)
else:
total += heapq.heappop(front)
return total
def totalCost(costs: list[int], k: int, candidates: int) -> int:
if 2 * candidates >= len(costs):
return sum(sorted(costs)[:k])
# otherwise fall back to the two-heap method (Approach 2)
return two_heaps(costs, k, candidates)
Walkthrough of costs = [1,2,4,1], k = 3, candidates = 3: 2 * 3 >= 4, so sort → [1,1,2,4] and sum the first three → 4.
Complexity: O(n log n) time, O(n) space for the sorted copy. Same asymptotics as the heap path when the windows overlap, expressed in one line.
Common pitfalls
- Letting the same worker enter both heaps when the windows overlap — the
i <= j guard is what prevents double-hiring one person.
- Breaking ties toward the back heap (
<= instead of < in the comparison) — the rules say the smaller index wins, and every front-heap worker has a smaller index than every back-heap worker.
- Refilling only the heap you popped from is fine, but refilling before the first session must fill front first: if you fill back first, the middle pointer logic assigns overlapping workers to the wrong side and tie-breaking silently changes.
- Forgetting that heaps can go empty near the end (
k close to n) — guard the pop with not front / back and ... checks.
Pattern takeaway
When a process repeatedly extracts the minimum from a set that changes by one element at a time, model each such set as a min-heap and feed it with pointers. Two ends of an array → two heaps + two pointers is a recurring shape; and always check whether the constraints degenerate (windows covering everything) into a plain sort.