2

(This question is inspired by deque::insert() at index?, I was surprised that it wasn't covered in my algorithm lecture and that I also didn't find it mentioned in another question here and even not in Wikipedia :). I think it might be of general interest and I will answer it myself ...)

Dynamic arrays are datastructures that allow addition of elements at the end in amortized constant time O(1) (by doubling the size of the allocated memory each time it needs to grow, see Amortized time of dynamic array for a short analysis).

However, insertion of a single element in the middle of the array takes linear time O(n), since in the worst case (i.e. insertion at first position) all other elements needs to be shifted by one.

If I want to insert k elements at a specific index in the array, the naive approach of performit the insert operation k times would thus lead to a complexity of O(n*k) and, if k=O(n), to a quadratic complexity of O(n²).

If I know k in advance, the solution is quite easy: Expand the array if neccessary (possibly reallocating space), shift the elements starting at the insertion point by k and simply copy the new elements.

But there might be situations, where I do not know the number of elements I want to insert in advance: For example I might get the elements from a stream-like interface, so I only get a flag when the last element is read.

Is there a way to insert multiple (k) elements, where k is not known in advance, into a dynamic array at consecutive positions in linear time?

Community
  • 1
  • 1
MartinStettner
  • 28,719
  • 15
  • 79
  • 106

2 Answers2

3

In fact there is a way and it is quite simple:

  • First append all k elements at the end of the array. Since appending one element takes O(1) time, this will be done in O(k) time.
  • Second rotate the elements into place. If you want to insert the elements at position index. For this you need to rotate the subarray A[pos..n-1] by k positions to the right (or n-pos-k positions to the left, which is equivalent). Rotation can be done in linear time by use of a reverse operation as explained in Algorithm to rotate an array in linear time. Thus the time needed for rotation is O(n).

Therefore the total time for the algorithm is O(k)+O(n)=O(n+k). If the number of elements to be inserted is in the order of n (k=O(n)), you'll get O(n+n)=O(2n)=O(n) and thus linear time.

Community
  • 1
  • 1
MartinStettner
  • 28,719
  • 15
  • 79
  • 106
  • 1
    -1 for using rotate, just look at a standard implentation of this (for instance javas [`ArrayList.addAll(index, collection)`](http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html#addAll(int,%20java.util.Collection))). It (of course) uses the method described by aioobe. – dacwe Oct 24 '11 at 09:20
  • @dacwe That's not an argument: Microsofts STL uses the approach, I described (when you want to insert elements described by a ForwardIterator, i.e. when you don't know the number of elements to be inserted). It's in the nature of dynamic arrays that they might already have enough allocated space for the insertion, and memory allocation might be rather expensive operation (in terms of "real" time). I usually don't complain about downvoting, but in your case, I find it's unfair (it's not incorrect and I still find it useful ...) – MartinStettner Oct 24 '11 at 09:46
  • 2
    In your question you assumed the length of the inserted array to be `k`. It is *another question* (*and a quite good one* :)) if you do not know the length of the array to be inserted... – dacwe Oct 24 '11 at 10:40
3

You could simply allocate a new array of length k+n and insert the desired elements linearly.

newArr = new T[k + n];

for (int i = 0; i < k + n; i++)
    newArr[i] = i <= insertionIndex      ? oldArr[i]
              : i <= insertionIndex + k  ? toInsert[i - insertionIndex - 1]
              :                            oldArr[i - k];

return newArr;

Each iteration takes constant time, and it runs k+n times, thus O(k+n) (or, O(n) if you so like).

aioobe
  • 413,195
  • 112
  • 811
  • 826
  • That would work, of course. But in many languages/libraries, you already have ready-to-use implementations of dynamic arrays, often even with implementations of `reverse` or even `rotate`. Also if you do the insertions repeatedly you must be careful of not to loose the property of the dynamic array having "enough" allocated space in the average case (which is needed for amortized constant time when appending) When you use a library for arrays, you might not have influence on the allocation... – MartinStettner Oct 24 '11 at 09:09
  • I think there's a typo in your answer, O(k+n) is not O(n²) – MartinStettner Oct 24 '11 at 09:10
  • Not sure I get your first comment. Fixed the ordo-typo. Thanks. – aioobe Oct 24 '11 at 09:15
  • Dynamic arrays depend on the fact, that the allocated space doubles each time you need "more" place. If, for instance, you're using C++/STL `vector` class, and you translate your first code line into it, it will allocate exactly the space needed for the `k` insertions. If you alternatively insert `k` elements and then append one single element, the latter operation will always take `O(n)` instead of `O(1)`. Of course that can be fixed, but then again, you won't have a "general" insertion function. I found it interesting to express insertions by a combination of append and rotate – MartinStettner Oct 24 '11 at 09:30
  • Yes, that can obviously be fixed by changing to `new T[(k + n) * factorOfYourChoice]`. – aioobe Oct 24 '11 at 09:31
  • After a bit of thinking, I modified the question saying the number of elements is not known in advance (thanks dacwe to pointing that out). Sorry, if your answer doesn't fit the question anymore, I gave you +1 anyway (for the original question, your solution will probably be the better one ...) – MartinStettner Oct 24 '11 at 13:48