title: Smallest positive integer not in a specific combination of two unsorted arrays
body: <h2>Classic problem</h2>
  <blockquote>
  
  <p>Given an unsorted array <code>A</code> of integers, find the smallest positive integer which doesn't exist in <code>A</code>.</p>
  <p>[3, 2, 1, 6, 5] -&gt; 4<br />
  [2, 3, 4, 5] -&gt; 1<br />
  [1, 2, 3, 4] -&gt; 5</p>
  </blockquote>
  <p>In this classic problem you are given just one array, and you can find a lot of solutions and resources about this problem, including <a href="https://stackoverflow.com/questions/1586858/find-the-smallest-integer-not-in-a-list">stack<strong>overflow</strong></a>, <a href="https://codereview.stackexchange.com/questions/179037/given-an-array-of-integers-return-the-smallest-positive-integer-not-in-it">Code Review@SE</a> and <a href="https://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/" rel="nofollow noreferrer">geeksforgeeks.org</a>.</p>
  <h2>Hard edition</h2>
  <p>In my problem you are given two arrays, <code>A</code> and <code>B</code>, both of length <code>N</code>. Construct an array <code>C</code> of length <code>N</code>, whose <em>smallest missing integer</em> is <strong>maximum</strong> possible. <code>C[i]</code> must be either <code>A[i]</code> or <code>B[i]</code>.</p>
  <p>A = [1, 2, 4, 3],<br />
  B = [1, 3, 2, 3] =-&gt;<br />
  C = [1, 2, 4, 3] answer = 5</p>
  <p>A = [4, 2, 1, 6, 5],<br />
  B = [3, 2, 1, 7, 7] =-&gt;<br />
  C = [3, 2, 1, 6, 5] answer = 4</p>
  <p>A = [2, 3],<br />
  B = [4, 5] =-&gt;<br />
  C = [2, 5] answer = 1</p>
  <p>How can we solve this problem with <code>O(N)</code> worst-case time and space complexity?</p>
  <p>Assume that:</p>
  <pre><code>1&lt;= N &lt;= 100,000
  1&lt;= A[i], B[i] &lt;= 100,000,000
  </code></pre>