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.
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:
Traversal means visiting each element of the array once. There are several ways to traverse an array in JavaScript.
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.
let arr = [1, 2, 3, 4, 5]; arr.forEach(element => console.log(element));
Time Complexity: O(n)
let arr = [1, 2, 3, 4, 5];
for (let element of arr) {
console.log(element);
}
Time Complexity: O(n)
Insertion in arrays can be done at the beginning, end, or at a specific position.
let arr = [1, 2, 3]; arr.push(4); console.log(arr); // Output: [1, 2, 3, 4]
Time Complexity: O(1) (amortized)
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
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
Similar to insertion, deletion can be performed at the beginning, end, or at a specific position.
let arr = [1, 2, 3, 4]; arr.pop(); console.log(arr); // Output: [1, 2, 3]
Time Complexity: O(1)
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
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
Searching is a common operation performed on arrays. Let's look at some searching techniques.
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)
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)
Now let's explore some more advanced techniques for array manipulation.
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)
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)
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)
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)
Here are 50 practice problems ranging from easy to advanced levels. Some of these are from LeetCode, while others are common array manipulation scenarios:
Here are 20 LeetCode problems to test your array manipulation skills:
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!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
