Arrays and Dynamic Arrays: Unleashing the Power of Data Storage and Manipulation

In continuation for our series Demystifying Data Structures and Algorithms: A Comprehensive Guide for Developers we are going to discuss on

1. Arrays and Dynamic Arrays:

• What are Arrays:

  • Arrays are a fundamental data structure in JavaScript that allows you to store multiple elements of any data type in a sequential manner.
  • They provide efficient indexing and random access to elements.
  • Here's an example of creating and accessing elements in an array:

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

  • Arrays in JavaScript have various built-in methods for operations such as insertion, deletion, searching, and iteration.

• Dynamic Arrays:

  • Dynamic arrays are an extension of static arrays with the ability to automatically resize and accommodate a varying number of elements.
  • In JavaScript, arrays are dynamic by nature, as you can dynamically add or remove elements without explicitly managing the array size.
    • Here's an example of dynamically adding elements to an array:

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

- As you add elements to a dynamic array, it 
  automatically 
  allocates memory to accommodate the new elements.
- Dynamic arrays handle resizing behind the scenes, 
  allowing you to add or remove elements without worrying 
  about the size limitation of static arrays.

• Array Operations:
  • Both arrays and dynamic arrays support common operations such as insertion, deletion, searching, and iteration.
  • Here are some examples of array operations in JavaScript:
  • Insertion:

       let arr = [1, 2, 3];
       arr.push(4); // Add an element at the end
       console.log(arr); // Output: [1, 2, 3, 4]
       arr.splice(1, 0, 5); // Insert an element at index 1
       console.log(arr); // Output: [1, 5, 2, 3, 4]

 - Deletion:

        let arr = [1, 2, 3, 4];
        arr.pop(); // Remove the last element
        console.log(arr); // Output: [1, 2, 3]
        arr.splice(1, 1); // Remove an element at index 1
        console.log(arr); // Output: [1, 3]

 - Searching:

        let arr = [1, 2, 3, 4];
        let index = arr.indexOf(3); // Find the index of 
        element 3
        console.log(index); // Output: 2

 - Iteration:

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

• Arrays and dynamic arrays provide a versatile and efficient way to store and manipulate collections of data in JavaScript. Whether you need a fixed-size array or a dynamically resizable one, JavaScript's array capabilities have got you covered.

Now let solve some leedcode arrays popular questions:
We are going to solve 3 Arrays and Dynamic Arrays leedocode questions:

• First thing first before you start solving logical problems you need determine whether the question is related to Arrays or Dynamic Arrays to that you need to:
• Read the problem description carefully to identify any references to arrays or dynamic arrays. Look for mentions of elements, indexing, subarrays, or resizing.
• Pay attention to specific keywords that often hint at array-related problems, such as "sum," "subarray," "rotation," "rearrange," "window," or "consecutive." These keywords often appear in array manipulation or traversal scenarios.
• LeetCode assigns tags to each problem, indicating the main topics or data structures involved. Look for tags like "Array," "Dynamic Programming," or "Two Pointers." These tags can provide insights into the problem's nature.
• Check the problem's input and output constraints. If the problem involves manipulating or analyzing a collection of elements, it could be related to arrays or dynamic arrays.

1. Two Sum:

• Description: Given an array of integers, find two numbers
  that add up to a specific target.

• LeetCode problem link: Two Sum

• Algorithmic Approach:

  • Use a hash map to store the elements of the array and their indices
  • iterate through the array and for each element, calculate its complement (target minus the current element).
  • Check if the complement exists in the hash map. If it does, return the indices of the two numbers that add up to the target.
  • If no pair is found, return an empty array.
  • Time Complexity: O(n), where n is the number of elements in the array.
  • Space Complexity: O(n), as the hash map may store up to n elements in the worst case.

• Javascript code sample
  
  

function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

1. Maximum Subarray:
   • Description: Find the contiguous subarray with the largest sum in an array of numbers.
   • LeetCode problem link: Maximum Subarray
   • Algorithmic Approach:
     • Initialize two variables, maxSum and currentSum, to track the maximum subarray sum and the sum of the current subarray.
     • Iterate through the array and for each element, update the currentSum by taking the maximum of the current element itself or the currentSum plus the current element.
     • Update maxSum with the maximum of maxSum and currentSum at each step.
     • Finally, return maxSum as the maximum subarray sum.
     • Time Complexity: O(n), where n is the number of elements in the array.
     • Space Complexity: O(1), as only a constant amount of extra space is used.
2. JavaScript code sample:

function maxSubArray(nums) {
  let maxSum = nums[0];
  let currentSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

1. Rotate Array:
   • Description: Rotate an array of numbers to the right by a given number of steps.
   • LeetCode problem link: Rotate Array
   • Algorithmic Approach:
     • Calculate the actual number of rotations required by taking the modulo of k with the length of the array. This ensures that excessive rotations are reduced.
     • Reverse the entire array.
     • Reverse the first rotations elements.
     • Reverse the remaining elements after the rotations.
   • Time Complexity: O(n), where n is the number of elements in the array.
   • Space Complexity: O(1), as the rotations are performed in-place without requiring additional space.
   • JavaScript code sample:

function rotate(nums, k) {
  const rotations = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, rotations - 1);
  reverse(nums, rotations, nums.length - 1);
}

function reverse(nums, start, end) {
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
}