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.
class Solution:
def totalCost(self, 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 — hopeless.
Approach 2 — Two min-heaps with fill pointers
The insight: 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; taking from the back slides one in from the right. So the two windows are just two min-heaps that get refilled from a shrinking middle. A binary min-heap gives O(log n) insert and pop-min — exactly the “cheapest of a slowly changing set” primitive we need.
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.
import heapq
class Solution:
def totalCost(self, 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
The insight: when 2 * candidates >= n, the two windows cover the entire row from session 1 onward, and they always will. The elaborate window machinery collapses: the answer is simply the sum of the k cheapest costs.
class Solution:
def totalCost(self, 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 self.two_heaps(costs, k, candidates)
def two_heaps(self, 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
Walkthrough of costs = [1,2,4,1], k = 3, candidates = 3: 2 * 3 >= 4, so sort → [1,1,2,4], 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 windows overlap, but a one-liner.
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.