Data Structure and Algorithms with JS - Part 1 : Arrays

Arrays are a fundamental data structure in computer science and are used in a wide variety of applications. They are particularly useful for storing and manipulating large datasets, as they allow us to access and manipulate elements quickly using their indices.

There are several advantages to using arrays:

• Arrays are efficient for storing and accessing data. Because elements are stored in a contiguous block of memory, we can access them quickly using their indices.
• Arrays are easy to use. They offer a simple interface for storing, accessing, and manipulating data.
• Arrays are flexible. We can store elements of any data type in an array, and we can add or remove elements at any time.

There are also some limitations to using arrays:

• Arrays have a fixed size. Once we create an array, we cannot change its size unless we create a new array and copy the elements from the old array to the new one.
• Arrays are not always the most efficient data structure for certain operations. For example, inserting or deleting elements from the middle of an array can be time-consuming, as it requires shifting all the elements after the inserted/deleted element.

Despite these limitations, arrays are still a widely used data structure due to their simplicity and efficiency. They are commonly used in a variety of programming languages, including C, C++, Java, and Python, as well as in many other applications.

In JavaScript , arrays are a subclass of the object data type, and they have a length property that represents the number of elements in the array. They are dynamic, which means that we can add or remove elements from the array at any time.

Elements of small enough arrays are stored in an internal fixed-size array. V8 allocates some extra space in the internal array to achieve constant amortized time for push() and similar operations that grow the array. When the array length decreases, the internal array may also shrink.

Once a JS array becomes large (this also includes holey arrays), V8 starts using a hash table to store the array elements. The array is now associated with the “slow” dictionary elements kind.

From [V8 Deep Dives] Understanding Array Internals

We can manipulate arrays in various ways. Here are a few examples:

• push method adds an element to the end of the array
• unshift method adds an element to the beginning of the array
• pop method removes the last element of the array
• shift method removes the first element of the array
• splice method removes or adds elements to the array at a specific index

Let’s Implement basic Array class in js

class MyArray {
  constructor() {
    this.length = 0
    this.data = {}
  }

  get(index) {
    return this.data[index]
  }
  push(item) {
    this.data[this.length] = item
    this.length++
    return this.length
  }
  pop() {
    let lastItem = this.data[this.length - 1]
    delete this.data[this.length - 1]
    this.length--
    return lastItem
  }
  delete(index) {
    this.shiftItems(index)
    delete this.data[this.length - 1]
    this.length--
  }
  shiftItems(index) {
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1]
    }
  }
}

const newarr = new MyArray()
newarr.push("Hi") //1
newarr.push("fiji") //2
newarr.push("you") //3
newarr.push("me") //4
newarr.delete(2) //3
newarr.get(2) //me
console.log(newarr) //{ length: 3, data: { '0': 'Hi', '1': 'fiji', '2': 'me' } }

Algorithms implemented using Arrays

Sorting

Sorting is a common operation in competitive programming. Sorting an array can make it easier to search for a specific element or to find the minimum or maximum element. There are many different sorting algorithms to choose from, including

• Selection Sort
• Bubble Sort
• Insertion Sort
• Merge Sort
• Quick Sort

Searching

Linear search and binary search are two algorithms that can be used to search for a specific element in an array.

Linear search is a simple algorithm that involves iterating through the array element by element and comparing each element to the target element. If the target element is found, the search is complete. If the target element is not found, the search continues until the end of the array is reached. Linear search has a time complexity of O(n), where n is the size of the array. This means that the time taken by the algorithm increases linearly with the size of the array.

Binary search is a more efficient algorithm that can be used to search for an element in a sorted array. It works by dividing the array in half and comparing the target element to the middle element. If the target element is less than the middle element, the search continues in the left half of the array. If the target element is greater than the middle element, the search continues in the right half of the array. This process is repeated until the target element is found or it is determined that the element is not present in the array. Binary search has a time complexity ofO(log n), which means that the time taken by the algorithm increases logarithmically with the size of the array.

Techniques used to solve problems using Arrays

Prefix sums:

Prefix sums are a technique that can be used to quickly find the sum of a range of elements in an array. They work by storing the cumulative sum of the elements in the original array in a new array. For example, if the original array is [1, 2, 3, 4], the prefix sum array would be [1, 3, 6, 10]. Here is an example of how you might implement prefix sums in JavaScript:

function prefixSums(array) {
  let prefixSumArray = [array[0]]
  for (let i = 1; i < array.length; i++) {
    prefixSumArray[i] = prefixSumArray[i - 1] + array[i]
  }
  return prefixSumArray
}

let array = [1, 2, 3, 4]
let prefixSumArray = prefixSums(array)
console.log(prefixSumArray) // Output: [1, 3, 6, 10]

You can then use the prefix sum array to quickly find the sum of a range of elements in the original array. For example, to find the sum of the elements in the range [1, 3] (i.e., the sum of the second, third, and fourth elements in the array), you can use the following code:

let startIndex = 1
let endIndex = 3
let sum = prefixSumArray[endIndex] - prefixSumArray[startIndex - 1]
console.log(sum) // Output: 9

Prefix sums have a time complexity of O(n) and require O(n) additional space to store the prefix sum array. They are useful for quickly answering queries about ranges of elements in an array, and they can be especially useful in dynamic programming problems where you need to perform repeated queries on the same array.

Here are a few examples of Leetcode problems where prefix sums can be used to efficiently find the solution:

1. Subarray Sum Equals K: Given an array of integers and a target sum, find the number of contiguous subarrays whose sum is equal to the target sum.

2. Minimum Size Subarray Sum: Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

3. Range Sum Query - Mutable: Given an integer array nums, you are allowed to perform the following operations: sumRange(i, j): Returns the sum of the elements in nums between indices i and j (i ≤ j), inclusive. update(i, val): Modifies nums by updating the element at index i to val.

4. Number of Subarrays with Bounded Maximum: We are given an array A of positive integers, and two positive integers L and R. Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

5. Subarray Product Less Than K: Your are given an array of positive integers nums. Count and return the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

In all of these problems, prefix sums can be used to efficiently find the sum or product of a range of elements in the array, which can then be used to solve the problem.

Two pointer technique:

The two pointer technique is a technique that involves using two pointers to iterate through an array and perform some operation on the elements. It is often used to solve problems that involve finding a pair of elements that meet some condition or to find the maximum or minimum of a contiguous subarray.

Here is an example of how the two pointer technique might be used to find the maximum sum of a contiguous subarray in an array:

function maxSumSubarray(array) {
  let maxSum = 0
  let start = 0
  let end = 0
  let currentSum = 0
  while (end < array.length) {
    currentSum += array[end]
    if (currentSum > maxSum) {
      maxSum = currentSum
      start = start
      end = end
    } else if (currentSum < 0) {
      currentSum = 0
      start = end + 1
    }
    end++
  }
  return maxSum
}

let array = [2, -3, 4, -1, -2, 1, 5, -3]
let maxSum = maxSumSubarray(array)
console.log(maxSum) // Output: 7

In this example, the two pointers start and end are used to mark the start and end of the current contiguous subarray. The currentSum variable is used to store the sum of the elements in the current subarray. The algorithm iterates through the array, adding each element to the currentSum and updating the maxSum and start and end pointers as necessary.

The two pointer technique can be very useful for solving problems that involve finding pairs of elements or subarrays that meet certain conditions. It is often used in competitive programming and can be an efficient way to solve certain types of problems.

Here are a few examples of Leetcode problems where two pointers technique can be used to efficiently find the solution:

1. Two Sum: Given an array of integers, return indices of the two numbers such that they add up to a specific target.

2. 3Sum: Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

3. Container With Most Water: Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

4. Valid Palindrome: Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

5. Reverse String: Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

In all of these problems, the two pointer technique can be used to efficiently iterate through the array and perform some operation on the elements, such as comparing them to a target value or checking for palindromicity.

Sliding window:

The sliding window technique is a technique that involves maintaining a window of elements in an array and sliding it along the array to perform some operation on the elements in the window. It is often used to solve problems that involve finding the maximum or minimum of a contiguous subarray or finding the number of elements that meet some condition.

Here is an example of how the sliding window technique might be used to find the maximum sum of a contiguous subarray of size k in an array:

function maxSumSubarray(array, k) {
  let maxSum = 0
  let currentSum = 0
  for (let i = 0; i < k; i++) {
    currentSum += array[i]
  }
  maxSum = currentSum
  for (let i = k; i < array.length; i++) {
    currentSum += array[i] - array[i - k]
    maxSum = Math.max(maxSum, currentSum)
  }
  return maxSum
}

let array = [2, -3, 4, -1, -2, 1, 5, -3]
let maxSum = maxSumSubarray(array, 3)
console.log(maxSum) // Output: 7

In this example, the sliding window is represented by the currentSum variable, which stores the sum of the elements in the current window. The algorithm iterates through the array, adding each element to the currentSum and subtracting the element that is being removed from the window. The maxSum variable is used to store the maximum sum of all the windows.

The sliding window technique can be very useful for solving problems that involve finding the maximum or minimum of a contiguous subarray or the number of elements that meet a certain condition. It is often used in competitive programming and can be an efficient way to solve certain types of problems.

Here are a few examples of Leetcode problems where the sliding window technique can be used to efficiently find the solution

1. Minimum Window Substring: Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

2. Longest Substring Without Repeating Characters: Given a string, find the length of the longest substring without repeating characters.

3. Find All Anagrams in a String: Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

4. Longest Substring with At Most Two Distinct Characters: Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

5. Sliding Window Maximum: Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

In all of these problems, the sliding window technique can be used to efficiently iterate through the array or string and perform some operation on the elements in the window.

2D Array:

The 2D array technique is a technique for working with two-dimensional arrays, which are arrays that have rows and columns. 2D arrays are commonly used to store and manipulate data in a variety of contexts, such as image processing, data analysis, and competitive programming.

There are many algorithms and techniques that can be used to work with 2D arrays, including looping through the elements of the array, rotating the array, finding the maximum or minimum of a submatrix, and using prefix sums to find the sum of a range of elements.

To use the 2D array technique effectively, it is important to have a good understanding of how 2D arrays work and how to manipulate them. This may involve understanding how to access and modify elements of the array, how to iterate through the elements of the array, and how to use algorithms and techniques to perform operations on the elements of the array.

Overall, the 2D array technique is a powerful tool for working with data and solving problems in a variety of contexts, and it is an important concept to understand for those interested in computer science and data analysis.

Here are a few examples of Leetcode problems where the 2D array technique can be used to find the solution.

1. Rotate Image: You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).

2. Maximal Square: Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

3. Spiral Matrix: Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

4. Spiral Matrix II: Given a positive integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

5. Set Matrix Zeroes: Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

In all of these problems, the 2D array technique can be used to manipulate and analyze the elements of the array in order to find the solution.

Dynamic Programming:

Dynamic programming is a technique for solving problems by breaking them down into smaller subproblems and storing the results of these subproblems to avoid redundant work. It is often used to solve problems that have overlapping subproblems, such as optimization problems or problems that involve computing the same value multiple times.

Here is an example of how dynamic programming might be used to solve the Fibonacci sequence problem:

function fibonacci(n) {
  let cache = new Array(n + 1).fill(0)
  return fibonacciHelper(n, cache)
}

function fibonacciHelper(n, cache) {
  if (n === 0 || n === 1) {
    return n
  }
  if (cache[n] > 0) {
    return cache[n]
  }
  cache[n] = fibonacciHelper(n - 1, cache) + fibonacciHelper(n - 2, cache)
  return cache[n]
}

console.log(fibonacci(10)) // Output: 55

In this example, the fibonacci function uses dynamic programming to compute the nth number in the Fibonacci sequence. The fibonacciHelper function is used to compute the Fibonacci value recursively, with a cache to store the results of previous computations to avoid redundant work.

Dynamic programming can be very useful for solving problems that involve optimization or computing the same value multiple times. It is often used in competitive programming and can be an efficient way to solve certain types of problems.

Here are a few examples of Leetcode problems where dynamic programming can be used to find the solution.

1. Climbing Stairs: You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

2. Maximum Subarray: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

3. Unique Paths: A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

4. Minimum Path Sum: Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

5.Coin Change: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

In all of these problems, dynamic programming can be used to break the problem down into smaller subproblems and store the results of these subproblems to avoid redundant work. This can help to improve the efficiency of the solution and make it possible to solve larger or more complex problems.

These are just a few examples of the many algorithms and techniques that are commonly used in competitive programming and that involve working with arrays.

Conclusion

Arrays are a fundamental data structure that is commonly used in competitive programming. These are some techniques and algorithms that can be used to work with arrays and solve problems efficiently, such as linear search, binary search, sorting algorithms, prefix sums, two pointer technique, sliding window technique, 2D array techniques, and dynamic programming.

To be successful in competitive programming, it is important to have a strong understanding of these techniques and be able to apply them effectively to solve problems. This may involve understanding how to access and modify elements of an array, how to iterate through the elements of an array, and how to use algorithms and techniques to perform operations on the elements of an array.

Overall, the ability to effectively work with arrays is an important skill for those interested in competitive programming and can be the key to solving a wide range of problems.