What is the brute force approach and complexity for Total Cost to Hire K Workers?

Each session, check the first and last candidates; hire the cheapest and remove it from the list with time complexity O(K · N) and space complexity O(N).

What is the optimal approach and complexity for Total Cost to Hire K Workers?

A min-heap for the left end and one for the right end, fed by two pointers that never overlap with optimal time complexity O((K + C) log C) and space complexity O(C).

How do you identify the pattern for Total Cost to Hire K Workers?

Look for key signals in the prompt: "first candidates and last candidates" indicates Only the two ends are visible, so they become two pools: front (left end) and back (right end).; "cheapest, ties go to the smaller index" indicates Each pool is a min-heap keyed by (cost, index).; "hire exactly k, one per session" indicates A hire removes a worker from one pool, and that pool is refilled from the locked middle..

Total Cost to Hire K Workers

Medium·LeetCode #2462 Pro OnlyMedium

LeetCode

Problem Statement

You have n workers. Worker i asks for costs[i] coins. You must hire exactly k workers, one per session.

In each session, look at the first candidates workers who are still unhired, and the last candidates workers who are still unhired. Hire the cheapest worker from those two groups. If two of them cost the same, hire the one with the smaller original index. A hired worker cannot be hired again.

If the two groups overlap (fewer than 2 × candidates workers remain), every remaining worker is a candidate.

Return the total cost of the k workers you hire.

Input

costs, an integer array, and two integers k and candidates.

Output

The total cost of the k hired workers, as a 64-bit number.

Example 1

Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4

Output: 11

Session 1: the first four are [17,12,10,2] and the last four are [2,11,20,8]. Both cost-2 workers qualify, and the one at index 3 has the smaller index, so hire it. Session 2: the other cost-2 worker (index 5) is now among the last four, so hire it. Session 3: the cheapest candidate is the cost-7 worker at index 4. 2 + 2 + 7 = 11.

Example 2

Input: costs = [1,2,4,1], k = 3, candidates = 3

Output: 4

Only 4 workers remain and 2 × 3 > 4, so every worker is a candidate. Hire the cost-1 worker at index 0, then the cost-1 worker at index 3, then the cost-2 worker at index 1. 1 + 1 + 2 = 4.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“first candidates and last candidates”

→ Only the two ends are visible, so they become two pools: front (left end) and back (right end).

“cheapest, ties go to the smaller index”

→ Each pool is a min-heap keyed by (cost, index).

“hire exactly k, one per session”

→ A hire removes a worker from one pool, and that pool is refilled from the locked middle.

Approach Complexity Ladder

Brute Force — rescan both ends every sessionO(K · N)O(N)

Each session, check the first and last candidates; hire the cheapest and remove it from the list

Optimal — two min-heaps, one for each endO((K + C) log C)O(C)

A min-heap for the left end and one for the right end, fed by two pointers that never overlap

Brute Force Intuition

Keep the unhired workers in a plain list, in their original order. Each session, look only at the two ends, the first and last candidates workers, take the cheapest (ties go to the smaller index), remove it from the list, and repeat for k sessions.

Recognition rule for this sub-pattern:

One heap holds what you can use now, the other what unlocks later. Move items across as conditions change.

Remember this · Two Heaps

Trigger

Running median, sliding median, choosing from two pools (available vs locked).

Think

Can I split the data into two halves and only care about the boundary between them?

Key question

How do I rebalance so the sizes differ by at most one?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Heaps translate into production architectures and low-level memory mechanics.

LLD Architecture

Real-time Metrics & Rolling Percentiles

Calculating streaming median and P99 latency in production telemetry systems.

Explore Track

C++ Internals

Smart Pointers & Ownership Semantics

Managing node ownership without memory leaks across priority queues.

Explore Track

Process Tasks Using Servers IPO