Two City Scheduling

📋

Problem

Imagine you are organizing a conference and need to send exactly half of the attendees to city A and the other half to city B, minimizing total travel costs.

There are 2n people and two cities: city A and city B. The cost of sending the i-th person to city A is costs[i][0], and to city B is costs[i][1]. You need to send exactly n people to city A and n people to city B. Find the minimum total cost to do so.

2n == costs.length1 ≤ n ≤ 10^5costs[i].length == 21 ≤ costs[i][j] ≤ 10^4

Edge cases: All costs to city A are cheaper → output sum of first n costs to city AAll costs to city B are cheaper → output sum of first n costs to city BCosts are equal for both cities for all people → output sum of costs for any n assigned to each city

</>

IDE

def twoCitySchedCost(costs: list[list[int]]) -> int:public int twoCitySchedCost(int[][] costs)int twoCitySchedCost(vector<vector<int>>& costs)function twoCitySchedCost(costs)

def twoCitySchedCost(costs):
    # Write your solution here
    pass

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int twoCitySchedCost(vector<vector<int>>& costs) {
    // Write your solution here
    return 0;
}

function twoCitySchedCost(costs) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Sum of cheapest city per person without balancingAssigning each person to their individually cheapest city ignoring the constraint of exactly n people per city.✅ Sort people by cost difference and assign first n to city A and rest to city B.

Wrong: Crash or error on empty inputNo check for empty costs array before processing.✅ Add base case: if costs is empty, return 0 immediately.

Wrong: Incorrect total cost due to off-by-one in assignment countNot enforcing exactly n assignments per city, leading to unbalanced assignments.✅ Track count of assignments and ensure exactly n people assigned to each city.

Wrong: Wrong output due to incorrect sorting orderSorting by cost difference in descending order or by wrong key.✅ Sort ascending by (costA - costB) to prioritize people cheaper to city A.

Wrong: TLE on large inputsUsing brute force or exponential approach instead of sorting and greedy.✅ Implement O(n log n) sorting and greedy assignment to meet time constraints.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly.

Think about common greedy pitfalls and global vs local decisions.

Optimize your solution to handle large inputs efficiently.

t1_01basic

Input{"costs":[[30,200],[10,20],[30,20],[400,50]]}

Expected110

⏱ Performance - must finish in 2000ms

Send person 0 and 3 to city A (costs 10 + 30 = 40), and person 1 and 2 to city B (costs 200 + 50 = 70). Total cost = 40 + 70 = 110.

💡 Consider sorting people by the difference in cost between city A and city B.

💡 Assign the first n people with the largest savings to city A, and the rest to city B.

💡 Sort by (costA - costB), send first n to city A, rest to city B, sum costs accordingly.

Why it failed: Incorrect total cost indicates failure to correctly assign exactly n people to each city. Fix by sorting by cost difference and assigning first n to city A, rest to city B.

✓ Correctly computed minimum total cost by proper assignment.

t1_02basic

Input{"costs":[[259,770],[184,139],[577,469],[926,667],[448,54],[840,118]]}

Expected1859

⏱ Performance - must finish in 2000ms

Optimal assignment sends persons 0,3,4 to city A and persons 1,2,5 to city B with total cost 259+184+840+54+667+469=1859.

💡 Calculate cost differences and sort to decide assignments.

💡 Assign first n people with smallest cost difference to city A, rest to city B.

💡 Sort by (costA - costB), assign first 3 to city A, others to city B, sum costs.

Why it failed: Wrong output means incorrect sorting or assignment count. Ensure exactly n people assigned to each city after sorting by cost difference.

✓ Correctly minimized total cost with balanced assignments.

t2_01edge

Input{"costs":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input means no people to assign, so total cost is 0.

💡 Check how your code handles empty input arrays.

💡 Return 0 immediately if costs array is empty.

💡 Add a base case: if costs is empty, return 0.

Why it failed: Code crashes or returns non-zero on empty input. Fix by adding a check for empty costs and returning 0.

✓ Handles empty input correctly with zero cost.

t2_02edge

Input{"costs":[[100,200],[300,400]]}

Expected500

⏱ Performance - must finish in 2000ms

With n=1, assign person 0 to city A (100) and person 1 to city B (400) or vice versa; minimal total cost is 300 by assigning person 0 to city A and person 1 to city B.

💡 Test with smallest non-empty input (n=1).

💡 Ensure exactly one person assigned to each city.

💡 Assign person with cheaper city A cost to city A, other to city B.

Why it failed: Fails to assign exactly one person to each city or miscalculates cost. Fix by enforcing n assignments per city.

✓ Correctly assigns single pair with minimal cost.

t2_03edge

Input{"costs":[[10,10],[10,10],[10,10],[10,10]]}

Expected40

⏱ Performance - must finish in 2000ms

All costs equal; any assignment with 2 people to each city results in total cost 40 (4*10).

💡 Consider cases where costs are equal for both cities.

💡 Any balanced assignment yields the same total cost.

💡 Sum all costs and divide by 2 since half go to each city.

Why it failed: Incorrect output means code depends on cost difference incorrectly. Fix by allowing any balanced assignment when costs are equal.

✓ Correctly handles equal costs with balanced assignment.

t3_01corner

Input{"costs":[[10,100],[20,90],[30,80],[40,70],[50,60],[60,50]]}

Expected240

⏱ Performance - must finish in 2000ms

Greedy by cheapest city per person fails; sorting by cost difference and assigning first n to city A and rest to city B yields minimal cost 210.

💡 Beware of greedy approach assigning each person to cheapest city individually.

💡 Sort by cost difference to decide assignments globally.

💡 Assign first n people with smallest (costA - costB) to city A, rest to city B.

Why it failed: Fails due to greedy assignment per person ignoring global cost difference. Fix by sorting all people by cost difference and assigning first n to city A.

✓ Correctly avoids greedy trap by sorting and assigning globally.

t3_02corner

Input{"costs":[[10,100],[10,100],[10,100],[10,100]]}

Expected220

⏱ Performance - must finish in 2000ms

All cheaper to city A but must assign exactly n=2 to each city; minimal cost is 220 by sending 2 to city A and 2 to city B.

💡 Check that exactly n people are assigned to each city even if one city is always cheaper.

💡 Sorting by cost difference helps enforce balanced assignment.

💡 Assign first n people to city A, rest to city B regardless of absolute costs.

Why it failed: Fails by assigning all to cheaper city ignoring n constraint. Fix by enforcing exactly n assignments per city after sorting.

✓ Correctly enforces balanced assignment despite cost bias.

t3_03corner

Input{"costs":[[50,60],[60,50],[70,40],[80,30],[90,20],[100,10]]}

Expected240

⏱ Performance - must finish in 2000ms

Reverse cost difference order; sorting by (costA - costB) and assigning first n to city A yields minimal cost 210.

💡 Test sorting correctness when cost differences are negative.

💡 Ensure sorting by (costA - costB) ascending.

💡 Assign first n people after sorting to city A, rest to city B.

Why it failed: Fails due to incorrect sorting order or sign of cost difference. Fix by sorting ascending by (costA - costB).

✓ Correctly handles negative cost differences in sorting.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n log n) solution to complete within 2 seconds.

💡 Use sorting by cost difference for O(n log n) complexity.

💡 Avoid brute force or exponential approaches.

💡 Implement greedy assignment after sorting to meet time constraints.

Why it failed: TLE due to exponential or quadratic complexity. Fix by using O(n log n) sorting and greedy assignment.

✓ Efficient O(n log n) solution passes performance test.

Practice

1. Given the following code, what is the return value when gas = [2, 3, 4] and cost = [3, 4, 3]?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    if sum(net) < 0:
        return -1
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

print(canCompleteCircuit(gas, cost))

easy

A. -1

B. 0

C. 1

D. 2

Solution

1. Step 1: Compute net array

   net = [2-3, 3-4, 4-3] = [-1, -1, 1], sum(net) = -1 which is less than 0, so return -1 immediately.

2. Step 2: Check sum(net)

   Since sum(net) < 0, no start station can complete the circuit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of net gas is negative, no solution exists [OK]

Hint: Sum net gas < 0 means no solution [OK]

Common Mistakes:

• Forgetting to check total gas vs cost
• Misindexing prefix sums
• Returning wrong start index

2. Given the following Python code implementing the max heap approach to reorganize a string, what is the output when the input is "aab"?

import heapq
from collections import Counter

def reorganizeString(s: str) -> str:
    freq = Counter(s)
    max_heap = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(max_heap)
    prev_count, prev_char = 0, ''
    result = []

    while max_heap:
        count, ch = heapq.heappop(max_heap)
        result.append(ch)
        if prev_count < 0:
            heapq.heappush(max_heap, (prev_count, prev_char))
        prev_count, prev_char = count + 1, ch

    res_str = ''.join(result)
    if len(res_str) != len(s):
        return ""
    return res_str

print(reorganizeString("aab"))

easy

A. "baa"

B. "aab"

C. "aba"

D. "" (empty string)

Solution

1. Step 1: Trace first iteration

   Heap contains [(' -2', 'a'), ('-1', 'b')]. Pop (-2, 'a'), append 'a', prev_count= -1, prev_char='a'.

2. Step 2: Trace second iteration

   Pop (-1, 'b'), append 'b', push back (-1, 'a') since prev_count < 0, update prev_count=0, prev_char='b'. Next pop (-1, 'a'), append 'a'. Result is "aba".

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output "aba" has no two adjacent same chars and uses all letters [OK]

Hint: Trace heap pops and pushes carefully [OK]

Common Mistakes:

• Returning input unchanged
• Appending characters without heap pushback
• Off-by-one in count update

3. What is the time complexity of the peak-valley approach for the Best Time to Buy and Sell Stock II problem, and why might some candidates incorrectly think it is higher?

medium

A. O(1) since only constant extra space is used

B. O(n^2) because of nested while loops

C. O(n log n) due to sorting or searching steps

D. O(n) because each element is visited at most twice in the loops

Solution

1. Step 1: Identify loop behavior

   Though there are nested while loops, the index i only moves forward and never revisits elements.

2. Step 2: Conclude time complexity

   Each element is processed at most twice, so total time is linear O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Index i increments monotonically through array [OK]

Hint: Index i only moves forward, no repeated visits [OK]

Common Mistakes:

• Assuming nested loops multiply to O(n^2)
• Confusing space complexity with time complexity
• Thinking sorting is involved

4. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

5. The following code attempts to form the largest number from a list of integers. Which line contains a subtle bug that causes incorrect output on inputs like [0, 0, 0]?

medium

A. Line 8: Returning concatenated string without zero check

B. Line 4-6: Custom comparator function

C. Line 7: Sorting with custom comparator

D. Line 3: Converting integers to strings

Solution

1. Step 1: Trace output for input [0,0,0]

   After sorting, nums_str is ['0', '0', '0'], concatenation is '000'.

2. Step 2: Identify missing check for all zeros

   Without checking if first element is '0', the function returns '000' instead of '0'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding a check to return '0' if nums_str[0] == '0' fixes the bug [OK]

Hint: Check if first string is '0' to handle all-zero case [OK]

Common Mistakes:

• Forgetting all-zero check
• Incorrect comparator logic
• Sorting without custom comparator