title: Flattening nested loops / decreasing complexity - complementary pairs counting algorithm
body: <p>I was recently trying to solve some task in Python and I have found the solution that seems to have the complexity of <em>O(n log n)</em>, but I believe it is very inefficient for some inputs (such as first parameter being <code>0</code> and <code>pairs</code> being very long list of zeros).</p>
  
  <p>It has also three levels of <code>for</code> loops. I believe it can be optimized, but at the moment I cannot optimize it more, I am probably just missing something obvious ;)</p>
  
  <p>So, basically, the problem is as follows:</p>
  
  <blockquote>
    <p>Given list of integers (<code>values</code>), the function needs to return the number of indexes' pairs that meet the following criteria:</p>
    
    <ul>
    <li>lets assume single index pair is a tuple like <code>(index1, index2)</code>,</li>
    <li>then <code>values[index1] == complementary_diff - values[index2]</code> is true,</li>
    </ul>
    
    <p><strong>Example</strong>:
    If given a list like <code>[1, 3, -4, 0, -3, 5]</code> as <code>values</code> and <code>1</code> as <code>complementary_diff</code>, the function should return <code>4</code> (which is the length of the following list of indexes' pairs: <code>[(0, 3), (2, 5), (3, 0), (5, 2)]</code>).</p>
  </blockquote>
  
  <p>This is what I have so far, it should work perfectly most of the time, but - as I said - in some cases it could run very slowly, despite the approximation of its complexity <em>O(n log n)</em> (it looks like pessimistic complexity is <em>O(n^2)</em>).</p>
  
  <pre class="lang-py prettyprint-override"><code>def complementary_pairs_number (complementary_diff, values):
      value_key = {} # dictionary storing indexes indexed by values
      for index, item in enumerate(values):
          try:
              value_key[item].append(index)
          except (KeyError,): # the item has not been found in value_key's keys
              value_key[item] = [index]
      key_pairs = set() # key pairs are unique by nature
      for pos_value in value_key: # iterate through keys of value_key dictionary
          sym_value = complementary_diff - pos_value
          if sym_value in value_key: # checks if the symmetric value has been found
              for i1 in value_key[pos_value]: # iterate through pos_values' indexes
                  for i2 in value_key[sym_value]: # as above, through sym_values
                      # add indexes' pairs or ignore if already added to the set
                      key_pairs.add((i1, i2))
                      key_pairs.add((i2, i1))
      return len(key_pairs)
  </code></pre>
  
  <p>For the given example it behaves like that:</p>
  
  <pre><code>&gt;&gt;&gt; complementary_pairs_number(1, [1, 3, -4, 0, -3, 5])
  4
  </code></pre>
  
  <p>If you see how the code could be "flattened" or "simplified", please let me know.</p>
  
  <p>I am not sure if just checking for <code>complementary_diff == 0</code> etc. is the best approach - if you think it is, please let me know.</p>
  
  <p><strong>EDIT:</strong> I have corrected the example (thanks, unutbu!).</p>