DEV Community

Manoj Swami
Manoj Swami

Posted on

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
Enter fullscreen mode Exit fullscreen mode

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]);
}
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (1)

Collapse
 
fode_oulare_b0acd4df2b222 profile image
Fode Oulare

Amazing content