title: Dance Pair Algorithm(from a programming contest)
body: <p>The question was as follows:
  Input:</p>
  
  <p>3 10</p>
  
  <p>1 2 3</p>
  
  <p>12 11 101</p>
  
  <p>where 3(n) is number of boys and girls 10(k) is accepted height difference
  next 2 lines are heights of girls and boys respectively</p>
  
  <p>1 2 3 are height's of the 3 boys</p>
  
  <p>and 12 11 101 are heights of 3 girls</p>
  
  <p>now we have to find the maximum number of pair of  one girl and one boy
  such that their height difference is less than or equal to k.</p>
  
  <p>Given:</p>
  
  <pre><code>      K &gt;= 1 and less than 10^9,
  
        N &gt;=1 and less than 10^5,
  
        heights(both boy an girl)&gt;=1 and less than 10^9.
  </code></pre>
  
  <p>A girl cant dance with more than one boy and vice versa</p>
  
  <pre><code>import java.io.*;
  import java.util.*;
  import java.text.*;
  import java.math.*;
  import java.util.regex.*;
  
  public class Solution {
  
  public static void main(String[] args) {
      Map&lt;Integer,List&lt;Integer&gt;&gt; boyGirlsPair= new HashMap&lt;Integer,List&lt;Integer&gt;&gt;();
      Map&lt;Integer,List&lt;Integer&gt;&gt; girlBoysPair= new HashMap&lt;Integer,List&lt;Integer&gt;&gt;();
      int dancingPairsCount = 0;
      int count = 0;
      Scanner scan = new Scanner(System.in);
      int N = scan.nextInt();
      long K = scan.nextLong();
      long[] boysHeightList = new long[N];
      long[]  girlsHeightList = new long[N];
      scan.nextLine();
      while (count&lt;N) {
          boysHeightList[count]=scan.nextLong();
          count++;
      }
      scan.nextLine();
      count =0;
      while (count&lt;N) {
      girlsHeightList[count]=scan.nextLong();
      count++;
      }
      scan.close();
      for (Integer boysHeightListIter =0;boysHeightListIter&lt;N;boysHeightListIter++) {
          for (Integer girlsHeightListIter=0;girlsHeightListIter&lt;N;girlsHeightListIter++) {
              if (Math.abs(boysHeightList[boysHeightListIter] - girlsHeightList[girlsHeightListIter]) &lt;= K) {
                  if(boyGirlsPair.containsKey(boysHeightListIter))
                  {
                      List&lt;Integer&gt; pairValue = boyGirlsPair.get(boysHeightListIter);
                      pairValue.add(girlsHeightListIter);
                      boyGirlsPair.put(boysHeightListIter,pairValue);
                  }
                  else
                  {
                      List&lt;Integer&gt; pairValue = new ArrayList&lt;Integer&gt;();
                      pairValue.add(girlsHeightListIter);
                      boyGirlsPair.put(boysHeightListIter,pairValue); 
                  }
                  if(girlBoysPair.containsKey(girlsHeightListIter))
                  {
                      List&lt;Integer&gt; pairValue = girlBoysPair.get(girlsHeightListIter);
                      pairValue.add(boysHeightListIter);
                      girlBoysPair.put(girlsHeightListIter,pairValue);
                  }
                  else
                  {
                      List&lt;Integer&gt; pairValue = new ArrayList&lt;Integer&gt;();
                      pairValue.add(boysHeightListIter);
                      girlBoysPair.put(girlsHeightListIter,pairValue);
                  }   
              }
          }
      }
     if(girlBoysPair.size()&lt;=boyGirlsPair.size())
     {
         System.out.println(girlBoysPair.size());
     }
     else
     {
         System.out.println(boyGirlsPair.size());
     }
   }
  }
  </code></pre>
  
  <p>The basic algorithm i used is formed 2 hashMaps one with keys as boys and values are list of girls they can dance with and another hashmap with keys as girls and values are boys who they can dance with.The smallest of 2 hashmaps are the maximum pairs that can be formed.This passed this basic test case of the contest,but failed for all other cases.Want to know one case where my algorithm won't work and if possible other solutions to this problem.</p>