MTCI_Sec4_GoogleInterview

using System;
using System.Collections.Generic;
using System.Linq;

class MainClass {

    
    static void Main() {
        // collection of numbers
        // find a  pair that is equal to a given sum
        //
        //ex [1,2,3,9] Sum = 8
        //ex [1,2,4,4] Sum = 8
        //
        // inputs:
        //  - collection of numbers
        //  - in memory
        //  - in order
        //  - can be repeating elements
        //  - all integers, including negatives
        // outputs: 
        //  - bool
        //
        
        // example inputs
        int[] input1 = new int[] { 1,2,3,9 };
        int input1Sum = 8;
        
        int[] input2 = new int[] { 1,2,4,4 };
        int input2Sum = 8;
        
        // Brute force solution
        // hasPairEqualingValBF(input1, input1Sum);
        // hasPairEqualingValBF(input2, input2Sum);
        
        // O(n) Dictionary solution
        // hasPairEqualingValDict(input1, input1Sum);
        // hasPairEqualingValDict(input2, input2Sum);
        
        // O(log n) solution
        hasPairEqualingValLog(input1, input1Sum);
        hasPairEqualingValLog(input2, input2Sum);
        
    }
    
    private static bool hasPairEqualingValBF(int[] inputs, int sumValue)
    {
        // error checking
        if (inputs.Length < 2) {
            Console.WriteLine("Error: inputs array must have at least 2 items.");
        }
        
        // O(n^2) solution
        for (int i = 0; i < inputs.Length; i++) {
            for (int j = 0; j < inputs.Length; j++) {
                if (j != i && ((inputs[i] + inputs[j]) == sumValue))
                {
                    // pair equaling the sum has been found
                    Console.WriteLine("Pair found: {0} + {1} = {2}", inputs[i], inputs[j], sumValue);
                    return true;
                }
            }
        }
        // a pair equaling the sum was not found
        Console.WriteLine("Pair not found.");
        return false;
    }
    
    private static bool hasPairEqualingValDict(int[] inputs, int sumValue)
    {
        // error checking
        if (inputs.Length < 2) {
            Console.WriteLine("Error: inputs array must have at least 2 items.");
        }
        
        //O(n) solution
        Dictionary<int, int> inputDict = inputs
            .Select((value, index) => new { value, index })
            .ToDictionary(pair => pair.index, pair => pair.value);
        int complement = 0; 
        
        for (int i = 0; i < inputs.Length; i++) {
            complement = sumValue - inputs[i];
            
            if (inputDict.Any(kvp => kvp.Value == complement && kvp.Key != i))
            {
                // pair equaling the sum has been found
                Console.WriteLine("Pair found"); 
                return true;
            }
        }
        
        Console.WriteLine("Pair not found."); 
        return false;
    }
    
    private static bool hasPairEqualingValLog(int[] inputs, int sumValue)
    {
        // error checking
        if (inputs.Length < 2) {
            Console.WriteLine("Error: inputs array must have at least 2 items.");
        }
        
        // O(log n) solution
        int left = 0;
        int right = inputs.Length - 1;
        
        while (right > left) {
            int currentSum = inputs[left] + inputs[right];
            if (currentSum == sumValue) {
                // pair equaling the sum has been found
                Console.WriteLine("Pair found"); 
                return true;
            }
            if (currentSum > sumValue)
                right--; // decrease right index
            if (currentSum < sumValue)
                left++; // increase left index
        }
        
        Console.WriteLine("Pair not found."); 
        return false;
    }
}