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;
}
}
