transcript of array pair talk - April 29, 2017

Transcript_ArrayPair.cs

using System;

class Solution
{
  // linear scan -> O(n)
  // space contain O(n) 
  // if the number is used twice - array -> 
    static int[,] FindPairsInTheArrayWithGivenDifference(int[] arr, int k)
    {
      // your code goes here   a, b => "a"+"b", tuple<int,int>
      IList<int[]> pairsFound = new List<int[]>(); 
      if(arr == null || arr.Length == 0) pairsFound; 
      
      var cache = new HashSet<int>(); 
      int length = arr.Length; 
      for(int i = 0; i < length ; i++)
      {
        var current = arr[i]; 
        var search1 = current + k; // add to cache 
        var search2 = current - k; 
        // 1 , 3, 4 k = 1
        // visit 1 , cache is empty , 1 + 1 = 2, 1-1 = 0, put cache{0,2}
        // visit 3, 3 is not in cache, 3+1, 3-1=>4, 2 , put cache{0,2,4}
        // visit 4, 4 is in the cache, now you need to add one or two pairs into output
        // but peer maybe 3 or3, you do not save the information -> catch up design to fix the issue
        // hashset -> Dictionary -> key is still number look for, but value is a list to your original value
        // 3 -> key = 4, value 3, 
        // 
        // 100, visit 100, k = 2, then 102, 98 in the cache
        //  102, or 
        if(cache.Contains(search1) || cache.Contains(search2) )
        {
           // have found one or two pairs number, 
          if(cache.Contains(search1))
           pairsFound.Add(new int[]{current, search1}); // bug, do not +k or -k 
          
          if(cache.Contains(search2))
            pairsFound.Add(new int[]{current, search1});
        }
        else 
        {
          cache.Add(current); 
          //cache.Add(search2); 
        }
        
        return pairsFound;       
      }
    }

    static void Main(string[] args)
    {

    }
}
// distinct integer
//  1  2 3 4 5 -> 
// k - nonngetaive 1, 
// pair with give difference 1, how many pair -> n* (n-1), 
// choose two nodes from each, n, select n-1  -> 0(n*n)
// test case ascending order, for each number 1, check its right, 
// gap of array 1000000, k = 2, binary search -> expedite O(logn)
// time complexity O(nlogn) find pair -> based on sort O(nlogn)
// distince, x- y = k, 
// 1, k = 1, only number is 2, 
// 1000, k = 5, two choice 998, or 1002
// build a hashtable extra space -> meet 1000, save hashset add 998 and 10002 in hashset, 
// go over find 998, I find a pair -> O(n) -> extra space performance -> O(n)
// My solution, no binary search, one linear scan of the array, first you check if your pair is in hashset, if it is, then add 1 pair, 
// if it is not, add  a[i] +- k > 0, add at most 2 elements in the hashset 
// continue -> negative 
//  k = 1, nonnegative,   -1, its pair value should 0 or -2,