I got this question in an online Interview test. I wasn't able to get all the test cases passing. I'm looking for how it could have been solved.

We are given two arrays A and B, consisting of N integers each. We want to merge them into array C such that, for each index K (from 0 to N - 1), C[K] can be either A[K] or B[K]. For example, arrays A = [1, 2, 4, 3] and B = [1, 3, 2, 3] can be merged in any one of the the following ways:

[1,2,4,3] [1,3,4,3] [1,2,2,3] [1,3,2,3]

Our goal is to obtain C such that the smallest positive integer not present in C is as small as possible. In the arrangements in our example, this value would be 5, 2, 4 and 4 respectively. So, our solution is 2nd arrangement, which results in 2.

Some more Examples:

1. A = [1, 2, 4, 3] and B = [1, 3, 2, 3], Answer: 2
2. A = [3, 2, 1, 6, 5] and B = [4, 2, 1, 3, 3],Answer: 3as we can create C = [4, 2, 1, 6, 5]
3. A = [1, 2] and B = [1, 2], Answer: 3 as C = [1, 2] is only possible arangement.

Constraints:

• Input arrays size, 1 < N < 10^5
• 0 < A[i], B[i] <= 10^5
• Input arrays are of equal size.

My Approach:

I greedily compared the two arrays and pushed the larger of the two elements in the new vector named C. Then iterated over it to find the first missing positive element. I guess there is some flaw in the logic of pushing the max of two elements to the answer. Some hidden test cases failed.

Pseudocode:

input A,B
for i = 0 to N-1:
    C[i] = max(A[i], B[i])
sort(C)
h = 0
for i = 0 to N-1:
    if C[i] - h > 1:
        return h 1
    h = C[i]
return h 1

CodePudding user response：

From the second example, shouldn't it return 1? because we can form array C = [4, 3, 3, 6, 5] Maybe there is a condition I am missing?

UPDATE

Yes, sorry I misunderstood the process. So your approach seems right: comparing A[i] with B[i] and choosing the greater one and assigning it to C[i].

Now, to find the smallest number not in C, after you have made your C array, you need to find a way of finding all existing 'gaps' (by a gap, I mean an interval with two numbers x and y such that they differ by at least 2: such as [2,4] or [110, 290]. You need to find the gap that has the smallest value for x. And then, the answer would simply be x 1.

Also, you need to consider cases when there is no gap at all, like the third example.

For example, the pseudocode would look like:

// If there is at least one gap

// find all the gaps
C.sort() // sort C to ascending order
// iterate C to find the first gap. And this gap will surely have the smallest x.

ans = min_x   1;

// If there is no gap
if (min_element != 1) then ans = min_element - 1
else ans = max_element   1

CodePudding user response：

EDIT I deleted the code since it had the same problem as the one of Gaurav

@vish4071 made me realize, that my code has some problems / the same problems as the one from the author. However I think I found now the problem with the above code, I will demonstrade it with an example:

A = [1,2,3,3], B = [1,2,1,4]

With the code above we would get 5 as minimum element. However our smalles element in C should be 3. Why?? See:

C = [1,2,1,4]

What is the flaw in the logic of pushing the greater element to array C? Whenever we compare two numbers, we must check if the smaller one is already in our array C. If so -> we should add the smaller number, since it won't increase our minimum element. (Here idx 2 is the important one)

CodePudding user response：

Well, I'll start my answer by giving a counter-case to your approach. Let's say, the input is:

A = [3, 2, 1, 6, 5, 3] and B = [4, 2, 1, 3, 3, 3]

According to your approach, C would be created as: [4, 2, 1, 6, 5, 3], and hence, the answer will be 7

But a possible C could be: [3, 2, 1, 6, 5, 3], which results in the answer being 4. Notice that for C[0], we took the lower of A[0] and B[0].

I think this case should ring some bells. Here is my approach:

1. Since we have 0 < A[i], B[i] <= 10^5, create a helper array, say H of size 10^5 1 and initialize it to zeroes.
2. Now, iterate over A and B, looking for those values where A[i] == B[i], and for those values, set H[A[i]] = 1
3. Once again iterate over A and B. If H[A[i]] == 1 or H[B[i]] == 1, continue. Else, set H[max(A[i], B[i])] = 1.
4. Now, iterate over H from index 1 onwards. The index on which you find your 1st 0 is your answer.