Is there any efficient way to get longest possible sorted array from alternate elements of two arrays?

Question

For Example: N=5, M=4

A=[4,2,10,5,9]

B=[4,5,6,15]

so the one of longest sorted array is [2,4,5,6,9,15]

this is my Approach but want to know is there any efficient approach available. I can assure it is not from any online coding contest, it is being asked to me in an interview so I want to know the efficient approach if any.

#include<bits/stdc++.h> 
using namespace std; 
int mx=0;
void generateUtil(int A[], int B[], int C[], int i, int j, int m, int n, 
                int len, bool flag) 
{ 
    if (flag) 
    { 
        if (len) 
            mx=max(mx,len+1); 
        for (int k = i; k < m; k++) 
        { 
            if (!len) 
            { 
                C[len] = A[k];
                generateUtil(A, B, C, k+1, j, m, n, len, !flag); 
            } 
            { 
                if (A[k] > C[len]) 
                { 
                    C[len+1] = A[k]; 
                    generateUtil(A, B, C, k+1, j, m, n, len+1, !flag); 
                } 
            } 
        } 
    } 
    { 
        for (int l = j; l < n; l++) 
        { 
            if (B[l] > C[len]) 
            { 
                C[len+1] = B[l]; 
                generateUtil(A, B, C, i, l+1, m, n, len+1, !flag); 
            } 
        } 
    } 
} 
void generate(int A[], int B[], int m, int n) 
{ 
    int C[m+n];
    generateUtil(A, B, C, 0, 0, m, n, 0, true); 
} 
int main() 
{ 
    int n,m,i,j;
    cin>>n>>m;
    int A[n],B[m];
    for(i=0;i<n;i++)
    {
     cin>>A[i];
    }
    for(j=0;j<n;j++)
    {
     cin>>B[j];
    }
    generate(A, B, n, m); 
    cout<<mx<<"\n";
    return 0; 
}

Do you need strict ordering? For example, is `[4 4 ...]` accepted? — Damien, Mar 09 '21 at 19:47
Can you please explain more thoroughly what exactly the output of this algorithm should be? How do 2, 5, and 15 end up in the solution? — AVH, Mar 09 '21 at 19:49
Please read: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice — AVH, Mar 09 '21 at 19:51
I think the easiest way is to add all the items into a set and then print the contents of the set. This works because a set doesn't allow duplicates and it automatically sorts it's contents. — Jerry Jeremiah, Mar 09 '21 at 20:37
@AVH The way I read it, all the numbers from both arrays are used to make an array of sorted unique values. — Jerry Jeremiah, Mar 09 '21 at 20:39
I think the problem need more clarification. Because, when it says `"from alternate elements of two arrays"`, it means that, `the first element should be taken from A then from B then from A and so on in increasing order till the arrays exhausted`. — biqarboy, Mar 09 '21 at 21:07
@JerryJeremiah I thought that as well, but that doesn't match with the solution shown in the question. — AVH, Mar 09 '21 at 21:20
@biqarboy I don't think that's quite it either. Because that means you take either A[0] or B[0], then B[1] or A[1], etc. So how can 2, 5, and 15 be part of the solution then? — AVH, Mar 09 '21 at 21:22
@AVH I see what you mean. The wording of the question needs to be changed so that the expected outcome is possible. — Jerry Jeremiah, Mar 09 '21 at 22:00
@AVH I agree with you as well. I think @Anonymous actually trying to [run code form geeksforgeeks](https://www.geeksforgeeks.org/generate-all-possible-sorted-arrays-from-alternate-elements-of-two-given-arrays/) for the wrong problem, as this solution is trying to solve `Generate all possible sorted arrays from alternate elements of two given sorted arrays`. The given sample of this problem indicate the input array is not sorted at all! — biqarboy, Mar 09 '21 at 23:45
@biqarboy Ah, so "I can assure it is not from any online coding contest" then... — AVH, Mar 10 '21 at 00:02
@AVH even the provided code does not work at all. First, while taking input for `array-B`, the loop should be running for `m` times instead of `n`. Second, he simply remove the **else** part of the `if (flag)` from `generateUtil` function. Third, by default the code do not print the longest sorted array ... just printing the length of the longest sorted array is not enough to reproduce the output. Anyway, enough effort given for this one ... I quit! — biqarboy, Mar 10 '21 at 00:13
@biqarboy - I tried running the provided code. I get [9,15,15,15,15,15,0,0,0,6] as the output. Anyway, maybe he got enough to get through the interview! — QuatCoder, Mar 10 '21 at 01:06
@QuatCoder Ahh! That means `the provided code does not work at all`! When you give some sample input/output and a code that needs to improve, it supposed to generate the output properly without any guess/change. How you get `[9,15,15,15,15,15,0,0,0,6] as the output`? You should not! Because, when I run it I got the output as `6` meaning the length of the `longest possible sorted array from alternate elements of two arrays` is `6`. You print an output with 10 elements! The total size of the input array (i.e., `(N + M)`) is `9`! — biqarboy, Mar 10 '21 at 01:20
To get that result I added stream output of the local C array in the 'generate' function, after the call to 'generateUtil'. I assumed that is where the result was put. Last number is the 6 you get ;) — QuatCoder, Mar 10 '21 at 01:42

AVH · Answer 1 · 2021-03-09T19:47:10.540

1

Depends on what you mean by efficient. This is pretty efficient if we're measuring e.g. code length, ease of understanding, and chance of bugs:

#include <algorithm>
#include <iterator>
#include <set>

std::set<int> result;
std::copy(std::begin(A), std::end(A), std::inserter(result, result.end()));
std::copy(std::begin(B), std::end(B), std::inserter(result, result.end()));

for (int e : result) { std::cout << e << ' '; }

Also: Why should I not #include <bits/stdc++.h>?.

Edit: It seems this doesn't actually do what is asked. Although at this point I have no clue what is being asked.

edited Mar 09 '21 at 19:47

answered Mar 09 '21 at 18:54

AVH

11,349
4
34
43

Efficient in terms of time & space complexity as my code is looking for all combinations this will create either TLE or MLE for higher constraints. – Anonymous Mar 09 '21 at 18:58
@Anonymous I'm sorry but I have no clue what TLE and MRE are. Also note that time and space efficiency are often opposites, so which one is most important? – AVH Mar 09 '21 at 19:41
@Anonymous Actually, my code probably does not do what you want it to do. I'll update my answer and add some comment to your original question. – AVH Mar 09 '21 at 19:46
@AVH I think @Anonymous wants to indicate `Time Limit Exceed` and `Memory Limit Exceed`; meaning the program do not able to run within a time and memory constraint respectively. If time and space is a concern, @Anonymous should put a limit for those constraints (time and space) in the problem statement. – biqarboy Mar 09 '21 at 23:33
This gives the same result as my code below [2 4 5 6 9 10 15] on the input data given. Overall I like this code better than mine. So, happy to upvote this as the best answer – QuatCoder Mar 10 '21 at 01:59

score 1 · Answer 2 · answered Mar 09 '21 at 20:44

1

The following uses the standard algorithms library. As to whether that is what your employer wants is an open question!

#include <algorithm>
#include <iostream>
#include <iterator>

int main()
{
    int A[] = {4,2,10,5,9};
    int B[] = {4,5,6,15};

    std::sort(std::begin(A), std::end(A));
    std::sort(std::begin(B), std::end(B));

    int C [std::size(A) + std::size(B)];
    std::merge(std::begin(A), std::end(A),std::begin(B), std::end(B),C);

    // std::unique will return one after last valid element
    auto iter = std::unique(std::begin(C), std::end(C));
    for ( auto p = std::begin(C); p != iter; ++p){
       std::cout << *p << ",\n";
    }
}

answered Mar 09 '21 at 20:44

QuatCoder

232
1
5

1

If you sort `A` and `B`, then you will break the order. I think the problem requires to keep the original order of the data. – biqarboy Mar 09 '21 at 20:59
Note that this is not valid C++ (neither is the code in the question for that matter). You can't create an array on the stack dynamically (i.e. a variable length array). – AVH Mar 09 '21 at 21:23
@AVH This is valid C++ as far as I know. The number of elements of A and B is known at compile time. [std::size is a constexpr function](https://en.cppreference.com/w/cpp/iterator/size), so the computation of number of elements of C is also a compile time computation. In fact the definition of C would not be allowed if that was not the case. – QuatCoder Mar 09 '21 at 22:50
@biqarboy Title says "Is there any efficient way to get longest possible ***sorted array*** from alternate elements of two arrays". Can't be much clearer than that. – QuatCoder Mar 09 '21 at 22:52
@QuatCoder Ah, good point about the sizes of A & B being constexpr in your code. I glossed over that, my mistake! – AVH Mar 09 '21 at 22:58
@QuatCoder Even if my assumption was wrong, your program gives wrong output: `[2,4,5,6,9,10,15]` instead of `[2,4,5,6,9,15]`. What about that? – biqarboy Mar 09 '21 at 23:38
@biqarboy I assumed that Anonymous had made a typo in his pseudocode, since I didn't see a reason that the 10 wasn't included in the sorted result, unless you can explain the reason 10 is missing from the result? – QuatCoder Mar 10 '21 at 00:49
@QuatCoder As you put `10` in the output, why not consider giving an explanation about why your output is different from the sample one? – biqarboy Mar 10 '21 at 01:26
@biqarboy. Output of my version is the same as that of AVH above on the supplied input data – QuatCoder Mar 10 '21 at 02:02

Is there any efficient way to get longest possible sorted array from alternate elements of two arrays?

2 Answers2