CODEWITHSUNDEEP
arraysalgorithmcomplexity-theorydynamic-arrays
MartinStettner
MartinStettner

Reputation: 29164

Inserting unknown number of elements into dynamic array in linear time

(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?

Upvotes: 2

Views: 2418

Answers (2)

aioobe
aioobe

Reputation: 420951

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).

Upvotes: 3

MartinStettner
MartinStettner

Reputation: 29164

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.

Upvotes: 3

Related Questions