1

This is an interview question, so the usual bounds apply.

One array has size n and n elements. Second array has size n+m and m elements. Both the arrays are sorted. The question is to move all n+m elements into the second array in a sorted order. O(N) is desired.

There's no mention of not being able to use extra space, but going by the question, it doesn't seem to allow for additional space.

We can simultaneously walk the two arrays (a la Merge Sort) and combine them, but that would need an extra array or extra complexity of moving existing elements down by 1 (which would mean O(N2)).

Update: Here's an example.

Array1: {2, 4, 6, 10}

Array2: {21, 23, 25, , , , }

Answer: {2, 4, 6, 10, 21, 23, 25}

Improve this question

3 Answers 3

Reset to default
4

Walk them in descending order. O(2N), not O(N^2).

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

@bdares - I actually thought of walking them in descending order, but that would still need pushing down the existing elements, won't it? Pushing existing elements down would in fact result in O(N^2).
No, you start with the empty end of the n+m array. No pushing down needed.
@user183037 I'm assuming they're sorted in ascending order, starting at index 0. If they're kind of jumbled up with random intervals between numbers, I've badly misunderstood the problem.
No, that would be O(2N) which becomes O(N). If you start at the end (in the empty part of the second array), you are working with usable space at all times. Draw it out on paper, and you will see where the space is.
@all - I've added an example, could you please see if walking from the back will help?
|
3

There's no mention of not being able to use extra space, but going by the question, it doesn't seem to allow for additional space.

You don't need any - you have n elements in one array and m elements in the other. You also have n+m space in the other. It can clearly accommodate the union of the two arrays.

As mentioned in other answers, all you need to is :

  1. Iterate over the two arrays, beginning from the end of each
  2. Compare the two current elements from the two arrays
  3. Write the larger of the two into the last position in the second array (the one with extra space)
  4. Move on the next element in the array you just wrote from and note that the next larger element will be written to a position one before the position you just wrote to, irrespective of whether it already contains an element or not
  5. If you run out of elements in the first array, you're done since the second array elements are already in their right place
  6. If, instead, you run out of elements in the second array, you simply copy all the elements from the first into the second, moving towards the head of the array.
/**
 * Assumes both array are sorted in ascending order
 * Array a has length n and contains n elements
 * Array b has length m+n and contains m elements
 * The merged, sorted array will be returned in b
 */

public void merge(int [] a, int [] b)
{
    //b is the one with m+n space
    int indexA = a.length - 1; //points to last element in a
    int indexB = b.length - a.length - 1; //points to last element in b
    int writeTo = b.length - 1; //points to last free position

    while(indexA > -1 && indexB > -1)
    {
        if(a[indexA] > b[indexB])
        {
            b[writeTo--] = a[indexA--]
        }
        else
        {
            b[writeTo--] = b[indexB--];
        }
    }

    //are there any elements left-over in a?
    //any elements left-over in b will already be in their right place
    while(indexA > -1)
    {
        b[writeTo--] = a[indexA--];
    }
}
Improve this answer

Comments

3

Walk the two arrays simultaneously, but from the back of the data rather than the start. Write the sorted data starting from the end of the larger array. You will never need to displace anything. Any data you overwrite will have already been written at its new location further down in the array... O(m+n)

Improve this answer

1 Comment

I've added an example - could you please see if walking from the back will help?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.