Inserting an element in a 1D array at the first position

Question

I was asked this question in a Javascript interview and sadly, I couldnt come up with a better answer than the obvious one at that time: Creating a new array, assigning new value to the first location and copying the rest.

What would be the best algorithm in terms of time and space complexity for inserting an element in a 1D array at the first position?

EDIT: No built-in functions like unshift(), splice(), push() and all are to be used.

Answer 1

If the task is to simply insert an element at the head of a vanilla 1D array, then I think pretty much your only option is this O(N) approach:

for(var i = ary.length; i > 0; i--) {
    ary[i] = ary[i - 1];
}
ary[0] = value;

If the objective is to optimize the operation of inserting elements at the beginning of arrays (as in, there is a need to do that operation a lot), what you can do is create a data structure that maintains an array with empty space at the beginning and end, and the locations of the first and last populated items:

_ _ b d f a _ _ 
0 1 2 3 4 5 6 7

This allows you to insert and delete items at the beginning and end of your data structure in O(1) amortized time, simply by updating the index of the start or end and inserting the value in the next empty location, though the worst-case space usage is 2N.

When the beginning or end of the array fills up, create a new array with double the size of the previous one, and copy the values of the old array to the middle of the new one.

I don't know if that fits within the constraints of your interview question, but a lot of interview questions are more about testing your ability to think about problems, and your knowledge about algorithms, and less about producing the one right answer.

Answer 2

var myArr = [0, 1, 2];

function spliceToStart (value, inArray) {
    for (count = inArray.length; count > 0; count--) {
        inArray[count] = inArray[count-1];
    }
    inArray[0] = value;
};

spliceToStart('Value', myArr);
console.log(myArr);

Fiddle