What is the time complexity of Two City Scheduling?

The optimal solution has a time complexity of O(n log n).

What data structures are used to solve Two City Scheduling?

This problem uses Array, Greedy, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Two City Scheduling?

Insight 1: The key is to realize that we need to strategically choose which people to send to which city. Sorting the costs based on the difference between the cost of going to city A and city B is crucial. Insight 2: By sorting the costs based on `aCost - bCost`, we prioritize sending people to city A for whom the cost difference is significantly lower for city A than city B. After sending `n` people to city A, we send the remaining `n` to city B.

Which companies ask LeetCode 1029. Two City Scheduling in interviews?

This problem is frequently asked at Swiggy.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Two City Scheduling - LeetCode 1029 Solution

Two City Scheduling - Complete Solution Guide

Two City Scheduling is LeetCode problem 1029, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCost i , bCost i ] , the cost of flying the i th person to city a is aCost i , and the cost of flying the i th person to city b is bCost i . Return the minimum cost to fly every person to a city such that exactly n people arrive in each city. Example 1: Input: costs = [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A

Detailed Explanation

The problem asks us to find the minimum cost to send 2n people to two cities, A and B, such that exactly n people are sent to each city. We are given a `costs` array where `costs[i] = [aCost_i, bCost_i]` represents the cost of sending the i-th person to city A and city B, respectively. The goal is to minimize the total cost while ensuring an equal number of people are sent to each city.

Solution Approach

The solution uses a greedy approach. It sorts the `costs` array based on the difference between the cost of going to city A and the cost of going to city B (i.e., `aCost - bCost`). After sorting, the first 'n' people are assigned to city A, and the remaining 'n' people are assigned to city B. This approach minimizes the total cost because we are sending people with the biggest savings (in terms of A vs B cost) to city A first.

Step-by-Step Algorithm

Step 1: Sort the `costs` array in ascending order based on the difference between `aCost` and `bCost` (i.e., `aCost - bCost`).
Step 2: Initialize a variable `total_cost` to 0.
Step 3: Iterate through the first `n` elements of the sorted `costs` array and add the cost of going to city A (`aCost`) to `total_cost`. These people are assigned to city A.
Step 4: Iterate through the next `n` elements of the sorted `costs` array and add the cost of going to city B (`bCost`) to `total_cost`. These people are assigned to city B.
Step 5: Return the `total_cost`.

Key Insights

Insight 1: The key is to realize that we need to strategically choose which people to send to which city. Sorting the costs based on the difference between the cost of going to city A and city B is crucial.
Insight 2: By sorting the costs based on `aCost - bCost`, we prioritize sending people to city A for whom the cost difference is significantly lower for city A than city B. After sending `n` people to city A, we send the remaining `n` to city B.
Insight 3: This greedy approach works because it attempts to minimize the increase in cost by initially prioritizing assignments where the cost difference is most favorable.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(1)

Topics

This problem involves: Array, Greedy, Sorting.

Companies

Asked at: Swiggy.

Two City Scheduling | LeetCode 1029

Medium

Array Greedy Sorting

Time: O(n log n)Space: O(1)

Solution Code

Available in:

import java.util.Arrays;

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_cost = 0;
        
        for (int i = 0; i < n; i++) {
            total_cost += costs[i][0];
        }
        
        for (int i = n; i < 2 * n; i++) {
            total_cost += costs[i][1];
        }
        
        return total_cost;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1029: Two City Scheduling - Detailed explanation and solution approaches.

Topics

Array Greedy Sorting

Companies

Swiggy

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1029

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Sort the `costs` array in ascending order based on the difference between `aCost` and `bCost` (i.e., `aCost - bCost`).
2
Step 2: Initialize a variable `total_cost` to 0.
3
Step 3: Iterate through the first `n` elements of the sorted `costs` array and add the cost of going to city A (`aCost`) to `total_cost`. These people are assigned to city A.
4
Step 4: Iterate through the next `n` elements of the sorted `costs` array and add the cost of going to city B (`bCost`) to `total_cost`. These people are assigned to city B.
5
Step 5: Return the `total_cost`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log n)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is determined by the sorting algorithm used. Most standard sorting algorithms (e.g., merge sort, quicksort) have a time complexity of O(n log n). The space complexity is constant because we are not using any additional data structures that scale with the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Dynamic Programming

A dynamic programming approach could be used to solve this problem. Define dp[i][j] as the minimum cost to send the first 'i' people such that 'j' people are sent to city A. The recurrence relation would involve considering whether the i-th person is sent to city A or city B.

Time: O(n^2), where n is costs.length / 2Space: O(n^2)

Trade-offs: The dynamic programming approach has a higher time and space complexity compared to the greedy approach. It may be useful if more complex constraints were added, such as limitations on specific people being sent to specific cities, where the greedy approach may not produce optimal results. For the base problem as presented, the greedy solution is much preferred due to simplicity and performance.

✨

Key Insights

1Insight 1: The key is to realize that we need to strategically choose which people to send to which city. Sorting the costs based on the difference between the cost of going to city A and city B is crucial.
2Insight 2: By sorting the costs based on `aCost - bCost`, we prioritize sending people to city A for whom the cost difference is significantly lower for city A than city B. After sending `n` people to city A, we send the remaining `n` to city B.
3Insight 3: This greedy approach works because it attempts to minimize the increase in cost by initially prioritizing assignments where the cost difference is most favorable.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Greedy Algorithm

Making the best choice at each step without looking ahead.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty input (costs.length = 0). While not explicitly mentioned in the constraints, the code handles it gracefully because the loops won't execute, and 0 will be returned, which is the correct minimum cost.
Edge case 2: Very large cost values. The integer data type might overflow if the input costs are extremely large, leading to incorrect results. However, the constraints state that costs are between 1 and 1000, and n is at most 50 (costs.length <= 100), so the maximum possible total cost is 100 * 1000 = 100,000, which does not overflow.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not sorting the costs array. Without sorting based on the cost difference, the solution won't correctly prioritize sending people to the city where they have the lowest relative cost.

✗Common mistake 2: Incorrectly implementing the sorting logic. It's essential to sort based on `aCost - bCost` to accurately determine the optimal assignment of people to cities. Reversing the order or using an incorrect comparison metric can lead to a suboptimal solution.

✗Common mistake 3: Integer overflow. While less likely with current constraints, consider using larger datatypes (long) if constraints could change to allow very high costs for individual flights.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Resource allocation. The problem resembles allocating employees to different projects or tasks where each employee has different costs associated with each task, and you want to minimize the overall cost while meeting certain constraints on the number of employees assigned to each project.

🏦Real-world scenario 2: Scheduling and logistics. It can be applied to scheduling flights for employees to different locations for meetings or conferences, where the company needs to minimize travel expenses while ensuring a specific number of employees attend each event.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

What are common greedy problem patterns?

Activity selection (sort by end time), interval scheduling (sort by start/end), Huffman coding (always combine smallest), fractional knapsack (sort by value/weight ratio), and minimum spanning tree. Look for problems where local decisions don't affect future options.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Two City Scheduling"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether greedy techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?