title: The intersection of multiple sorted arrays
body: <p>From <a href="https://stackoverflow.com/questions/2400157/the-intersection-of-two-sorted-arrays">this</a>, we know the method to solve the intersection of two sorted arrays. So how to get the intersection of multiple sorted arrays?</p>
  
  <p>Based on the answers of two sorted arrays, we can apply it to multiple arrays. Here are the codes</p>
  
  <pre><code>vector&lt;int&gt; intersectionVector(vector&lt;vector&lt;int&gt; &gt; vectors){
      int vec_num = vectors.size();
  
      vector&lt;int&gt; vec_pos(vec_num);// hold the current position for every vector
      vector&lt;int&gt; inter_vec; // collection of intersection elements
  
      while (true){
          int max_val = INT_MIN;
          for (int index = 0; index &lt; vec_num; ++index){
              // reach the end of one array, return the intersection collection
              if (vec_pos[index] == vectors[index].size()){
                  return inter_vec;
              }
  
              max_val = max(max_val, vectors[index].at(vec_pos[index]));
          }
  
          bool bsame = true;
          for (int index = 0; index &lt; vec_num; ++index){
              while (vectors[index].at(vec_pos[index]) &lt; max_val){
                  vec_pos[index]++; // advance the position of vector, once less than max value
                  bsame = false;
              }
          }
  
          // find same element in all vectors
          if (bsame){
              inter_vec.push_back(vectors[0].at(vec_pos[0]));
  
              // advance the position of all vectors
              for (int index = 0; index &lt; vec_num; ++index){
                  vec_pos[index]++;
              }
          }
      }
  }
  </code></pre>
  
  <p><strong>Is any better approach to solve it?</strong></p>
  
  <p><strong>Update1</strong></p>
  
  <p>From those two topics <a href="https://stackoverflow.com/questions/497338/efficient-list-intersection-algorithm">1</a> and <a href="https://stackoverflow.com/questions/4642172/computing-set-intersection-in-linear-time">2</a>, it seem that <code>Hash set</code> is more efficient method to do that.</p>
  
  <p><strong>Update2</strong></p>
  
  <p>To improve the performance, maybe the <code>min-heap</code> can be used instead of <code>vec_pos</code> in my codes above. And the variable <code>max_val</code> holds the current max value of all vectors. So just compare the root value with <code>max_val</code>, if they are same, this element can be put into intersection list.</p>