title: Find two integers in a sorted array such that a - b = k
body: <p>Given an <strong>integer k</strong> and an <strong>sorted array A</strong> (can consist of both positive and negative numbers), output <strong>2 integers from A</strong> such that <code>a-b=k</code> in <code>O(n) time</code> and <code>O(1) space</code></p>
  
  <p><strong>O(n logn) Solution:</strong></p>
  
  <ol>
  <li>Traverse the array: <code>O(n)</code></li>
  <li>For element <code>a[i]</code>, find <code>a[i]+k</code> in the array using binary search :<code>O(log n)</code></li>
  </ol>
  
  <p>Total Time: <code>O(n logn)</code></p>
  
  <p><strong>O(n) Solution:</strong></p>
  
  <ol>
  <li>Store all elements of the array in a Hash Table: <code>O(n)</code></li>
  <li>For element a[i], check whether a[i]+k in the hash table : <code>O(1)</code></li>
  </ol>
  
  <p>Total Time: <code>O(n)</code></p>
  
  <p>Space: <code>O(n)</code></p>
  
  <p>But he wants an <code>O(n)</code> solution with <code>O(1)</code> extraspace. Anyone have any idea?</p>