Minimum Cost to Connect Sticks

🎯

Minimum Cost to Connect Sticks

mediumGREEDYAmazonGoogle

Imagine you have several wooden sticks and want to connect them all into one stick. Each time you connect two sticks, it costs you the sum of their lengths. How do you minimize the total cost?

💡 This problem is a classic example of greedy algorithms where the key is to always merge the smallest sticks first. Beginners often struggle because they try to merge sticks arbitrarily or use brute force without realizing the optimal greedy strategy.

📋

Problem Statement

Given an array of integers sticks where sticks[i] is the length of the i-th stick, you can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. The new stick length is also x + y. Return the minimum cost to connect all the sticks into one stick.

1 ≤ sticks.length ≤ 10^51 ≤ sticks[i] ≤ 10^4

💡

Example

Input"[2, 4, 3]"

Output14

Connect sticks 2 and 3 for cost 5, then connect 5 and 4 for cost 9, total cost = 5 + 9 = 14.

• Single stick [5] → cost 0 because no connections needed
• All sticks equal length [1,1,1,1] → cost accumulates merging smallest pairs
• Large number of sticks with minimum length [1,1,...,1] → tests efficiency
• Two sticks only [10, 20] → cost is sum of both, simplest merge

⚠️

Common Mistakes

Merging sticks in arbitrary order

Leads to higher total cost, not minimal

✅ Always merge the two smallest sticks first using a min-heap

Not updating the data structure after merges

Incorrect merges or infinite loops

✅ After merging, insert the new stick back into the min-heap

Using a max-heap or sorting descending

Merges largest sticks first, increasing cost

✅ Use a min-heap or sort ascending to get smallest sticks first

Not handling single stick or empty input

May cause errors or incorrect cost

✅ Return 0 cost if sticks length ≤ 1

🧠

Brute Force (Try All Merge Orders)

💡 This approach exists to understand the problem deeply by exploring all possible ways to merge sticks, even though it is inefficient. It helps grasp why greedy is needed.

Intuition

Try every possible pair of sticks to merge, recursively compute the cost for the remaining sticks, and pick the minimum total cost.

Algorithm

1. If only one stick remains, return 0 cost.
2. For every pair of sticks, merge them and recursively compute cost for the new list.
3. Add the cost of merging the pair to the recursive result.
4. Return the minimum total cost among all pairs.

💡 The recursion and trying all pairs is hard to visualize because the number of combinations grows exponentially.

</>

Code

from typing import List

def min_cost_brute_force(sticks: List[int]) -> int:
    if len(sticks) == 1:
        return 0
    min_cost = float('inf')
    for i in range(len(sticks)):
        for j in range(i+1, len(sticks)):
            merged = sticks[i] + sticks[j]
            new_sticks = [sticks[k] for k in range(len(sticks)) if k != i and k != j] + [merged]
            cost = merged + min_cost_brute_force(new_sticks)
            if cost < min_cost:
                min_cost = cost
    return min_cost

# Driver code
if __name__ == '__main__':
    sticks = [2, 4, 3]
    print(min_cost_brute_force(sticks))  # Output: 14

Line Notes

if len(sticks) == 1:Base case: no cost if only one stick remains

for i in range(len(sticks))Outer loop picks first stick to merge

for j in range(i+1, len(sticks))Inner loop picks second stick to merge

merged = sticks[i] + sticks[j]Calculate cost of merging two sticks

new_sticks = [sticks[k] for k in range(len(sticks)) if k != i and k != j] + [merged]Create new list after merging two sticks

cost = merged + min_cost_brute_force(new_sticks)Add current merge cost plus recursive cost

if cost < min_cost:Track minimum cost among all merges

return min_costReturn the minimum total cost found

import java.util.*;

public class MinCostConnectSticksBrute {
    public static int minCostBruteForce(List<Integer> sticks) {
        if (sticks.size() == 1) return 0;
        int minCost = Integer.MAX_VALUE;
        for (int i = 0; i < sticks.size(); i++) {
            for (int j = i + 1; j < sticks.size(); j++) {
                int merged = sticks.get(i) + sticks.get(j);
                List<Integer> newSticks = new ArrayList<>();
                for (int k = 0; k < sticks.size(); k++) {
                    if (k != i && k != j) newSticks.add(sticks.get(k));
                }
                newSticks.add(merged);
                int cost = merged + minCostBruteForce(newSticks);
                if (cost < minCost) minCost = cost;
            }
        }
        return minCost;
    }

    public static void main(String[] args) {
        List<Integer> sticks = Arrays.asList(2, 4, 3);
        System.out.println(minCostBruteForce(sticks)); // Output: 14
    }
}

Line Notes

if (sticks.size() == 1) return 0;Base case: no cost if only one stick remains

for (int i = 0; i < sticks.size(); i++)Outer loop picks first stick to merge

for (int j = i + 1; j < sticks.size(); j++)Inner loop picks second stick to merge

int merged = sticks.get(i) + sticks.get(j);Calculate cost of merging two sticks

List<Integer> newSticks = new ArrayList<>();Create new list for merged sticks

newSticks.add(merged);Add merged stick to new list

int cost = merged + minCostBruteForce(newSticks);Add current merge cost plus recursive cost

if (cost < minCost) minCost = cost;Track minimum cost among all merges

return minCost;Return the minimum total cost found

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minCostBruteForce(vector<int> &sticks) {
    if (sticks.size() == 1) return 0;
    int minCost = INT_MAX;
    for (int i = 0; i < sticks.size(); i++) {
        for (int j = i + 1; j < sticks.size(); j++) {
            int merged = sticks[i] + sticks[j];
            vector<int> newSticks;
            for (int k = 0; k < sticks.size(); k++) {
                if (k != i && k != j) newSticks.push_back(sticks[k]);
            }
            newSticks.push_back(merged);
            int cost = merged + minCostBruteForce(newSticks);
            if (cost < minCost) minCost = cost;
        }
    }
    return minCost;
}

int main() {
    vector<int> sticks = {2, 4, 3};
    cout << minCostBruteForce(sticks) << endl; // Output: 14
    return 0;
}

Line Notes

if (sticks.size() == 1) return 0;Base case: no cost if only one stick remains

for (int i = 0; i < sticks.size(); i++)Outer loop picks first stick to merge

for (int j = i + 1; j < sticks.size(); j++)Inner loop picks second stick to merge

int merged = sticks[i] + sticks[j];Calculate cost of merging two sticks

vector<int> newSticks;Create new vector for merged sticks

newSticks.push_back(merged);Add merged stick to new vector

int cost = merged + minCostBruteForce(newSticks);Add current merge cost plus recursive cost

if (cost < minCost) minCost = cost;Track minimum cost among all merges

return minCost;Return the minimum total cost found

function minCostBruteForce(sticks) {
    if (sticks.length === 1) return 0;
    let minCost = Infinity;
    for (let i = 0; i < sticks.length; i++) {
        for (let j = i + 1; j < sticks.length; j++) {
            let merged = sticks[i] + sticks[j];
            let newSticks = sticks.filter((_, idx) => idx !== i && idx !== j);
            newSticks.push(merged);
            let cost = merged + minCostBruteForce(newSticks);
            if (cost < minCost) minCost = cost;
        }
    }
    return minCost;
}

// Test
console.log(minCostBruteForce([2,4,3])); // Output: 14

Line Notes

if (sticks.length === 1) return 0;Base case: no cost if only one stick remains

for (let i = 0; i < sticks.length; i++)Outer loop picks first stick to merge

for (let j = i + 1; j < sticks.length; j++)Inner loop picks second stick to merge

let merged = sticks[i] + sticks[j];Calculate cost of merging two sticks

let newSticks = sticks.filter((_, idx) => idx !== i && idx !== j);Create new array excluding merged sticks

newSticks.push(merged);Add merged stick to new array

let cost = merged + minCostBruteForce(newSticks);Add current merge cost plus recursive cost

if (cost < minCost) minCost = cost;Track minimum cost among all merges

return minCost;Return the minimum total cost found

⏱

Complexity

TimeO(n! * n) due to trying all pairs and recursive calls

SpaceO(n) recursion stack and new arrays per call

At each step, we try all pairs to merge, leading to factorial growth in possibilities.

💡 For n=5, this means over 100,000 operations, which is impractical for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate greedy.

🧠

Greedy Using Min-Heap (Optimal Strategy)

💡 This approach uses a min-heap to always merge the two smallest sticks first, which is the key insight to minimize total cost.

Intuition

By always merging the two smallest sticks first, we keep the incremental cost as low as possible, similar to Huffman coding.

Algorithm

1. Insert all sticks into a min-heap.
2. While more than one stick remains, extract the two smallest sticks.
3. Merge them and add the cost to total.
4. Insert the merged stick back into the heap.
5. Return the total cost after all merges.

💡 The heap ensures we always pick the smallest sticks efficiently, avoiding costly merges.

</>

Code

import heapq

def min_cost_greedy(sticks):
    if len(sticks) <= 1:
        return 0
    heapq.heapify(sticks)
    total_cost = 0
    while len(sticks) > 1:
        first = heapq.heappop(sticks)
        second = heapq.heappop(sticks)
        cost = first + second
        total_cost += cost
        heapq.heappush(sticks, cost)
    return total_cost

# Driver code
if __name__ == '__main__':
    sticks = [2, 4, 3]
    print(min_cost_greedy(sticks))  # Output: 14

Line Notes

if len(sticks) <= 1:No cost if zero or one stick

heapq.heapify(sticks)Convert list into a min-heap for efficient smallest extraction

first = heapq.heappop(sticks)Extract smallest stick

second = heapq.heappop(sticks)Extract second smallest stick

cost = first + secondCalculate cost of merging two smallest sticks

total_cost += costAccumulate cost of merging two sticks

heapq.heappush(sticks, cost)Insert merged stick back into heap

return total_costReturn total accumulated cost after all merges

import java.util.*;

public class MinCostConnectSticksGreedy {
    public static int minCostGreedy(int[] sticks) {
        if (sticks.length <= 1) return 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int stick : sticks) minHeap.add(stick);
        int totalCost = 0;
        while (minHeap.size() > 1) {
            int first = minHeap.poll();
            int second = minHeap.poll();
            int cost = first + second;
            totalCost += cost;
            minHeap.add(cost);
        }
        return totalCost;
    }

    public static void main(String[] args) {
        int[] sticks = {2, 4, 3};
        System.out.println(minCostGreedy(sticks)); // Output: 14
    }
}

Line Notes

if (sticks.length <= 1) return 0;No cost if zero or one stick

PriorityQueue<Integer> minHeap = new PriorityQueue<>();Min-heap to get smallest sticks efficiently

for (int stick : sticks) minHeap.add(stick);Add all sticks to heap

int first = minHeap.poll();Extract smallest stick

int second = minHeap.poll();Extract second smallest stick

int cost = first + second;Calculate cost of merging two smallest sticks

totalCost += cost;Accumulate cost of merging

minHeap.add(cost);Add merged stick back to heap

return totalCost;Return total accumulated cost after all merges

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int minCostGreedy(vector<int> &sticks) {
    if (sticks.size() <= 1) return 0;
    priority_queue<int, vector<int>, greater<int>> minHeap(sticks.begin(), sticks.end());
    int totalCost = 0;
    while (minHeap.size() > 1) {
        int first = minHeap.top(); minHeap.pop();
        int second = minHeap.top(); minHeap.pop();
        int cost = first + second;
        totalCost += cost;
        minHeap.push(cost);
    }
    return totalCost;
}

int main() {
    vector<int> sticks = {2, 4, 3};
    cout << minCostGreedy(sticks) << endl; // Output: 14
    return 0;
}

Line Notes

if (sticks.size() <= 1) return 0;No cost if zero or one stick

priority_queue<int, vector<int>, greater<int>> minHeap(sticks.begin(), sticks.end());Min-heap initialization with sticks

int first = minHeap.top(); minHeap.pop();Extract smallest stick

int second = minHeap.top(); minHeap.pop();Extract second smallest stick

int cost = first + second;Calculate cost of merging two smallest sticks

totalCost += cost;Accumulate cost of merging

minHeap.push(cost);Add merged stick back to heap

return totalCost;Return total accumulated cost after all merges

class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent] <= this.heap[idx]) break;
            this.swap(parent, idx);
            idx = parent;
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return top;
    }
    bubbleDown() {
        let idx = 0;
        const length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let smallest = idx;
            if (left < length && this.heap[left] < this.heap[smallest]) smallest = left;
            if (right < length && this.heap[right] < this.heap[smallest]) smallest = right;
            if (smallest === idx) break;
            this.swap(idx, smallest);
            idx = smallest;
        }
    }
    size() {
        return this.heap.length;
    }
}

function minCostGreedy(sticks) {
    if (sticks.length <= 1) return 0;
    const minHeap = new MinHeap();
    for (const stick of sticks) minHeap.push(stick);
    let totalCost = 0;
    while (minHeap.size() > 1) {
        const first = minHeap.pop();
        const second = minHeap.pop();
        const cost = first + second;
        totalCost += cost;
        minHeap.push(cost);
    }
    return totalCost;
}

// Test
console.log(minCostGreedy([2,4,3])); // Output: 14

Line Notes

if (sticks.length <= 1) return 0;No cost if zero or one stick

const minHeap = new MinHeap();Create min-heap instance

for (const stick of sticks) minHeap.push(stick);Add all sticks to heap

const first = minHeap.pop();Extract smallest stick

const second = minHeap.pop();Extract second smallest stick

const cost = first + second;Calculate cost of merging two smallest sticks

totalCost += cost;Accumulate cost of merging

minHeap.push(cost);Add merged stick back to heap

return totalCost;Return total accumulated cost after all merges

⏱

Complexity

TimeO(n log n) due to heap operations for n sticks

SpaceO(n) for the heap

Each merge involves two heap pops and one push, each O(log n), repeated n-1 times.

💡 For n=100,000 sticks, this approach is efficient and practical.

Interview Verdict: Accepted

This is the optimal and accepted solution for large inputs.

🧠

Sorting + Simulated Merge (Less Efficient than Heap)

💡 This approach tries to simulate the greedy merges by sorting sticks and merging smallest pairs, but without a heap it is less efficient.

Intuition

Sort sticks and repeatedly merge the smallest two, but since merges create new sticks, we must re-sort or find smallest pairs inefficiently.

Algorithm

1. Sort the sticks initially.
2. While more than one stick remains, merge the first two sticks.
3. Add the merged stick back and re-sort the list.
4. Accumulate the cost of each merge.
5. Return the total cost.

💡 Re-sorting after each merge is inefficient but conceptually simple.

</>

Code

def min_cost_sorting(sticks):
    if len(sticks) <= 1:
        return 0
    sticks.sort()
    total_cost = 0
    while len(sticks) > 1:
        first = sticks.pop(0)
        second = sticks.pop(0)
        cost = first + second
        total_cost += cost
        sticks.append(cost)
        sticks.sort()
    return total_cost

# Driver code
if __name__ == '__main__':
    sticks = [2, 4, 3]
    print(min_cost_sorting(sticks))  # Output: 14

Line Notes

if len(sticks) <= 1:No cost if zero or one stick

sticks.sort()Sort list initially and after each merge to find smallest sticks

first = sticks.pop(0)Remove smallest stick

second = sticks.pop(0)Remove second smallest stick

cost = first + secondCalculate cost of merging two smallest sticks

total_cost += costAccumulate cost of merging

sticks.append(cost)Add merged stick back to list

import java.util.*;

public class MinCostConnectSticksSort {
    public static int minCostSorting(int[] sticks) {
        if (sticks.length <= 1) return 0;
        List<Integer> list = new ArrayList<>();
        for (int stick : sticks) list.add(stick);
        Collections.sort(list);
        int totalCost = 0;
        while (list.size() > 1) {
            int first = list.remove(0);
            int second = list.remove(0);
            int cost = first + second;
            totalCost += cost;
            list.add(cost);
            Collections.sort(list);
        }
        return totalCost;
    }

    public static void main(String[] args) {
        int[] sticks = {2, 4, 3};
        System.out.println(minCostSorting(sticks)); // Output: 14
    }
}

Line Notes

if (sticks.length <= 1) return 0;No cost if zero or one stick

Collections.sort(list);Sort list initially and after each merge to find smallest sticks

int first = list.remove(0);Remove smallest stick

int second = list.remove(0);Remove second smallest stick

int cost = first + second;Calculate cost of merging two smallest sticks

totalCost += cost;Accumulate cost of merging

list.add(cost);Add merged stick back to list

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCostSorting(vector<int> sticks) {
    if (sticks.size() <= 1) return 0;
    sort(sticks.begin(), sticks.end());
    int totalCost = 0;
    while (sticks.size() > 1) {
        int first = sticks[0];
        int second = sticks[1];
        sticks.erase(sticks.begin());
        sticks.erase(sticks.begin());
        int cost = first + second;
        totalCost += cost;
        sticks.push_back(cost);
        sort(sticks.begin(), sticks.end());
    }
    return totalCost;
}

int main() {
    vector<int> sticks = {2, 4, 3};
    cout << minCostSorting(sticks) << endl; // Output: 14
    return 0;
}

Line Notes

if (sticks.size() <= 1) return 0;No cost if zero or one stick

sort(sticks.begin(), sticks.end());Sort list initially and after each merge to find smallest sticks

int first = sticks[0];Get smallest stick

sticks.erase(sticks.begin());Remove second smallest stick

int second = sticks[1];Get second smallest stick

int cost = first + second;Calculate cost of merging two smallest sticks

totalCost += cost;Accumulate cost of merging

sticks.push_back(cost);Add merged stick back to list

function minCostSorting(sticks) {
    if (sticks.length <= 1) return 0;
    sticks.sort((a,b) => a - b);
    let totalCost = 0;
    while (sticks.length > 1) {
        let first = sticks.shift();
        let second = sticks.shift();
        let cost = first + second;
        totalCost += cost;
        sticks.push(cost);
        sticks.sort((a,b) => a - b);
    }
    return totalCost;
}

// Test
console.log(minCostSorting([2,4,3])); // Output: 14

Line Notes

if (sticks.length <= 1) return 0;No cost if zero or one stick

sticks.sort((a,b) => a - b);Sort list initially and after each merge to find smallest sticks

let first = sticks.shift();Remove smallest stick

let second = sticks.shift();Remove second smallest stick

let cost = first + second;Calculate cost of merging two smallest sticks

totalCost += cost;Accumulate cost of merging

sticks.push(cost);Add merged stick back to list

⏱

Complexity

TimeO(n^2 log n) due to repeated sorting after each merge

SpaceO(n) for the list

Each merge requires sorting the list again, which is costly for large n.

💡 For n=1000, this approach is much slower than the heap approach.

Interview Verdict: Accepted but inefficient

Works for small inputs but not scalable; shows why heap is preferred.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the min-heap greedy approach in 95% of interviews for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n)	O(n)	Yes (deep recursion)	N/A	Mention only - never code
2. Greedy Using Min-Heap	O(n log n)	O(n)	No	N/A	Code this approach
3. Sorting + Simulated Merge	O(n^2 log n)	O(n)	No	N/A	Mention as less efficient alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the heap solution, and prepare to explain why greedy works here.

How to Present

Step 1: Clarify problem constraints and examples.Step 2: Describe brute force approach to show understanding.Step 3: Explain greedy intuition and why merging smallest sticks first minimizes cost.Step 4: Implement min-heap solution.Step 5: Test with examples and discuss complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Ability to identify greedy pattern, implement heap, and optimize from brute force to efficient solution.

Common Follow-ups

• What if sticks are very large numbers? → Use 64-bit integers to avoid overflow.
• Can you do this without a heap? → Yes, but less efficient; explain sorting approach.

💡 These follow-ups test understanding of data types and alternative methods.

🔍

Pattern Recognition

When to Use

1) Problem involves merging elements with cost equal to sum, 2) Goal is to minimize total cost, 3) Merging order affects cost, 4) Greedy or heap suggested by problem constraints.

Signature Phrases

'connect sticks with minimum cost''merge smallest first''sum of lengths as cost'

NOT This Pattern When

Problems where merging cost is fixed or independent of elements, or where DP is required for optimal merges.

Similar Problems

Connect Ropes with Minimum Cost - same greedy mergingHuffman Encoding - greedy tree construction minimizing weighted pathMinimum Cost to Merge Stones - DP variant with merging costs

Practice

1. You have a list of tasks represented by characters, each task takes 1 unit of time to execute. The CPU must wait for at least n units of time before executing the same task again. Which approach guarantees the minimum total time to finish all tasks?

easy

A. Dynamic Programming that tries all permutations of task orders to find the minimal schedule

B. Greedy algorithm using a max-heap to always schedule the most frequent available task next

C. Simple round-robin scheduling without considering cooldown intervals

D. Sorting tasks by frequency and inserting idle slots greedily without priority queue

Solution

1. Step 1: Understand the cooldown constraint

   The CPU must wait n units before repeating the same task, so scheduling must consider task frequencies and cooldowns.

2. Step 2: Why max-heap greedy works best

   Using a max-heap prioritizes tasks with the highest remaining frequency, ensuring minimal idle time by always picking the most urgent task available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Max-heap approach matches known optimal solution [OK]

Hint: Max-heap greedily schedules highest frequency tasks first [OK]

Common Mistakes:

• Assuming DP or brute force is needed
• Ignoring cooldown leads to incorrect minimal time
• Greedy without priority queue misses optimal order

2. Identify the bug in the following code snippet for the Task Scheduler problem:

medium

A. Line with 'if cnt + 1 <= 0:' should be 'if cnt + 1 < 0:' to avoid pushing zero counts

B. Line with 'time += cycle if not max_heap else n + 1' should always add cycle, not n+1

C. Line with 'for _ in range(n + 1):' should be 'for _ in range(n):' to match cooldown

D. Line with 'heapq.heapify(max_heap)' should be after the while loop

Solution

1. Step 1: Understand frequency decrement logic

   When a task count reaches zero, it should not be pushed back into the heap.

2. Step 2: Check condition for pushing back tasks

   The condition cnt + 1 <= 0 incorrectly pushes zero counts back, causing infinite loops or extra scheduling.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to cnt + 1 < 0 fixes the bug [OK]

Hint: Only push tasks back if remaining count is negative (still pending) [OK]

Common Mistakes:

• Pushing zero counts back causes infinite loops
• Miscounting cooldown cycles
• Incorrect loop ranges

3. Identify the bug in the following code snippet for Two City Scheduling:

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: abs(x[0] - x[1]))
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total

medium

A. Sorting by absolute difference instead of signed difference

B. Incorrect calculation of n as half the length

C. Adding cost[1] for the first half instead of cost[0]

D. Using enumerate instead of a simple for loop

Solution

1. Step 1: Analyze sorting key

   The code sorts by absolute difference abs(cost[0] - cost[1]) instead of signed difference cost[0] - cost[1].

2. Step 2: Effect of wrong sorting

   Sorting by absolute difference loses the direction of cost preference, causing suboptimal assignments and higher total cost.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Signed difference sorting is required for correct greedy assignment [OK]

Hint: Sort by signed difference, not absolute [OK]

Common Mistakes:

• Sorting by absolute difference
• Miscounting half the people
• Swapping city costs in assignment

4. Suppose now you can reuse boxes infinitely (unlimited supply of each box type). Which modification to the algorithm correctly computes the maximum units that can be loaded on the truck?

hard

A. Use dynamic programming to consider all combinations of boxes up to truckSize, since greedy no longer works

B. Use the same greedy approach but do not reduce truckSize after picking boxes, since supply is unlimited

C. Sort boxTypes by units per box descending and fill the truck entirely with the box type having the highest units per box

D. Sort boxTypes ascending by units per box and pick boxes until truckSize is full

Solution

1. Step 1: Understand unlimited supply impact

   With infinite boxes, the best strategy is to fill the truck entirely with the box type having the highest units per box.

2. Step 2: Identify correct algorithm

   Sorting descending by units per box and taking all truckSize boxes from the top box type yields maximum units efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy fill with highest unit box type maximizes units [OK]

Hint: With infinite supply, pick only highest unit box type [OK]

Common Mistakes:

• Not reducing truckSize leading to infinite loop
• Using DP unnecessarily
• Sorting ascending which is suboptimal

5. Suppose the problem is modified so that dominoes can be rotated multiple times (reused) to achieve uniformity, or the arrays can contain values outside 1-6. Which approach correctly adapts the solution?

hard

A. Check all unique values appearing in either array as candidates with early exit

B. Continue checking only the first domino's two values as candidates, ignoring others

C. Use dynamic programming to track rotations for all possible values 1 to 6 only

D. Sort arrays and greedily pick the most frequent value to minimize rotations

Solution

1. Step 1: Identify candidate values

   With values outside 1-6 and reuse allowed, candidates are all unique values in A and B, not just first domino.

2. Step 2: Check feasibility for each candidate

   For each candidate, verify if all dominoes can be rotated to match it, counting minimal rotations.

3. Step 3: Early exit optimization

   Stop checking candidates as soon as a valid minimal rotation count is found.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Checking all unique values covers extended domain and reuse [OK]

Hint: Check all unique values when domain expands [OK]

Common Mistakes:

• Checking only first domino candidates
• Limiting candidates to 1-6 values only