Array Insertion in DSA using JavaScript: From Basics to Advanced

Arrays are fundamental data structures in computer science, and understanding how to manipulate them efficiently is crucial for any developer. In this blog post, we'll dive deep into array insertion techniques using JavaScript, covering concepts from basic to advanced levels. We'll explore various scenarios, provide 20 examples, discuss time complexities, and even tackle some LeetCode-style problems.

Table of Contents

1. Introduction to Arrays
2. Basic Array Insertion
3. Inserting at Specific Positions
4. Inserting Multiple Elements
5. Efficient Insertion Techniques
6. Advanced Insertion Scenarios
7. LeetCode-Style Problems
8. Practice Problems

1. Introduction to Arrays

An array is a collection of elements stored at contiguous memory locations. In JavaScript, arrays are dynamic, meaning they can grow or shrink in size. Before we dive into insertion techniques, let's quickly recap the basics of JavaScript arrays.

// Creating an array
let fruits = ['apple', 'banana', 'orange'];

// Accessing elements
console.log(fruits[0]); // Output: 'apple'

// Getting array length
console.log(fruits.length); // Output: 3

2. Basic Array Insertion

Example 1: Inserting at the End (push)

The simplest way to insert an element into an array is to add it at the end using the push() method.

let numbers = [1, 2, 3];
numbers.push(4);
console.log(numbers); // Output: [1, 2, 3, 4]

Time Complexity: O(1) - Constant time

Example 2: Inserting at the Beginning (unshift)

To insert an element at the beginning of an array, use the unshift() method.

let colors = ['red', 'green'];
colors.unshift('blue');
console.log(colors); // Output: ['blue', 'red', 'green']

Time Complexity: O(n) - Linear time, where n is the number of elements in the array

Example 3: Inserting Using the Spread Operator

The spread operator can be used to create a new array with additional elements.

let animals = ['cat', 'dog'];
let newAnimals = ['bird', ...animals, 'fish'];
console.log(newAnimals); // Output: ['bird', 'cat', 'dog', 'fish']

Time Complexity: O(n) - Linear time, where n is the total number of elements in the new array

3. Inserting at Specific Positions

Example 4: Using splice() to Insert at a Specific Index

The splice() method can be used to insert elements at a specific position in the array.

let fruits = ['apple', 'banana', 'orange'];
fruits.splice(1, 0, 'mango');
console.log(fruits); // Output: ['apple', 'mango', 'banana', 'orange']

Time Complexity: O(n) - Linear time, where n is the number of elements after the insertion point

Example 5: Inserting Multiple Elements with splice()

You can insert multiple elements at once using splice().

let numbers = [1, 2, 5, 6];
numbers.splice(2, 0, 3, 4);
console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]

Time Complexity: O(n) - Linear time, where n is the number of elements after the insertion point

Example 6: Overwriting Elements

You can also use array indexing to overwrite elements at specific positions.

let letters = ['A', 'B', 'D', 'E'];
letters[2] = 'C';
console.log(letters); // Output: ['A', 'B', 'C', 'E']

Time Complexity: O(1) - Constant time

4. Inserting Multiple Elements

Example 7: Concatenating Arrays

The concat() method can be used to combine multiple arrays.

let arr1 = [1, 2];
let arr2 = [3, 4];
let arr3 = [5, 6];
let combined = arr1.concat(arr2, arr3);
console.log(combined); // Output: [1, 2, 3, 4, 5, 6]

Time Complexity: O(n) - Linear time, where n is the total number of elements in all arrays

Example 8: Using push() with Spread Operator

You can use push() with the spread operator to insert multiple elements at the end.

let numbers = [1, 2, 3];
let newNumbers = [4, 5, 6];
numbers.push(...newNumbers);
console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]

Time Complexity: O(m) - Linear time, where m is the number of elements being inserted

Example 9: Inserting an Array into Another Array

Here's how you can insert an entire array into another at a specific position.

function insertArray(mainArray, subArray, position) {
    return [...mainArray.slice(0, position), ...subArray, ...mainArray.slice(position)];
}

let main = [1, 2, 5, 6];
let sub = [3, 4];
console.log(insertArray(main, sub, 2)); // Output: [1, 2, 3, 4, 5, 6]

Time Complexity: O(n) - Linear time, where n is the total number of elements in the resulting array

5. Efficient Insertion Techniques

Example 10: Preallocating Array Size

When you know the final size of the array, preallocating can improve performance.

function createSequence(n) {
    let arr = new Array(n);
    for (let i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    return arr;
}

console.log(createSequence(5)); // Output: [1, 2, 3, 4, 5]

Time Complexity: O(n) - Linear time, but more efficient than growing the array dynamically

Example 11: Using Typed Arrays for Numeric Data

For large arrays of numeric data, using typed arrays can be more efficient.

let floatArray = new Float64Array(5);
for (let i = 0; i < 5; i++) {
    floatArray[i] = i * 1.1;
}
console.log(floatArray); // Output: Float64Array(5) [0, 1.1, 2.2, 3.3000000000000003, 4.4]

Time Complexity: O(n) - Linear time, but with better memory efficiency for numeric data

Example 12: Batch Insertion

When inserting multiple elements, doing it in batches can be more efficient than one at a time.

function batchInsert(arr, elements, batchSize = 1000) {
    for (let i = 0; i < elements.length; i += batchSize) {
        arr.push(...elements.slice(i, i + batchSize));
    }
    return arr;
}

let numbers = [1, 2, 3];
let newNumbers = Array.from({ length: 10000 }, (_, i) => i + 4);
console.log(batchInsert(numbers, newNumbers).length); // Output: 10003

Time Complexity: O(n) - Linear time, but with better performance for large insertions

6. Advanced Insertion Scenarios

Example 13: Inserting into a Sorted Array

When inserting into a sorted array, we can use binary search to find the correct position.

function insertSorted(arr, element) {
    let left = 0;
    let right = arr.length;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] < element) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    arr.splice(left, 0, element);
    return arr;
}

let sortedArray = [1, 3, 5, 7, 9];
console.log(insertSorted(sortedArray, 4)); // Output: [1, 3, 4, 5, 7, 9]

Time Complexity: O(log n) for finding the position + O(n) for insertion = O(n)

Example 14: Circular Buffer Insertion

A circular buffer is a fixed-size array that wraps around. Here's an implementation of insertion in a circular buffer.

class CircularBuffer {
    constructor(size) {
        this.buffer = new Array(size);
        this.size = size;
        this.head = 0;
        this.tail = 0;
        this.count = 0;
    }

    insert(element) {
        this.buffer[this.tail] = element;
        this.tail = (this.tail + 1) % this.size;
        if (this.count < this.size) {
            this.count++;
        } else {
            this.head = (this.head + 1) % this.size;
        }
    }

    getBuffer() {
        return this.buffer.slice(this.head, this.head + this.count);
    }
}

let cb = new CircularBuffer(3);
cb.insert(1);
cb.insert(2);
cb.insert(3);
cb.insert(4);
console.log(cb.getBuffer()); // Output: [2, 3, 4]

Time Complexity: O(1) for insertion

Example 15: Sparse Array Insertion

Sparse arrays have "empty" slots. Here's how to work with them:

let sparseArray = new Array(5);
sparseArray[2] = 'Hello';
sparseArray[4] = 'World';
console.log(sparseArray); // Output: [empty × 2, 'Hello', empty, 'World']
console.log(sparseArray.length); // Output: 5

// Iterating over sparse array
sparseArray.forEach((item, index) => {
    if (item !== undefined) {
        console.log(`${index}: ${item}`);
    }
});
// Output:
// 2: Hello
// 4: World

Time Complexity: O(1) for insertion, O(n) for iteration

Example 16: Insertion with Deduplication

When inserting elements, you might want to avoid duplicates:

function insertUnique(arr, element) {
    if (!arr.includes(element)) {
        arr.push(element);
    }
    return arr;
}

let uniqueNumbers = [1, 2, 3, 4];
console.log(insertUnique(uniqueNumbers, 3)); // Output: [1, 2, 3, 4]
console.log(insertUnique(uniqueNumbers, 5)); // Output: [1, 2, 3, 4, 5]

Time Complexity: O(n) due to the includes check

Example 17: Insertion with Priority

Implementing a basic priority queue using an array:

class PriorityQueue {
    constructor() {
        this.queue = [];
    }

    insert(element, priority) {
        const item = { element, priority };
        let added = false;
        for (let i = 0; i < this.queue.length; i++) {
            if (item.priority < this.queue[i].priority) {
                this.queue.splice(i, 0, item);
                added = true;
                break;
            }
        }
        if (!added) {
            this.queue.push(item);
        }
    }

    getQueue() {
        return this.queue.map(item => item.element);
    }
}

let pq = new PriorityQueue();
pq.insert('Task 1', 2);
pq.insert('Task 2', 1);
pq.insert('Task 3', 3);
console.log(pq.getQueue()); // Output: ['Task 2', 'Task 1', 'Task 3']

Time Complexity: O(n) for insertion

Example 18: Dynamic 2D Array Insertion

Creating and inserting into a dynamic 2D array:

function create2DArray(rows, cols) {
    return Array.from({ length: rows }, () => new Array(cols).fill(0));
}

function insert2D(arr, row, col, value) {
    // Expand array if necessary
    while (arr.length <= row) {
        arr.push([]);
    }
    while (arr[row].length <= col) {
        arr[row].push(0);
    }
    arr[row][col] = value;
}

let matrix = create2DArray(2, 2);
insert2D(matrix, 1, 1, 5);
insert2D(matrix, 3, 3, 7);
console.log(matrix);
// Output: [
//   [0, 0],
//   [0, 5],
//   [0],
//   [0, 0, 0, 7]
// ]

Time Complexity: O(1) average case, O(n) worst case when expanding the array

Example 19: Insertion into a Trie (Prefix Tree)

While not strictly an array, a trie uses arrays (or objects) internally and is useful for string insertions:

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.children[char]) {
                current.children[char] = new TrieNode();
            }
            current = current.children[char];
        }
        current.isEndOfWord = true;
    }

    search(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.children[char]) {
                return false;
            }
            current = current.children[char];
        }
        return current.isEndOfWord;
    }
}

let trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.search("apple")); // Output: true
console.log(trie.search("app")); // Output: true
console.log(trie.search("appl")); // Output: false

Time Complexity: O(m) for insertion and search, where m is the length of the word

Example 20: Insertion with Custom Sorting

Inserting elements while maintaining a custom sort order:

function insertSorted(arr, element, compareFn) {
    let index = arr.findIndex(item => compareFn(element, item) <= 0);
    if (index === -1) {
        arr.push(element);
    } else {
        arr.splice(index, 0, element);
    }
    return arr;
}

// Example: Sort by string length, then alphabetically
let words = ['cat', 'elephant', 'dog'];
let compareFn = (a, b) => {
    if (a.length !== b.length) {
        return a.length - b.length;
    }
    return a.localeCompare(b);
};

console.log(insertSorted(words, 'bear', compareFn));
// Output: ['cat', 'dog', 'bear', 'elephant']

Time Complexity: O(n) for finding the insertion point + O(n) for insertion = O(n)

7. LeetCode-Style Problems

Now that we've covered various insertion techniques, let's look at some LeetCode-style problems that involve array insertions.

Problem 1: Insert Interval

Given a sorted array of non-overlapping intervals and a new interval, insert the new interval and merge if necessary.

function insert(intervals, newInterval) {
    let result = [];
    let i = 0;

    // Add all intervals that come before newInterval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }

    // Add the merged interval
    result.push(newInterval);

    // Add remaining intervals
    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }

    return result;
}

console.log(insert([[1,3],[6,9]], [2,5]));
// Output: [[1,5],[6,9]]

Time Complexity: O(n), where n is the number of intervals

Problem 2: Merge Sorted Array

Given two sorted arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

function merge(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
}

let nums1 = [1,2,3,0,0,0];
let m = 3;
let nums2 = [2,5,6];
let n = 3;

merge(nums1, m, nums2, n);
console.log(nums1);
// Output: [1,2,2,3,5,6]

Time Complexity: O(m + n), where m and n are the lengths of nums1 and nums2 respectively

8. Practice Problems

To further test your understanding of array insertions, here are 15 LeetCode problems that involve various aspects of array manipulation and insertion:

1. Insert Interval
2. Merge Sorted Array
3. Insert Delete GetRandom O(1)
4. Search Insert Position
5. Array Partition I
6. Maximum Subarray
7. Move Zeroes
8. Sort Colors
9. Merge Intervals
10. Next Permutation
11. Find First and Last Position of Element in Sorted Array
12. 3Sum
13. Container With Most Water
14. Rotate Array
15. Product of Array Except Self

These problems cover a wide range of difficulty levels and will help you practice various array insertion and manipulation techniques.

Conclusion

Array insertion is a fundamental operation in data structures and algorithms. As we've seen, there are many ways to insert elements into arrays, each with its own use cases and time complexities. From simple push operations to more complex scenarios like maintaining sorted order or implementing data structures like circular buffers and tries, understanding these techniques will greatly enhance your ability to work with arrays efficiently.

Remember that the choice of insertion method can significantly impact the performance of your algorithm, especially when dealing with large datasets. Always consider the specific requirements of your problem and the trade-offs between time and space complexity when choosing an insertion technique.

Practice with the provided examples and LeetCode problems to solidify your understanding and improve your problem-solving skills.

Happy coding!

The above is the detailed content of Array Insertion in DSA using JavaScript: From Basics to Advanced. For more information, please follow other related articles on the PHP Chinese website!