Problem Description

You are given a list of countries, each with a unique name, and a list of pairs indicating which countries are at war with each other. Your task is to determine which countries are "safe to invest in." A country is considered safe if it is not at war with any other country.

• countries: An array of strings, each string is a unique country name.
• wars: An array of pairs/lists, where each pair [a, b] means country a is at war with country b (and vice versa).

Your output should be a list of all country names that are not involved in any war, in any order.

Constraints:

• Each country name is unique.
• Each war pair contains two different countries from the list.
• There may be zero or more wars.
• Return all safe countries. The order does not matter.

Thought Process

The first step is to understand that a country is unsafe if it appears in any war pair. A brute-force approach would be to check, for each country, whether it appears in any pair in the wars list. However, this means for every country, we scan the entire wars list, which can be slow if both lists are large.

To optimize, we can precompute a set of all countries involved in wars. Then, for each country, we just check if it is in this set (which is a fast operation). This shift from repeated scanning to set-based lookup is the key optimization.

Solution Approach

Let's break down the steps to solve this efficiently:

1. Build a Set of Unsafe Countries:
   • For each pair [a, b] in wars, add both a and b to a set called unsafe.
   • This set will contain all countries involved in any conflict.
2. Find Safe Countries:
   • Iterate through the countries list.
   • If a country is not in the unsafe set, add it to the result list.
3. Return the Result:
   • Return the list of safe countries. The order does not matter.

We use a set for unsafe because checking membership in a set is O(1), making our solution efficient even for large input sizes.

Example Walkthrough

Input:

• countries = ["USA", "Canada", "Mexico", "Brazil"]
• wars = [["USA", "Canada"], ["Mexico", "Brazil"]]

Step 1: Build Unsafe Set
After processing each war pair:

• ["USA", "Canada"] → unsafe = {"USA", "Canada"}
• ["Mexico", "Brazil"] → unsafe = {"USA", "Canada", "Mexico", "Brazil"}

Step 2: Find Safe Countries
We check each country:

• "USA" is in unsafe set → skip
• "Canada" is in unsafe set → skip
• "Mexico" is in unsafe set → skip
• "Brazil" is in unsafe set → skip

Output: []

Another Example:

• countries = ["USA", "Canada", "Mexico", "Brazil"]
• wars = [["USA", "Canada"]]

• unsafe = {"USA", "Canada"}
• Safe countries: "Mexico", "Brazil"

Code Implementation

def safeCountries(countries, wars):
    unsafe = set()
    for a, b in wars:
        unsafe.add(a)
        unsafe.add(b)
    return [country for country in countries if country not in unsafe]
      

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

vector<string> safeCountries(vector<string>& countries, vector<vector<string>>& wars) {
    unordered_set<string> unsafe;
    for (const auto& pair : wars) {
        unsafe.insert(pair[0]);
        unsafe.insert(pair[1]);
    }
    vector<string> res;
    for (const string& country : countries) {
        if (unsafe.find(country) == unsafe.end()) {
            res.push_back(country);
        }
    }
    return res;
}
      

import java.util.*;

public class Solution {
    public List<String> safeCountries(List<String> countries, List<List<String>> wars) {
        Set<String> unsafe = new HashSet<>();
        for (List<String> pair : wars) {
            unsafe.add(pair.get(0));
            unsafe.add(pair.get(1));
        }
        List<String> res = new ArrayList<>();
        for (String country : countries) {
            if (!unsafe.contains(country)) {
                res.add(country);
            }
        }
        return res;
    }
}
      

function safeCountries(countries, wars) {
    const unsafe = new Set();
    for (const [a, b] of wars) {
        unsafe.add(a);
        unsafe.add(b);
    }
    return countries.filter(country => !unsafe.has(country));
}
      

Time and Space Complexity

Brute-force Approach:
For each country, scan all wars to see if it is involved. If there are n countries and m wars, this is O(n * m) time.

Optimized Approach (Using Set):

• Building the unsafe set takes O(m) time (since each war adds two entries).
• Checking each country for membership in unsafe is O(1) per country, so O(n) total.
• Total Time Complexity: O(n + m)
• Space Complexity: O(n + m) for storing the set and result list.

Summary

The main insight is to precompute all unsafe countries using a set, allowing us to quickly determine which countries are safe. This approach is efficient and simple, relying on fast set lookups. By avoiding repeated scans, we reduce the time complexity from O(n * m) to O(n + m), making the solution scalable and elegant.