Mastering Array Manipulation in DSA using JavaScript: From Basics to Advanced

Mastering Array Manipulation in JavaScript for DSA

Arrays are fundamental data structures in computer science and are extensively used in various algorithms and problem-solving scenarios. This comprehensive guide will take you through the essentials of array manipulation in JavaScript, covering topics from basic to advanced levels. We'll explore traversal, insertion, deletion, searching, and more, along with their time complexities and practical examples.

Table of Contents

1. Introduction to Arrays
2. Array Traversal
3. Insertion in Arrays
4. Deletion in Arrays
5. Searching in Arrays
6. Advanced Array Manipulation Techniques
7. Practice Problems
8. LeetCode Problem Links

1. Introduction to Arrays

An array is a collection of elements stored at contiguous memory locations. In JavaScript, arrays are dynamic and can hold elements of different types.

Basic array operations:

// Creating an array
let arr = [1, 2, 3, 4, 5];

// Accessing elements
console.log(arr[0]); // Output: 1

// Modifying elements
arr[2] = 10;
console.log(arr); // Output: [1, 2, 10, 4, 5]

// Getting array length
console.log(arr.length); // Output: 5

Time Complexity:

• Accessing elements: O(1)
• Modifying elements: O(1)
• Getting array length: O(1)

2. Array Traversal

Traversal means visiting each element of the array once. There are several ways to traverse an array in JavaScript.

2.1 Using a for loop

let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

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

2.2 Using forEach

let arr = [1, 2, 3, 4, 5];
arr.forEach(element => console.log(element));

Time Complexity: O(n)

2.3 Using for...of loop

let arr = [1, 2, 3, 4, 5];
for (let element of arr) {
    console.log(element);
}

Time Complexity: O(n)

3. Insertion in Arrays

Insertion in arrays can be done at the beginning, end, or at a specific position.

3.1 Insertion at the end

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

Time Complexity: O(1) (amortized)

3.2 Insertion at the beginning

let arr = [1, 2, 3];
arr.unshift(0);
console.log(arr); // Output: [0, 1, 2, 3]

Time Complexity: O(n), as all existing elements need to be shifted

3.3 Insertion at a specific position

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

Time Complexity: O(n), as elements after the insertion point need to be shifted

4. Deletion in Arrays

Similar to insertion, deletion can be performed at the beginning, end, or at a specific position.

4.1 Deletion from the end

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

Time Complexity: O(1)

4.2 Deletion from the beginning

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

Time Complexity: O(n), as all remaining elements need to be shifted

4.3 Deletion at a specific position

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

Time Complexity: O(n), as elements after the deletion point need to be shifted

5. Searching in Arrays

Searching is a common operation performed on arrays. Let's look at some searching techniques.

5.1 Linear Search

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(linearSearch(arr, 5)); // Output: 2
console.log(linearSearch(arr, 6)); // Output: -1

Time Complexity: O(n)

5.2 Binary Search (for sorted arrays)

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 5)); // Output: 2
console.log(binarySearch(arr, 6)); // Output: -1

Time Complexity: O(log n)

6. Advanced Array Manipulation Techniques

Now let's explore some more advanced techniques for array manipulation.

6.1 Two Pointer Technique

The two-pointer technique is often used to solve array problems efficiently. Here's an example of using two pointers to reverse an array in-place:

function reverseArray(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

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

Time Complexity: O(n)

6.2 Sliding Window Technique

The sliding window technique is useful for solving subarray problems. Here's an example to find the maximum sum subarray of size k:

function maxSumSubarray(arr, k) {
    let maxSum = 0;
    let windowSum = 0;

    // Calculate sum of first window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

let arr = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSumSubarray(arr, 4)); // Output: 39

Time Complexity: O(n)

6.3 Kadane's Algorithm

Kadane's algorithm is used to find the maximum subarray sum in an array. It's an example of dynamic programming:

function kadane(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
console.log(kadane(arr)); // Output: 7

Time Complexity: O(n)

6.4 Dutch National Flag Algorithm

This algorithm is used to sort an array containing only 0s, 1s, and 2s:

function dutchNationalFlag(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }
}

let arr = [2, 0, 1, 2, 1, 0];
dutchNationalFlag(arr);
console.log(arr); // Output: [0, 0, 1, 1, 2, 2]

Time Complexity: O(n)

7. Practice Problems

Here are 50 practice problems ranging from easy to advanced levels. Some of these are from LeetCode, while others are common array manipulation scenarios:

1. Sum all elements in an array
2. Find the maximum element in an array
3. Reverse an array in-place
4. Remove duplicates from a sorted array
5. Rotate an array by k steps
6. Find the second largest element in an array
7. Merge two sorted arrays
8. Find the missing number in an array of 1 to n
9. Move all zeros to the end of the array
10. Find the intersection of two arrays
11. Find the union of two arrays
12. Check if an array is a subset of another array
13. Find the equilibrium index in an array
14. Rearrange positive and negative numbers in an array
15. Find the majority element in an array
16. Find the peak element in an array
17. Implement a circular array
18. Find the smallest positive missing number in an array
19. Trapping Rain Water problem
20. Implement a stack using an array
21. Implement a queue using an array
22. Find the longest increasing subsequence
23. Implement binary search in a rotated sorted array
24. Find the maximum sum of a subarray of size k
25. Implement the Kadane's algorithm
26. Find the minimum number of platforms required for a railway station
27. Find the longest subarray with equal number of 0s and 1s
28. Implement the Dutch National Flag algorithm
29. Find the smallest subarray with sum greater than a given value
30. Implement the Boyer-Moore Majority Voting algorithm
31. Find the maximum product subarray
32. Implement the Jump Game algorithm
33. Find the next greater element for every element in an array
34. Implement the Sliding Window Maximum algorithm
35. Find the longest substring without repeating characters
36. Implement the Merge Intervals algorithm
37. Find the minimum number of jumps to reach the end of an array
38. Implement the Stock Buy Sell to Maximize Profit algorithm
39. Find the Longest Palindromic Substring
40. Implement the Longest Common Subsequence algorithm
41. Find the Shortest Unsorted Continuous Subarray
42. Implement the Container With Most Water algorithm
43. Find the Longest Consecutive Sequence in an array
44. Implement the Maximum Product of Three Numbers algorithm
45. Find the Kth Largest Element in an Array
46. Implement the Find All Duplicates in an Array algorithm
47. Find the Minimum Size Subarray Sum
48. Implement the Product of Array Except Self algorithm
49. Find the Maximum Gap in a sorted array
50. Implement the Median of Two Sorted Arrays algorithm

8. LeetCode Problem Links

Here are 20 LeetCode problems to test your array manipulation skills:

1. Two Sum
2. Best Time to Buy and Sell Stock
3. Contains Duplicate
4. Product of Array Except Self
5. Maximum Subarray
6. Merge Intervals
7. 3Sum
8. Container With Most Water
9. Rotate Array
10. Search in Rotated Sorted Array
11. Find Minimum in Rotated Sorted Array
12. Next Permutation
13. Subarray Sum Equals K
14. Spiral Matrix
15. Jump Game
16. Longest Consecutive Sequence
17. Find All Duplicates in an Array
18. Kth Largest Element in an Array
19. Trapping Rain Water
20. Median of Two Sorted Arrays

By working through these problems and understanding the underlying concepts, you'll significantly improve your array manipulation skills in JavaScript for Data Structures and Algorithms.

Remember, the key to mastering these techniques is consistent practice and understanding the time and space complexities of your solutions.

Happy coding!

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