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
- Introduction to Arrays
- Array Traversal
- Insertion in Arrays
- Deletion in Arrays
- Searching in Arrays
- Advanced Array Manipulation Techniques
- Practice Problems
- 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:
- Sum all elements in an array
- Find the maximum element in an array
- Reverse an array in-place
- Remove duplicates from a sorted array
- Rotate an array by k steps
- Find the second largest element in an array
- Merge two sorted arrays
- Find the missing number in an array of 1 to n
- Move all zeros to the end of the array
- Find the intersection of two arrays
- Find the union of two arrays
- Check if an array is a subset of another array
- Find the equilibrium index in an array
- Rearrange positive and negative numbers in an array
- Find the majority element in an array
- Find the peak element in an array
- Implement a circular array
- Find the smallest positive missing number in an array
- Trapping Rain Water problem
- Implement a stack using an array
- Implement a queue using an array
- Find the longest increasing subsequence
- Implement binary search in a rotated sorted array
- Find the maximum sum of a subarray of size k
- Implement the Kadane's algorithm
- Find the minimum number of platforms required for a railway station
- Find the longest subarray with equal number of 0s and 1s
- Implement the Dutch National Flag algorithm
- Find the smallest subarray with sum greater than a given value
- Implement the Boyer-Moore Majority Voting algorithm
- Find the maximum product subarray
- Implement the Jump Game algorithm
- Find the next greater element for every element in an array
- Implement the Sliding Window Maximum algorithm
- Find the longest substring without repeating characters
- Implement the Merge Intervals algorithm
- Find the minimum number of jumps to reach the end of an array
- Implement the Stock Buy Sell to Maximize Profit algorithm
- Find the Longest Palindromic Substring
- Implement the Longest Common Subsequence algorithm
- Find the Shortest Unsorted Continuous Subarray
- Implement the Container With Most Water algorithm
- Find the Longest Consecutive Sequence in an array
- Implement the Maximum Product of Three Numbers algorithm
- Find the Kth Largest Element in an Array
- Implement the Find All Duplicates in an Array algorithm
- Find the Minimum Size Subarray Sum
- Implement the Product of Array Except Self algorithm
- Find the Maximum Gap in a sorted array
- Implement the Median of Two Sorted Arrays algorithm
8. LeetCode Problem Links
Here are 20 LeetCode problems to test your array manipulation skills:
- Two Sum
- Best Time to Buy and Sell Stock
- Contains Duplicate
- Product of Array Except Self
- Maximum Subarray
- Merge Intervals
- 3Sum
- Container With Most Water
- Rotate Array
- Search in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array
- Next Permutation
- Subarray Sum Equals K
- Spiral Matrix
- Jump Game
- Longest Consecutive Sequence
- Find All Duplicates in an Array
- Kth Largest Element in an Array
- Trapping Rain Water
- 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!
Top comments (1)
Amazing content