Two City Scheduling

🎯

Two City Scheduling

mediumGREEDYAmazonGoogleFacebook

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.

💡 This problem is about assigning tasks (people) to two groups (cities) to minimize total cost. Beginners often struggle because the naive approach tries all assignments, which is exponential, and they don't see how sorting by cost difference leads to an optimal greedy solution.

📋

Problem Statement

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

💡

Example

Input"[[10,20],[30,200],[400,50],[30,20]]"

Output110

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.

• All costs to city A are cheaper → output sum of first n costs to city A
• All costs to city B are cheaper → output sum of first n costs to city B
• Costs are equal for both cities for all people → output sum of costs for any n assigned to each city
• Large input size (n=10^5) → solution must be O(n log n) or better

⚠️

Common Mistakes

Not sorting by cost difference but by absolute cost

Leads to suboptimal assignments and higher total cost

✅ Sort by the difference between cost to city A and city B

Assigning more than n people to one city

Violates problem constraints, possibly causing incorrect results or runtime errors

✅ Keep track of counts and assign exactly n people to each city

Using brute force without memoization for large inputs

Causes timeouts or stack overflow errors

✅ Use greedy approach or memoization to optimize

Off-by-one errors in loops when assigning people

Incorrect total cost or index errors

✅ Carefully use correct loop bounds and indices

Not handling equal cost differences correctly

May still get correct answer but logic is unclear or inconsistent

✅ Sorting is stable or handle ties explicitly if needed

🧠

Brute Force (Pure Recursion / Nested Loops / etc.)

💡 This approach tries every possible way to assign people to cities, which is impractical but helps understand the problem's complexity and why optimization is needed.

Intuition

Try all combinations of sending n people to city A and n people to city B, calculate total cost for each, and pick the minimum.

Algorithm

1. Define a recursive function that tracks current index, count of people sent to city A, and total cost so far.
2. At each person, if city A quota not full, recurse by sending them to city A.
3. If city B quota not full, recurse by sending them to city B.
4. Return the minimum cost from all recursive calls.

💡 The recursion tree grows exponentially because each person has two choices, and we must keep track of counts to ensure balanced assignment.

</>

Code

def twoCitySchedCost(costs):
    n = len(costs) // 2
    memo = {}
    def dfs(i, a_count):
        if i == len(costs):
            return 0
        if (i, a_count) in memo:
            return memo[(i, a_count)]
        b_count = i - a_count
        res = float('inf')
        if a_count < n:
            res = min(res, costs[i][0] + dfs(i+1, a_count+1))
        if b_count < n:
            res = min(res, costs[i][1] + dfs(i+1, a_count))
        memo[(i, a_count)] = res
        return res
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    costs = [[10,20],[30,200],[400,50],[30,20]]
    print(twoCitySchedCost(costs))

Line Notes

n = len(costs) // 2Calculate half the number of people to know how many must go to each city

memo = {}Initialize memo dictionary to cache results of subproblems and avoid recomputation

def dfs(i, a_count):Define recursive function with current index and count of people sent to city A

if i == len(costs):Base case: all people assigned, cost is zero from here

if (i, a_count) in memo:Check if result for this state is already computed to save time

b_count = i - a_countCalculate how many people have been assigned to city B so far

res = float('inf')Initialize result to infinity to find minimum cost

if a_count < n:If city A quota not full, try assigning current person to city A

if b_count < n:If city B quota not full, try assigning current person to city B

memo[(i, a_count)] = resStore computed result in memo for future reference

return resReturn minimum cost for current state

import java.util.*;
public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2;
        Map<String, Integer> memo = new HashMap<>();
        return dfs(costs, 0, 0, n, memo);
    }
    private int dfs(int[][] costs, int i, int aCount, int n, Map<String, Integer> memo) {
        if (i == costs.length) return 0;
        String key = i + "," + aCount;
        if (memo.containsKey(key)) return memo.get(key);
        int bCount = i - aCount;
        int res = Integer.MAX_VALUE;
        if (aCount < n) {
            res = Math.min(res, costs[i][0] + dfs(costs, i + 1, aCount + 1, n, memo));
        }
        if (bCount < n) {
            res = Math.min(res, costs[i][1] + dfs(costs, i + 1, aCount, n, memo));
        }
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] costs = {{10,20},{30,200},{400,50},{30,20}};
        System.out.println(sol.twoCitySchedCost(costs));
    }
}

Line Notes

int n = costs.length / 2;Calculate half the number of people for city quotas

Map<String, Integer> memo = new HashMap<>();Use memoization to cache results of subproblems

return dfs(costs, 0, 0, n, memo);Start recursion from first person with zero assigned to city A

if (i == costs.length) return 0;Base case: all people assigned, no additional cost

String key = i + "," + aCount;Create unique key for memoization based on current state

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

int bCount = i - aCount;Calculate how many people assigned to city B so far

int res = Integer.MAX_VALUE;Initialize result to max value to find minimum cost

if (aCount < n)Only assign to city A if quota not full

if (bCount < n)Only assign to city B if quota not full

memo.put(key, res);Store computed result in memo

return res;Return minimum cost for current state

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

class Solution {
    unordered_map<string, int> memo;
    int n;
    int dfs(const vector<vector<int>>& costs, int i, int aCount) {
        if (i == costs.size()) return 0;
        string key = to_string(i) + "," + to_string(aCount);
        if (memo.count(key)) return memo[key];
        int bCount = i - aCount;
        int res = INT_MAX;
        if (aCount < n) {
            res = min(res, costs[i][0] + dfs(costs, i + 1, aCount + 1));
        }
        if (bCount < n) {
            res = min(res, costs[i][1] + dfs(costs, i + 1, aCount));
        }
        memo[key] = res;
        return res;
    }
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        n = costs.size() / 2;
        return dfs(costs, 0, 0);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> costs = {{10,20},{30,200},{400,50},{30,20}};
    cout << sol.twoCitySchedCost(costs) << endl;
    return 0;
}

Line Notes

int n;Store half the number of people as class member for quota checks

unordered_map<string, int> memo;Memoize subproblem results to avoid recomputation

int dfs(const vector<vector<int>>& costs, int i, int aCount)Recursive function with current index and city A count

if (i == costs.size()) return 0;Base case: all people assigned, no cost left

string key = to_string(i) + "," + to_string(aCount);Create unique key for memoization

if (memo.count(key)) return memo[key];Return cached result if available

int bCount = i - aCount;Calculate how many assigned to city B

int res = INT_MAX;Initialize result to max int to find minimum

if (aCount < n)Assign to city A only if quota allows

if (bCount < n)Assign to city B only if quota allows

memo[key] = res;Store computed result

return res;Return minimum cost

var twoCitySchedCost = function(costs) {
    const n = costs.length / 2;
    const memo = new Map();
    function dfs(i, aCount) {
        if (i === costs.length) return 0;
        const key = i + ',' + aCount;
        if (memo.has(key)) return memo.get(key);
        const bCount = i - aCount;
        let res = Infinity;
        if (aCount < n) {
            res = Math.min(res, costs[i][0] + dfs(i + 1, aCount + 1));
        }
        if (bCount < n) {
            res = Math.min(res, costs[i][1] + dfs(i + 1, aCount));
        }
        memo.set(key, res);
        return res;
    }
    return dfs(0, 0);
};

// Example usage
console.log(twoCitySchedCost([[10,20],[30,200],[400,50],[30,20]]));

Line Notes

const n = costs.length / 2;Calculate half the number of people for city quotas

const memo = new Map();Memoize results of recursive calls to optimize

function dfs(i, aCount)Recursive function with current index and city A count

if (i === costs.length) return 0;Base case: all people assigned, no cost left

const key = i + ',' + aCount;Create unique key for memoization

if (memo.has(key)) return memo.get(key);Return cached result if available

const bCount = i - aCount;Calculate how many assigned to city B

let res = Infinity;Initialize result to infinity to find minimum

if (aCount < n)Assign to city A only if quota not exceeded

if (bCount < n)Assign to city B only if quota not exceeded

memo.set(key, res);Store computed result

return res;Return minimum cost

⏱

Complexity

TimeO(2^(2n)) without memoization, reduced to O(n^2) states with memoization

SpaceO(n^2) due to memoization storage

Each person has two choices, leading to 2^(2n) possibilities. Memoization reduces the number of unique states to O(n^2) because the state is defined by index and count of city A assignments. However, this is still exponential in input size and impractical for large n.

💡 For n=10, this means about 2^20 calls without memoization, which is huge; memoization helps but still too slow for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but is essential to understand the problem's complexity and motivate greedy solutions.

🧠

Greedy Approach Using Sorting by Cost Difference

💡 This approach sorts people by how much cheaper it is to send them to city A versus city B, then assigns the first half to city A and the rest to city B, ensuring minimum total cost.

Intuition

People who are much cheaper to send to city A should go there, and those cheaper for city B should go there. Sorting by cost difference helps decide this efficiently.

Algorithm

1. Calculate the difference between cost to city A and city B for each person.
2. Sort people by this difference in ascending order.
3. Send the first n people to city A and the remaining n people to city B.
4. Sum the costs accordingly and return the total.

💡 Sorting by cost difference ensures that the people who benefit most from city A assignment go there, and vice versa, balancing the quotas.

</>

Code

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: x[0] - x[1])
    n = len(costs) // 2
    total = 0
    for i in range(n):
        total += costs[i][0]  # Send first n to city A
    for i in range(n, 2*n):
        total += costs[i][1]  # Send rest to city B
    return total

# Example usage
if __name__ == '__main__':
    costs = [[10,20],[30,200],[400,50],[30,20]]
    print(twoCitySchedCost(costs))

Line Notes

costs.sort(key=lambda x: x[0] - x[1])Sort by cost difference to prioritize cheaper city A assignments

n = len(costs) // 2Calculate half the number of people for city quotas

total = 0Initialize total cost accumulator

for i in range(n):Assign first half to city A based on sorted order

total += costs[i][0] # Send first n to city AAdd cost of sending person i to city A

for i in range(n, 2*n):Assign second half to city B

total += costs[i][1] # Send rest to city BAdd cost of sending person i to city B

return totalReturn the minimum total cost

import java.util.*;
public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
        int n = costs.length / 2;
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += costs[i][0];
        }
        for (int i = n; i < 2 * n; i++) {
            total += costs[i][1];
        }
        return total;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] costs = {{10,20},{30,200},{400,50},{30,20}};
        System.out.println(sol.twoCitySchedCost(costs));
    }
}

Line Notes

Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));Sort by cost difference to prioritize city A cheaper assignments

int n = costs.length / 2;Calculate half the number of people for city quotas

int total = 0;Initialize total cost accumulator

for (int i = 0; i < n; i++)Assign first half to city A

total += costs[i][0];Add cost of sending person i to city A

for (int i = n; i < 2 * n; i++)Assign second half to city B

total += costs[i][1];Add cost of sending person i to city B

return total;Return the minimum total cost

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

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
            return (a[0] - a[1]) < (b[0] - b[1]);
        });
        int n = costs.size() / 2;
        int total = 0;
        for (int i = 0; i < n; ++i) {
            total += costs[i][0];
        }
        for (int i = n; i < 2 * n; ++i) {
            total += costs[i][1];
        }
        return total;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> costs = {{10,20},{30,200},{400,50},{30,20}};
    cout << sol.twoCitySchedCost(costs) << endl;
    return 0;
}

Line Notes

sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b)Sort by cost difference to prioritize city A cheaper assignments

int n = costs.size() / 2;Calculate half the number of people for city quotas

int total = 0;Initialize total cost accumulator

for (int i = 0; i < n; ++i)Assign first half to city A

total += costs[i][0];Add cost of sending person i to city A

for (int i = n; i < 2 * n; ++i)Assign second half to city B

total += costs[i][1];Add cost of sending person i to city B

return total;Return the minimum total cost

var twoCitySchedCost = function(costs) {
    costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
    const n = costs.length / 2;
    let total = 0;
    for (let i = 0; i < n; i++) {
        total += costs[i][0];
    }
    for (let i = n; i < 2 * n; i++) {
        total += costs[i][1];
    }
    return total;
};

// Example usage
console.log(twoCitySchedCost([[10,20],[30,200],[400,50],[30,20]]));

Line Notes

costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));Sort by cost difference to prioritize city A cheaper assignments

const n = costs.length / 2;Calculate half the number of people for city quotas

let total = 0;Initialize total cost accumulator

for (let i = 0; i < n; i++)Assign first half to city A

total += costs[i][0];Add cost of sending person i to city A

for (let i = n; i < 2 * n; i++)Assign second half to city B

total += costs[i][1];Add cost of sending person i to city B

return total;Return the minimum total cost

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting costs O(n log n), then a single pass sums costs. No extra space besides sorting overhead.

💡 For n=10^5, sorting is efficient and practical, making this approach scalable.

Interview Verdict: Accepted / Optimal for interviews

This is the standard optimal solution and should be coded in interviews unless otherwise specified.

🧠

Greedy Approach with Inline Assignment and Single Loop

💡 This approach is a slight variation of the previous greedy method, combining sorting and assignment in a single loop for concise implementation.

Intuition

After sorting by cost difference, assign people to city A or B in one pass, accumulating cost without separate loops.

Algorithm

1. Sort people by cost difference (cost to A minus cost to B).
2. Initialize total cost to zero.
3. Iterate over all people; assign first n to city A and rest to city B while summing costs.
4. Return the total cost.

💡 Combining assignment and summation in one loop reduces code verbosity and potential off-by-one errors.

</>

Code

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: 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

# Example usage
if __name__ == '__main__':
    costs = [[10,20],[30,200],[400,50],[30,20]]
    print(twoCitySchedCost(costs))

Line Notes

costs.sort(key=lambda x: x[0] - x[1])Sort by cost difference to prioritize city A cheaper assignments

n = len(costs) // 2Calculate half the number of people for city quotas

total = 0Initialize total cost accumulator

for i, cost in enumerate(costs):Iterate over all people with index for assignment

if i < n:Assign first half to city A

total += cost[0]Add cost of sending person to city A

else:Assign remaining people to city B

total += cost[1]Add cost of sending person to city B

return totalReturn the minimum total cost

import java.util.*;
public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
        int n = costs.length / 2;
        int total = 0;
        for (int i = 0; i < costs.length; i++) {
            if (i < n) total += costs[i][0];
            else total += costs[i][1];
        }
        return total;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] costs = {{10,20},{30,200},{400,50},{30,20}};
        System.out.println(sol.twoCitySchedCost(costs));
    }
}

Line Notes

Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));Sort by cost difference to prioritize city A cheaper assignments

int n = costs.length / 2;Calculate half the number of people for city quotas

int total = 0;Initialize total cost accumulator

for (int i = 0; i < costs.length; i++)Iterate over all people for assignment

if (i < n) total += costs[i][0];Assign first half to city A

else total += costs[i][1];Assign remaining to city B

return total;Return the minimum total cost

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

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
            return (a[0] - a[1]) < (b[0] - b[1]);
        });
        int n = costs.size() / 2;
        int total = 0;
        for (int i = 0; i < costs.size(); ++i) {
            if (i < n) total += costs[i][0];
            else total += costs[i][1];
        }
        return total;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> costs = {{10,20},{30,200},{400,50},{30,20}};
    cout << sol.twoCitySchedCost(costs) << endl;
    return 0;
}

Line Notes

sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b)Sort by cost difference to prioritize city A cheaper assignments

int n = costs.size() / 2;Calculate half the number of people for city quotas

int total = 0;Initialize total cost accumulator

for (int i = 0; i < costs.size(); ++i)Iterate over all people for assignment

if (i < n) total += costs[i][0];Assign first half to city A

else total += costs[i][1];Assign remaining to city B

return total;Return the minimum total cost

var twoCitySchedCost = function(costs) {
    costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
    const n = costs.length / 2;
    let total = 0;
    costs.forEach((cost, i) => {
        if (i < n) total += cost[0];
        else total += cost[1];
    });
    return total;
};

// Example usage
console.log(twoCitySchedCost([[10,20],[30,200],[400,50],[30,20]]));

Line Notes

costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));Sort by cost difference to prioritize city A cheaper assignments

const n = costs.length / 2;Calculate half the number of people for city quotas

let total = 0;Initialize total cost accumulator

costs.forEach((cost, i) => {Iterate over all people with index for assignment

if (i < n) total += cost[0];Assign first half to city A

else total += cost[1];Assign remaining to city B

return total;Return the minimum total cost

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting dominates time complexity; assignment is linear. Space depends on sorting algorithm.

💡 This approach is as efficient as the previous but often preferred for cleaner code.

Interview Verdict: Accepted / Optimal and clean

This is a clean, optimal solution suitable for coding in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The greedy sorting approach is the best to code in interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(2n)) without memoization, reduced to O(n^2) states with memoization	O(n^2) due to memo	Yes (deep recursion)	Yes	Mention only - never code
2. Greedy Sorting + Two Loops	O(n log n)	O(1) or O(n)	No	N/A	Code this for optimal solution
3. Greedy Sorting + Single Loop	O(n log n)	O(1) or O(n)	No	N/A	Code this for clean, concise solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the greedy solution, and prepare to explain why brute force is inefficient and greedy works.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding of the problem's complexity.Step 3: Explain the greedy insight about cost differences and sorting.Step 4: Code the greedy solution carefully, explaining each step.Step 5: Test with sample inputs and edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to identify the greedy pattern, implement sorting-based logic correctly, and handle edge cases efficiently.

Common Follow-ups

• What if the number of people sent to each city is not equal? → Use a priority queue or dynamic programming.
• Can you solve this problem without sorting? → Sorting is key; without it, solution is inefficient.

💡 Follow-ups often test flexibility in constraints and understanding of why sorting is crucial.

🔍

Pattern Recognition

When to Use

1) You must assign items to two groups with equal size, 2) Costs differ per group, 3) Goal is to minimize total cost, 4) Sorting by cost difference is possible.

Signature Phrases

send exactly n people to city A and n people to city Bminimize total cost of sending people

NOT This Pattern When

Problems where assignments are not balanced or costs are uniform are different patterns.

Similar Problems

Assign Cookies - similar greedy assignment by sortingCampus Bikes - assignment with cost minimizationMinimum Cost to Hire K Workers - cost-based selection

Practice

1. You have two arrays representing the top and bottom halves of dominoes. You want to make all values in one row uniform by rotating some dominoes. Which algorithmic approach guarantees an optimal solution with minimal rotations?

easy

A. Dynamic Programming that tries all possible uniform values and stores intermediate results

B. Greedy approach checking only the two candidate values from the first domino

C. Backtracking to try all rotation combinations exhaustively

D. Sorting both arrays and then matching values to minimize rotations

Solution

1. Step 1: Identify candidate values from the first domino

   The only possible uniform values are the top or bottom value of the first domino, since all dominoes must match one of these.

2. Step 2: Check feasibility and count rotations

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

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Checking only two candidates reduces complexity and guarantees correctness [OK]

Hint: Only two candidates from first domino suffice [OK]

Common Mistakes:

• Trying all numbers 1-6 unnecessarily
• Using DP or backtracking wasting time

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. Consider the following Python function implementing the optimal wiggle subsequence algorithm. What is the value of count after the loop finishes when the input is [1, 5, 4]?

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
            count += 1
            last_diff = diff
    return count

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace loop iterations

   Input: [1, 5, 4] - i=1: diff=5-1=4 >0 and last_diff=0 ≤0 -> count=2, last_diff=4 - i=2: diff=4-5=-1 <0 and last_diff=4 ≥0 -> count=3, last_diff=-1

2. Step 2: Final count value

   After loop, count=3, which is the length of the longest wiggle subsequence.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Count increments twice for valid wiggles [OK]

Hint: Count increments on sign change of diff from last_diff

Common Mistakes:

• Off-by-one counting
• Ignoring initial count=1
• Not updating last_diff correctly

4. Consider the following buggy code for assigning cookies to children. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 5: Missing increment of j when cookie is assigned

B. Line 3: Incorrect loop condition including count < len(g)

C. Line 1: Missing sorting of g and s arrays

D. Line 7: Incrementing j only in else block

Solution

1. Step 1: Identify missing pointer increment

   When a cookie satisfies a child (s[j] ≥ g[i]), j should increment to avoid reusing the same cookie.

2. Step 2: Check code lines

   Line 5 increments count and i but does not increment j, causing the same cookie to be assigned multiple times.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without j increment on assignment, cookie reuse occurs [OK]

Hint: Check pointer increments on both branches [OK]

Common Mistakes:

• Forgetting to sort arrays
• Incorrect loop conditions
• Not incrementing both pointers on assignment

5. What is the time complexity of the optimal greedy solution for the Jump Game problem, and why is the following common misconception incorrect? Misconception: The time complexity is O(n^2) because for each index, you might check all reachable next indices.

medium

A. O(n) because the algorithm iterates through the array once, updating max reachable index

B. O(n log n) due to sorting or binary search involved in jump calculations

C. O(n^2) because each index can jump to multiple next indices

D. O(n) but with O(n) auxiliary space for memoization

Solution

1. Step 1: Identify the algorithm's iteration pattern

   The greedy solution iterates through the array once, updating a single variable maxReach without nested loops.

2. Step 2: Explain why O(n^2) is incorrect

   Unlike brute force, it does not explore all jumps explicitly; it only tracks the furthest reachable index, so no nested iteration occurs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass through array -> O(n) time, no nested loops [OK]

Hint: Greedy uses one pass, no nested loops [OK]

Common Mistakes:

• Confusing brute force with greedy complexity
• Assuming nested loops due to jumps