Udemy: Master Coding Interview - Coding Problems - #55

using System;
using System.Collections.Generic;


// Google interview question found at https://www.youtube.com/watch?v=XKu_SEDAykw

// Given a collection of numbers and a given sum, find a matching pair of numbers
//  that add to equal the sum.
// Example 1: [1,2,3,9], Sum=8
// Example 2: [1,2,4,4], Sum=8
// Initial assumption: values in arrays are sorted

// Naive approach: Loop through array, then an inner loop starting from next 
//  index, adding the two to check if equal to sum. This is slow, O(n^2) time
//  complexity.
// Better approach: Work from outside in. If sum is greater than target sum, 
//  decrement upper index (to get smaller sum). If sum is less than target sum,
//  increment lower index (to get greater sum). Stop before lower index equals
//  upper index. O(n)

// Updated assumption: values in arrays are not guaranteed to be sorted
// Naive approach: Add sort (eg, binary sort, O(n*log(n))) before main algorithm
// Better approach: Traverse array, storing complement (sum-x) for each value x
//  in a hashset. Check if value is in hashset before adding value. O(n)

class MainClass {
    static int[] array1 = {1, 2, 3, 9};
    static int[] array2 = {1, 2, 4, 4};
    static int[] array3 = {9, 1, 2, 3};
    static int[] array4 = {4, 1, 2, 4};
    
    static void Main() {
        Console.WriteLine("Sum in array1? " + DoTwoValuesAddToSum(array1, 8));
        Console.WriteLine("Sum in array2? " + DoTwoValuesAddToSum(array2, 8));
        Console.WriteLine("Sum in array3? " + DoTwoValuesAddToSum_Unsorted(array3, 8));
        Console.WriteLine("Sum in array4? " + DoTwoValuesAddToSum_Unsorted(array4, 8));
    }
    
    // O(n)
    static bool DoTwoValuesAddToSum(int[] array, int sum) {
        // Work from outside in. If sum is greater than target sum, 
        //  decrement upper index (to get smaller sum). If sum is less than target sum,
        //  increment lower index (to get greater sum). Stop before lower index equals
        //  upper index.
        int lo = 0;
        int hi = array.Length - 1;
        while (lo < hi) {
            int currentSum = array[lo] + array[hi];
            if (currentSum == sum) {
                return true;
            }
            if (currentSum < sum) {
                lo++;
            }
            if (currentSum > sum) {
                hi--;
            }
        }
        return false;
    }
    
    static bool DoTwoValuesAddToSum_Unsorted(int[] array, int sum) {
        // Better approach: Traverse array, storing complement (sum-x) for each value x
        //  in a hashset. Check if value is in hashset before adding value.
        HashSet<int> hash = new HashSet<int>();
        
        for (int i = 0; i < array.Length; i++) {
            if (hash.Contains(array[i])) {
                return true;
            }
            hash.Add(sum - array[i]);
        }
        return false;
    }
}