Data Structure and Algorithm
Data Structure
Array

Mastering Array Data Structures in JavaScript: A Deep Dive into DSA Arrays

Arrays are an important part of programming. They are used to store and organize data in a specific order. In JavaScript, arrays are easy to use and come with many tools to help work with them. An array is a list where each item is automatically given a number, called an index, starting from zero. You can create an array using brackets [] and fill it with items separated by commas. You can look at any item in the array using its index or even change the value at a specific index. This makes arrays very useful and flexible for many tasks.

What is an Array?

An array is an ordered collection of elements, where each element is identified by a numerical index. Arrays are widely used for storing lists of data because of their simplicity and versatility.

Key Characteristics of Arrays:

  1. Indexing: Arrays use zero-based indexing.
  2. Order: The order of elements is maintained.
  3. Dynamic Size: In JavaScript, arrays can grow or shrink dynamically.
  4. Homogeneous and Heterogeneous: Arrays can store data of the same or mixed types.

Custom Implementation of an Array

Below is an example of a custom MyArray class that mimics the behavior of JavaScript's native arrays. This helps understand the internal mechanics of arrays.

class MyArray {
    constructor() {
        this.length = 0;
        this.data = {};
    }
 
    // Add an item to the end
    push(item) {
        this.data[this.length] = item;
        this.length++;
        return this.length;
    }
 
    // Access an item at a specific index
    get(index) {
        return this.data[index];
    }
 
    // Remove the last item
    pop() {
        if (this.length === 0) return undefined;
        const lastItem = this.data[this.length - 1];
        delete this.data[this.length - 1];
        this.length--;
        return lastItem;
    }
 
    // Remove the first item
    shift() {
        if (this.length === 0) return undefined;
        const firstItem = this.data[0];
        for (let i = 0; i < this.length - 1; i++) {
            this.data[i] = this.data[i + 1];
        }
        delete this.data[this.length - 1];
        this.length--;
        return firstItem;
    }
 
    // Delete an item at a specific index
    delete(index) {
        if (index < 0 || index >= this.length) return undefined;
        const item = this.data[index];
        for (let i = index; i < this.length - 1; i++) {
            this.data[i] = this.data[i + 1];
        }
        delete this.data[this.length - 1];
        this.length--;
        return item;
    }
}
 
// Example Usage
const myArray = new MyArray();
myArray.push(10);
myArray.push(20);
myArray.push(30);
console.log(myArray.pop()); // 30
console.log(myArray.shift()); // 10

Common DSA Problems with Arrays

1. Reverse a String

Problem: Reverse the characters of a string.

const str = 'apple banana orange';
let rev = '';
for (let i = str.length - 1; i >= 0; i--) {
    rev += str[i];
}
console.log(rev); // "egnaro ananab elppa"

2. Reverse an Array

Problem: Reverse the elements of an array.

Iterative Approach

const reverseArray = (arr) => {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
    return arr;
};
 
console.log(reverseArray([1, 2, 3, 4])); // [4, 3, 2, 1]

Iterative Two-Pointer Approach (for loop)

const numArr = [10, 7, 0, 5, 0, 9, 16, 91, 22, 22, 0]
for (let i = 0; i < numArr.length / 2; i++) {
    let temp = numArr[i];
    numArr[i] = numArr[numArr.length - 1 - i];
    numArr[numArr.length - 1 - i] = temp;
}
console.log(numArr);

Iterative Two-Pointer Approach (while loop)

const numArr = [10, 7, 0, 5, 0, 9, 16, 91, 22, 22, 0]
let left = 0;
let right = numArr.length - 1;
while (left < right) {
    let temp = numArr[left];
    numArr[left] = numArr[right];
    numArr[right] = temp;
    left++;
    right--;
}
 
console.log(numArr);

Destructuring Assignment (for loop)

const numArr = [10, 7, 0, 5, 0, 9, 16, 91, 22, 22, 0]
for (let i = 0, j = numArr.length - 1; i < numArr.length / 2; i++, j--) {
    [numArr[i], numArr[j]] = [numArr[j], numArr[i]];
}
 
console.log(numArr);

Recursive Approach

const reverseArrayRecursive = (arr, start, end) => {
    if (start >= end) return arr;
    [arr[start], arr[end]] = [arr[end], arr[start]];
    return reverseArrayRecursive(arr, start + 1, end - 1);
};
 
const array = [1, 2, 3, 4, 5];
console.log(reverseArrayRecursive(array, 0, array.length - 1)); // [5, 4, 3, 2, 1]

3. Check if a String is a Palindrome

Problem: Check whether a given string reads the same forward and backward.

const isPalindrome = (str) => {
    let reversed = '';
    for (let i = str.length - 1; i >= 0; i--) {
        reversed += str[i];
    }
    return str === reversed;
};
 
console.log(isPalindrome("cddc")); // true

4. Capitalize the First Letter of Each Word in a Sentence

Problem: Convert each word's first letter to uppercase.

const capitalizeWords = (sentence) => {
    const words = sentence.split(' ');
    return words.map(word => word.charAt(0).toUpperCase() + word.slice(1)).join(' ');
};
 
console.log(capitalizeWords("pratap das")); // "Pratap Das"

5. Move All Zeroes to the End

Problem: Move all zeroes in an array to the end while maintaining the order of non-zero elements.

const moveZeroesToEnd = (arr) => {
    let nonZeroIndex = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== 0) {
            arr[nonZeroIndex] = arr[i];
            nonZeroIndex++;
        }
    }
    for (let i = nonZeroIndex; i < arr.length; i++) {
        arr[i] = 0;
    }
    return arr;
};
 
console.log(moveZeroesToEnd([1, 0, 2, 0, 3, 0])); // [1, 2, 3, 0, 0, 0]

6. Find the Second Largest Element

Problem: Find the second-largest element in an array.

const findSecondLargest = (arr) => {
    let largest = -Infinity, secondLargest = -Infinity;
    for (const num of arr) {
        if (num > largest) {
            secondLargest = largest;
            largest = num;
        } else if (num > secondLargest && num !== largest) {
            secondLargest = num;
        }
    }
    return secondLargest;
};
 
console.log(findSecondLargest([10, 20, 30, 40])); // 30

7. Rotate an Array

Problem: Rotate an array by d positions to the left.

Iterative Approach

const rotateArray = (arr, d) => {
    d %= arr.length;
    return [...arr.slice(d), ...arr.slice(0, d)];
};
 
console.log(rotateArray([1, 2, 3, 4, 5], 2)); // [3, 4, 5, 1, 2]

Slicing and Concatenation Approach

function rotatedArray(array, position) {
    // Handle cases where position > array.length
    position = position % array.length;
 
    const first = [];
    const second = [];
 
    // Collect elements before the position
    for (let i = 0; i < position; i++) {
        first.push(array[i]);
    }
 
    // Collect elements from the position to the end
    for (let j = position; j < array.length; j++) {
        second.push(array[j]);
    }
 
    // Return the concatenated rotated array
    return [...second, ...first];
}
 console.log(rotatedArray([7, 3, 9, 1], position=9))

Recursive Approach

const rotateArrayRecursive = (arr, d) => {
    d %= arr.length;
    if (d === 0) return arr;
    const first = arr.shift();
    arr.push(first);
    return rotateArrayRecursive(arr, d - 1);
};
 
console.log(rotateArrayRecursive([2, 4, 6, 8, 10], 3)); // [8, 10, 2, 4, 6]

Types of Array Algorithms and Techniques in DSA

When working with arrays in Data Structures and Algorithms (DSA), mastering the various algorithmic techniques is crucial. Here's a breakdown of commonly used array algorithms and the techniques behind them:

Searching Algorithms

  • Purpose: Locate an element within an array.
  • Examples:
    • Linear Search: Sequentially checks each element.
    • Binary Search: Efficiently searches a sorted array by dividing the search range.
  • Techniques:
    • Linear: Iterate over all elements (O(n)).
    • Binary: Use divide-and-conquer (O(log n)).

Sorting Algorithms

  • Purpose: Arrange array elements in a specific order.
  • Examples:
    • Bubble Sort: Repeatedly swap adjacent elements if out of order.
    • Quick Sort: Partition around a pivot.
    • Merge Sort: Divide the array and merge sorted halves.
  • Techniques:
    • Comparison-based or divide-and-conquer methods.
    • Complexity: Bubble (O(n^2)), Quick/Merge (O(n log n)).

Two Pointer Technique

  • Purpose: Solve problems efficiently by maintaining two pointers.
  • Examples:
    • Finding pairs with a given sum.
    • Removing duplicates from a sorted array.
  • Technique:
    • Move two indices towards or away from each other based on conditions.

Sliding Window Technique

  • Purpose: Handle problems involving subarrays.
  • Examples:
    • Maximum sum of a subarray of size k.
    • Longest substring without repeating characters.
  • Technique:
    • Use a fixed or dynamic window to reduce redundant calculations (O(n)).

Kadane's Algorithm

  • Purpose: Find the maximum sum subarray.
  • Technique:
    • Maintain the maximum sum at each step, updating the global maximum (O(n)).

Prefix Sum / Cumulative Sum

  • Purpose: Precompute sums for fast range queries.
  • Examples:
    • Subarray sum.
    • Range queries.
  • Technique:
    • Use a prefix sum array and subtraction for constant-time sum retrieval.

Divide and Conquer

  • Purpose: Solve problems by breaking them into subproblems.
  • Examples:
    • Maximum subarray problem.
    • Merge Sort.
  • Technique:
    • Recursively divide the array and combine results.

Dynamic Programming on Arrays

  • Purpose: Solve optimization problems using previously computed results.
  • Examples:
    • Longest Increasing Subsequence.
    • Maximum sum of non-adjacent elements.
  • Technique:
    • Store results in a DP table to prevent redundant computation.

Greedy Algorithms

  • Purpose: Solve problems by making the optimal local choice.
  • Examples:
    • Minimum jumps to reach the end.
    • Interval scheduling.
  • Technique:
    • Use iterative steps to maximize or minimize results.

Matrix Manipulation (2D Arrays)

  • Purpose: Handle multidimensional array problems.
  • Examples:
    • Rotate a matrix.
    • Search in a sorted matrix.
  • Technique:
    • Traverse rows, columns, or diagonals, applying logic specific to the problem.

Hashing-Based Approaches

  • Purpose: Use hash tables for fast lookups.
  • Examples:
    • Find duplicates.
    • Subarray with zero sum.
  • Technique:
    • Use hash maps to store frequencies, prefix sums, or indices (O(1) average lookup).

Conclusion

Understanding array algorithms and techniques not only deepens your knowledge of arrays in JavaScript but also equips you to solve a wide range of DSA problems efficiently. By mastering arrays and creating custom functions for them, you can tackle advanced coding challenges and address real-life applications effectively. Whether it's sorting, searching, or optimizing, arrays form the foundation for solving complex programming problems with confidence.

Math Coding Problem StreetIntroduction