Udemy: Master Coding Interview - Coding Problems - #52

using System;
using System.Collections.Generic;

// Given 2 arrays, create a function that lets a user know (true/false)
// whether these two arrays contain any common items

// For Example:
// const array1 = ['a', 'b', 'c', 'x'];
// const array1 = ['z', 'y', 'i'];
// should return false.
// ----------
// const array1 = ['a', 'b', 'c', 'x'];
// const array1 = ['z', 'y', 'x'];
// should return true.

// Naive approach: Loop through first list, then another inner loop through
// second list, comparing values. This is slow, O(n^2) due to nested loops.
// Next approach: Add elements to hash set? Sort lists?

class MainClass {
    static char[] array1 = {'a', 'b', 'c', 'x'};
    static char[] array2 = {'z', 'y', 'x'};
    static char[] array3 = {'z', 'y', 'i'};
    
    static void Main() {
        Console.WriteLine("Result = " + containsCommonItems2(array1, array2));
        
    }
    
    // O(a*b)
    static bool containsCommonItems(char[] array1, char[] array2) {
        for (int i = 0; i < array1.Length; i++) {
            for (int j = 0; j < array2.Length; j++) {
                if (array1[i] == array2[j]) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // O(a+b)
    static bool containsCommonItems2(char[] array1, char[] array2) {
        // Loop through first array and create object where 
        //  properties = items in array.
        HashSet<char> set = new HashSet<char>();
        for (int i = 0; i < array1.Length; i++) {
            set.Add(array1[i]);
        }
        // Loop through second array and check if item in second array 
        //  exists on created object.
        for (int j = 0; j < array2.Length; j++) {
            if (set.Contains(array2[j])) {
                return true;
            }
        }
        
        
        return false;
    }
}