I was asked this question in a Javascript interview and sadly, I couldnt e 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 plexity 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.

I was asked this question in a Javascript interview and sadly, I couldnt e 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 plexity 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.

• javascript
• algorithm

• 1 So you didn't go though R&D after interview .. – Runcorn Commented May 20, 2014 at 6:11
• 2 if you do not need to preserve original order of array then add first element to end of array and after that copy new element to first position – Spektre Commented May 20, 2014 at 6:14
• @FuzzyTree I saw unshift() does what we need, but not inbuilt function was expected by the interviewer. – Rahul Desai Commented May 20, 2014 at 6:14
• 1 Why not just make a new array with the first element, the use a for loop to add all the others to it? Or is there a shorter way with no built in functions? – David Fenko Commented May 20, 2014 at 6:15
• What about storing the first element into a temp variable, set the first position to the new value and then append the temp value to the end, since I imagine order doesn't matter in this case? – Chase Commented May 20, 2014 at 6:19

6 Answers 6

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.

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

A functional way to insert an element into an array @ position 0:

(function (val) { 
  var i = this.length; 
  while (i--){ this[i+1] = this[i]; };
  this[0] = val; 
}).call([1,2,3,4], 0); //=> [0,1,2,3,4]

Another (slightly faster)

(function (val) {
    this.reverse()[this.length] = val;
    return this.reverse();
}).call([1,2,3,4], 0); //=> [0,1,2,3,4]

jsFiddle example

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

Ordered - O(n)

for(var i=0; i<arr.length; i++)
    arr[i+1] = arr[i];

arr[0] = value;

Unordered - O(1)

arr[arr.length] = arr[0];
arr[0] = value;

Ordered - O(1)

arr[arr.length] = value;

// access ith item
arr[(arr.length-i-1)]

// print all items in order
for (int i=0; i<arr.length; i++)
    console.log( arr [ (arr.length-i-1) ] );

In this example, the array arr is reveresed, meaning you consider the last item in the array as the first one. :)

Many people have offered solutions which are basically 'shift everything, then replace the first element'. Perhaps a better way to think about the task is recursively 'insert the element at pos[0], then insert the old value at the first position in the rest of the array'.

We can write it iteratively like this:

function prepend(array, value) {
    for (i = 0; i < array.length; i++) {
        var old = array[i];
        array[i] = value;
        value = old;
    }
}

How about this:

<script>
var element = 1;
var array = [2, 3, 4, 5];
array = element + array;
alert(array[0]); //Prints 1
</script>

Not sure what this does in the background to be honest, but it seems to add the element to the beginning.