title: FInd position of latest smallest element in the array for all elements
body: <p>I want to calculate, for an array of integer elements, the position of the latest element which is smaller than that element(if possible) otherwise store -1 in this place.</p>
  
  <p>By latest element I mean that largest possible index smaller than current index.</p>
  
  <p>Eg.</p>
  
  <p>(based on 0 indexing)</p>
  
  <p>let <code>problem[5] = {4,7,1,3,8}</code></p>
  
  <p>then sol <code>array = {-1,0,-1,2,3}</code></p>
  
  <p>Now I was able to do this in O(n^2) time complexity.....but am unable to do this in less than this time complexity.
  So, can anyone please tell me how to do this in less than O(n^2) time complexity.</p>
  
  <p>My code for n^2 time complexity :</p>
  
  <pre><code>int n = 5;
  
  int ques[n] = {4, 7, 1, 3, 8};
  
  int sol[n] = { -1, -1, -1, -1, -1};
  
  for (int i = 1; i &lt; 5; i++) {
  
      int pos;
  
      for (int j = 0; j &lt; i; j++) {
  
          pos = -1;
  
          if (ques[j] &lt; ques[i]) {
  
              pos = j;
  
          }
  
      }
  
      sol[i] = pos;
  
  }
  
  for (int i = 0; i &lt; n; i++){
  
      cout &lt;&lt; sol[i] &lt;&lt; ' ';
  
  }
  </code></pre>