title: How to know that a triangle triple exists in our array?
body: <p>I was stuck in solving the following interview practice question:<br>
  I have to write a function:</p>
  
  <pre><code>int triangle(int[] A);
  </code></pre>
  
  <p>that given a zero-indexed array A consisting of <code>N</code> integers returns <code>1</code> if there exists a triple (P, Q, R) such that <code>0 &lt; P &lt; Q &lt; R &lt; N</code>.</p>
  
  <pre><code>A[P] + A[Q] &gt; A[R],  
  A[Q] + A[R] &gt; A[P],  
  A[R] + A[P] &gt; A[Q].
  </code></pre>
  
  <p>The function should return <code>0</code> if such triple does not exist. Assume that <code>0 &lt; N &lt; 100,000</code>. Assume that each element of the array is an integer in range <code>[-1,000,000..1,000,000]</code>.</p>
  
  <p>For example, given array <code>A</code> such that</p>
  
  <pre><code>A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20
  </code></pre>
  
  <p>the function should return <code>1</code>, because the triple <code>(0, 2, 4)</code> fulfills all of the required conditions.</p>
  
  <p>For array <code>A</code> such that</p>
  
  <pre><code>A[0]=10, A[1]=50, A[2]=5, A[3]=1
  </code></pre>
  
  <p>the function should return <code>0</code>.</p>
  
  <p>If I do a triple loop, this would be very very slow (complexity: <code>O(n^3)</code>). I am thinking maybe to use to store an extra copy of the array and sort it, and use a binary search for a particular number. But I don't know how to break down this problem.<br>
  Any ideas?</p>