Home Blog Page 11

Solving Leetcode 206. Reverse Linked List

0

Given the head of a singly linked list, reverse the list, and return the reversed list.

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Explaining the question.

Leetcode problem 206, “Reverse Linked List,” is a classic coding challenge that tests a developer’s ability to manipulate linked lists.

In this problem, you are given a singly linked list, which consists of a sequence of nodes connected by pointers. Your task is to write a function that reverses the order of the nodes in the linked list. In other words, the function should take a linked list as input and return a new linked list with the same elements, but in the reverse order.

For example, given the following linked list:(Diagram shown above)

1 -> 2 -> 3 -> 4 -> 5

Your function should return a new linked list that looks like this:

5 -> 4 -> 3 -> 2 -> 1

Solving Leetcode 206

To solve this problem, you need to have a good understanding of how linked lists work and be able to implement the algorithm for reversing a linked list. This involves iterating over the list, updating the pointers of each node so that they point to the previous node, and returning the new head of the reversed list.

Solving in JavaScript:

Solving this problem can help you improve your skills with linked lists and algorithms, and is a common challenge that is often asked in coding interviews.

const reverseList = (head) => {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    let temp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = temp;
  }
  return prev;
};

Solving in Java:

public  ListNode reverseList(ListNode head) {
            if  (head ==  null  || head.next ==  null )  return  head;
            ListNode prev =  null ;
            ListNode curr = head;
            while  (curr !=  null ) {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return  prev;
        }

Problems similar to Leetcode 206 “Reverse Linked List”

  • Palindrome Linked List
  • Remove Nodes From Linked List

Solving Leetcode 236. Lowest Common Ancestor of a Binary Tree

0

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Explaining Leetcode 236

To solve the problem of finding the lowest common ancestor (LCA) of a binary tree, you can use a recursive approach. The basic idea is to recurse down the tree and at each node, check if the given nodes p and q are on the left or right subtree. If one of the nodes is on one side and the other is on the other side, then the current node is the LCA. Otherwise, if both nodes are on the left or right subtree, then recurse down that subtree to continue searching for the LCA.

It is difficult to provide a diagram for the problem of finding the lowest common ancestor (LCA) of a binary tree, as the tree can have any number of nodes and any structure. However, here is a general diagram showing the concept of an LCA in a binary tree:

     A
   /   \
  B     C
 / \   / \
D   E F   G
   /   \
  H     I

In this example, the LCA of nodes H and I is node E. The LCA of nodes D and I is node A, and the LCA of nodes A and C is also node A.

To find the LCA of two nodes in a binary tree, you can use a recursive or iterative approach, as discussed in the previous answer. The specific algorithm will depend on the structure of the tree and the positions of the given nodes.

Solution

There are two main ways to solve the problem of finding the lowest common ancestor (LCA) of a binary tree: using a recursive approach, or using an iterative approach.

The recursive approach involves defining a recursive function that takes the current node, and the two nodes for which we want to find the LCA. At each step, the function checks if the given nodes are on the left or right subtree of the current node. If one of the nodes is on one side and the other is on the other side, then the current node is the LCA. Otherwise, if both nodes are on the left or right subtree, then the function recursively searches for the LCA in that subtree.

The iterative approach, on the other hand, involves using a stack to store the nodes that we have visited while traversing the tree. We then iterate over the stack to find the first node that has the given nodes in its left and right subtrees, respectively. This node is the LCA.

Both of these approaches have the same time and space complexity, which is O(n) in the worst case, where n is the number of nodes in the tree. The choice of which approach to use will depend on the specific needs of your implementation and your personal preference.

You can also use an iterative approach to solve this problem. In this case, you would use a stack to store the nodes that you have visited while traversing the tree. You would then iterate over the stack to find the first node that has p and q in its left and right subtrees, respectively. This node would be the LCA.

For our purpose we will be using the recursive version.

Solving in JavaScript:

const lowestCommonAncestor = (root, p, q) => {
  if (root === null || root === p || root === q) return root;
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ? left : right;
};

Solving in TypeScript:

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  if (root === null || root === p || root === q) return root;
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ? left : right;
}

Solving in Java:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if (root == null) return null;
      if (root.val == p.val || root.val == q.val) return root;
      TreeNode left = lowestCommonAncestor(root.left, p, q);
      TreeNode right = lowestCommonAncestor(root.right, p, q);
      if (left != null && right != null) return root;
      if (left == null && right == null) return null;
      return left != null ? left : right;
}

The JavaScript Map Object and How to Use it.

0

The JavaScript Map object is an inbuilt data structure type which helps you to hold an array of values. The main difference between Map and Set is that Map has a key as well as a value, whereas Set only has a value. In JavaScript, the Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value.

The JavaScript map object is an inbuilt data structure type which helps you to hold an array of values.

The JavaScript map object is an inbuilt data structure type which helps you to hold an array of values.

The Map object remembers the original insertion order of the keys, whereas each value can be accessed using its key. This makes maps very useful when you want to look up some specific values based on their key.

JavaScript Maps are mostly used to store primitive values or arrays as keys and corresponding objects as values:

The main difference between Map and Set is that Map has a key as well as a value, whereas Set only has a value.

The main difference between Map and Set is that Map has a key as well as a value, whereas Set only has a value. The key allows you to store more than one value with the same key. Let’s look at an example:

Example in JavaScript:

var map1 = new Map();

map1.set('cat', 'meow'); // 1st item (value = 'meow')

map1.set('dog', 'woof'); // 2nd item (value = 'woof')

Map is a collection of keyed data items, just like an Object. But the main difference is that Map allows keys of any type.

Methods and properties are:

JavaScript Map Objects can also be used as keys

let foo = { n: 1 };
let visitsCountMap = new Map();
visitsCountMap.set(foo, 123);
// 123
console.log(visitsCountMap.get(foo)); 

To reiterate, a Map is a data structure that stores key-value pairs. You can use any type of object as a key, including an object. For now we won’t worry about custom generics.

One of the most notable features of Map is the use of objects as keys. String is also a key in Map, but we cannot use another Map as a key in Map.

var myMap = {};
var key1 = {};
var key2 = {};
myMap[key1] = "value1";
myMap[key2] = "value2";
console.log(myMap); // Output: { '[object Object]': 'value2' }

In JavaScript, the Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value.

The Map object is a data structure that holds key-value pairs. It is one of the most important additions to JavaScript in ES6, or ECMAScript 6. This article will show you how the Map object works and give you some examples on how to use it.

The Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value.

Iteration over Map

For looping over a map, there are 3 methods:

  • map.keys() – returns an iterable for keys,
  • map.values() – returns an iterable for values,
  • map.entries() – returns an iterable for entries [key, value], it’s used by default in for..of.
const cities = new Map([
  ['London', 8615246],
  ['Berlin', 3562166],
  ['Madrid', 3165235],
]);

//iterate over keys (cities)
for (let city of cities.keys()) {
  console.log(city);
}
// iterate over values (populations)
for (let population of cities.values()) {
  console.log(population);
} 
// iterate over [key, value] entries
for (let entry of cities.entries()) {
  console.log(entry);
}
// iterate over [key, value] entries with destructuring
for (let [city, population] of cities.entries()) {
  console.log(city, population);
}

Map also has a built in high order array function.

cities.forEach((value, key) => console.log(key + ' = ' + value));

Iterating using for loop

Iterating over keys and values: You can use the keys() method to get an iterator object that contains all the keys in the Map object, and the values() method to get an iterator object that contains all the values. You can then use a loop, such as a for...of loop, to iterate over the keys or values. For example:

for (const key of map.keys()) {
   console.log(key);
}
for (const value of map.values()) {
   console.log(value);
}

Object.fromEntries: Object from Map

The Object.fromEntries() method transforms a list of key-value pairs into an object. This is the inverse of Object.entries(). The syntax is: Object.fromEntries(iterable) Where iterable is an iterable object, such as an Array, Map, Set, etc.

For example, you have a list of key-value pairs:

const arr = [
  ['a', 1],
  ['b', 2],
  ['c', 3],
];

You can use Object.fromEntries() to create an object from this list: const obj = Object.fromEntries(arr); console.log(obj); // { a: 1, b: 2, c: 3 }

Object.entries: Map from Object

When a Map is created, we can pass an array (or another iterable) with key/value pairs for initialization.

If we have a plain object, and we’d like to create a Map from it, then we can use built-in method Object.entries(obj) that returns an array of key/value pairs for an object exactly in that format.

So we can create a map from an object like this:

let obj = {
  city: "LA",
  temp: 75
};

let map = new Map(Object.entries(obj));
// LA
alert( map.get('city') ); 

Deleting an Entry

Deleting entries: You can use the delete() method to remove a specific entry from the Map object by providing the key. For example:

map.delete('key1');
console.log(map.has('key1')); // Output: false

The delete() method in JavaScript’s Map object is used to remove a specific key-value pair from the map. Here are some pros and cons of using the delete() method:

Pros:

  1. Easy removal: The delete() method provides a simple way to remove a key-value pair from the Map object. You just need to provide the key as an argument to the method, and it will remove the corresponding entry.
  1. Efficient memory management: When you delete a key-value pair using the delete() method, the memory occupied by that entry is freed up. This can be useful in scenarios where you need to manage memory efficiently.
  1. No side effects: The delete() method only removes the specified key-value pair from the Map object. It does not affect any other entries or modify the structure of the Map. This can be advantageous when you want to remove a specific entry without impacting the rest of the map.

Cons:

  1. No return value: One potential drawback of the delete() method is that it does not return the deleted value. If you need to retrieve the value before deleting, you would need to use the get() method to retrieve the value before calling delete(). This can lead to additional code complexity and potential performance overhead.
  1. Limited use cases: The delete() method is specifically designed to remove a single key-value pair from the Map object. If you need to perform more complex operations, such as deleting multiple entries based on certain conditions, you might need to use other methods or techniques.

Conclusion

We discussed the Map object and how to use it in your code. The JavaScript Map object is an inbuilt data structure type which helps you to hold an array of values. The main difference between Map and Set is that Map has a key as well as a value, whereas Set only has a value. In JavaScript, the Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value

Solving Leetcode 38. Count and Say

0

In Leetcode 38: Count and Say, we are given a string of letters and we need to count how many times each letter appears and say it out loud. This problem can be solved in a few different ways, but we will code two different solutions here. First, we will solve it with JavaScript and then with Java. Let’s get started!

Explaining the Question

Leetcode 38: Count and Say is asking us to take a string of letters and count the number of times each letter appears. We need to return the sequence, saying out loud the numbers each time a letter appears in order.

For example, let’s say our input is “abc”. In this case, we would say “1a1b1c” as the output. This means that our string contains one ‘a’, one ‘b’, and one ‘c’.

Ways to solve Leetcode 38

To solve the Leetcode 38 problem in JavaScript, we can use a combination of for-loops and objects to keep track of how many times each letter appears. We will create an empty object and then use a for-loop to iterate over each character in the string. If the character exists in the object, we will increment its value by one, otherwise we will set it to 1. After our loop is complete, we can build up our string saying out loud each time a letter appears by accessing the object properties.

To solve Leetcode 38 in Java, we can use a HashMap to keep track of how many times each letter appears. We will iterate over the string, and if the character already exists in our HashMap, then we will increment its value by one. Otherwise, we will set it to one. After the loop is complete, we can build up our output string saying out loud each time a letter appears by accessing the Map entries.

Most Optimal Solution

The most optimal solution for Leetcode 38 is to use a HashMap in Java. This is because HashMaps are faster than objects when it comes to searching and inserting values, making them better suited for this task. We can also do this in JavaScript by using an object, or built in Map data structures.

Coding in JavaScript using Map():

var countAndSay = function(n) {
    let map = new Map()
    map.set(1, "1")
    map.set(2, "11")
    map.set(3, "21")
    map.set(4, "1211")
    map.set(5, "111221")

    if (n <= 5) {
        return map.get(n)
    }

    for (let i = 6; i <= n; i++) {
        let prev = map.get(i - 1)
        let newNum = ""
        let count = 1
        for (let j = 0; j < prev.length; j++) {
            if (prev[j] === prev[j + 1]) {
                count += 1
            } else {
                newNum += `${count}${prev[j]}`
                count = 1
            }
        }
        map.set(i, newNum)
    }
    return map.get(n)
    
};

Code in Java using HashMap:

public String countAndSay(int n) {
               //edge case
       if(n <= 0){
           return "";
       }
       //use hashmap to store the previous result
       HashMap<Integer, String> map = new HashMap<>();
       // put the first result in the hashmap
       map.put(1, "1");
       
       //start from 2 because we already put 1 in the map
       for(int i = 2; i <= n; i++){
           //get the previous result from the map
           String prev = map.get(i - 1);
           //the current result
           String curr = "";
           //the count of the current digit
           int count = 1;
           //the current digit
           char say = prev.charAt(0);
           
           for(int j = 1; j < prev.length(); j++){
               //if the current digit is equal to the previous digit, increment the count
               if(prev.charAt(j) == say){
                   count++;
               }else{
                   //if the current digit is not equal to the previous digit,
                   //append the count of the previous digit and the digit to the current result
                   curr += count;
                   curr += say;
                   //set say to be the current digit
                   say = prev.charAt(j);
                   //reset the count
                   count = 1;
               }
           }
           // append the last digit
           curr += count;
           curr += say;
           // put the current result in the map
           map.put(i, curr);
       }
       
       //return the result
       return map.get(n);
   }
       

In Leetcode 38: Count and Say, we are given a string of letters and asked to count how many times each letter appears in the string. We can solve this problem in JavaScript with objects or with Java using HashMaps. The most optimal solution is to use a HashMap as it is faster than an object when searching for and inserting values.

After understanding the question and coding the solution in either JavaScript or Java, Leetcode 38: Count and Say can be solved!

Solving Leetcode 152. Maximum Product Subarray

0

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Explanation:

Given an array nums of integers, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.

Solution

We can keep track of the maximum and minimum product at each index i. Then, at each index i, we update the maximum and minimum product by taking the maximum and minimum of the previous maximum and minimum, and the current element. The maximum product will be the maximum of the current maximum and minimum products.

Code in JavaScript:

var maxProduct = function(nums) {
    if (nums.length === 0) return 0;
    
    let max = nums[0];
    let min = nums[0];
    let res = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        let currMax = Math.max(max * nums[i], min * nums[i], nums[i]);
        let currMin = Math.min(max * nums[i], min * nums[i], nums[i]);
        res = Math.max(res, currMax);
        max = currMax;
        min = currMin;
    }
    
    return res;
};


Essentially what we do is keep track of the maximum and minimum product at each index i. Then, at each index i, we update the maximum and minimum product by taking the maximum and minimum of the previous maximum and minimum, and the current element. The maximum product will be the maximum of the current maximum and minimum products.

Solving Leetcode 74. Search a 2D Matrix

0

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true

Basically what its asking is given a 2D matrix of integers, find whether the target is present in the matrix or not. You can solve this problem using either a binary search or a linear search. 1. Binary search: First, find the row where the target is likely to be located using binary search. Then, do a linear search in that row to find the target.

2. Linear search: Simply scan through the matrix until you find the target.

The binary search approach is more optimal, as it has a time complexity of O(log(m) + log(n)), while the linear search approach has a time complexity of O(m * n). This work because the matrix is sorted.

First, we need find the row where the target is likely to be located using binary search. Then, do a linear search in that row to find the target.

We can start by finding the midpoint of the matrix. If the target is less than the element at the midpoint, search the left half of the matrix. If the target is greater than the element at the midpoint, search the right half of the matrix. Repeat this process until you find the row where the target is likely to be located. How do you do the second part? Once you have found the row where the target is likely to be located, you can do a linear search in that row to find the target. Start at the beginning of the row and scan through until you find the target or reach the end of the row.

Code in JavaScript:

var searchMatrix = function(matrix, target) {
          let row = 0;
        let col = matrix[0].length - 1;
        
        while(row < matrix.length && col >= 0) {
            if(matrix[row][col] === target) {
                return true;
            } else if(matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
};

Code in Java:

public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;
        int i = 0;
        int j = col-1;
        while(i<row && j>=0){
            if(matrix[i][j] == target){
                return true;
            }
            else if(matrix[i][j] > target){
                j--;
            }
            else{
                i++;
            }
        }
        return false;
    }

Working with 2D Arrays in JavaScript

0

Summary: in this tutorial, you will learn how to work with a JavaScript 2D array and manipulate its elements effectively.

Introduction to 2D arrays

What is a 2D array and how is it different from a 1D array?

A 2D array is an array of arrays, meaning it is a collection of data items organized in rows and columns. It is different from a standard 1D array in that a 1D array holds a single row of data, whereas a 2D array can hold multiple rows of data. It also allows for easier searching for specific pieces of data, and address calculation is done by multiplying the size of each element with the index of the array.

How to create 2d array in JavaScript?

In JavaScript you can create one by using an array of arrays. The elements of a 2D array are accessed by using two indices, one for the row and one for the column. is there native 2d arrays in JavaScript?

Multidimensional arrays are not directly provided in JavaScript. If we want to use anything which acts as a multidimensional array then we need to create a multidimensional array by using another one-dimensional array. So multidimensional arrays in JavaScript is known as arrays inside another array. We need to put some arrays inside an array, then the total thing is working like a multidimensional array. The array, in which the other arrays are going to insert, that array is use as the multidimensional array in our code.

const arr = [
  ['John', 'Smith', '123 Main St.', '555-555-1212'],
  ['Jane', 'Doe', '456 Maple Rd.', '555-555-3434'],
  ['Mike', 'Jones', '789 Elm St.', '555-555-5678']
];
console.log(arr);

There are a number of important methods in 2d arrays, including:

Getting the dimensions

There is no built-in method in JavaScript to get the dimensions of an array, but it is possible to create a custom function to do this:

function getDimensions(arr) {
    var dimensions = [];
    var current = arr;
    while (true) {
        dimensions.push(current.length);
        if (Array.isArray(current[0])) {
            current = current[0];
        } else {
            break;
        }
    }
    return dimensions;
}
const args = [
  ['John', 'Smith', '123 Main St.', '555-555-1212'],
  ['Jane', 'Doe', '456 Maple Rd.', '555-555-3434'],
  ['Mike', 'Jones', '789 Elm St.', '555-555-5678']
];

const dem = getDimensions(args);
//[3,4]. This is a 3x4 matrix
console.log(dem)

Looping through 2d array

//Looping through matrix and consoling out values
arr.forEach((element) =>{
  element.forEach((number) =>{
      console.log(number);
  });
});

Removing elements from the JavaScript multidimensional array

Example in JavaScript

var arr = [[1,2,3,4], [5,6,7]];

arr[0].splice(1,1); // will remove 2 from arr[0]
arr[1].splice(0,2); // will remove 5,6 from arr[1]

console.log(arr); // outputs [ [ 1, 3, 4 ], [] ]
// 1
// 2
// 3
// 4
// 5
// 6
// 7
// 8
// 9
// 10
// 11
// 12
// 13
// 14
// 15
var arr = [[1,2,3,4], [5,6,7]];
 
arr[0].splice(1,1); // will remove 2 from arr[0]
arr[1].splice(0,2); // will remove 5,6 from arr[1]
 
console.log(arr); // outputs [ [ 1, 3, 4 ], [] ]

How to access and modify elements in a 2D array.

To access and modify elements in a 2D array in JavaScript, one can use the length property of the array to access the last element[1], as well as the isArray() function to determine if an array is an array.

For example, to access the element at row 0, column 2, one could use the following code:

if (Array.isArray(matrix) && matrix.length > 0) {
  const element = matrix[0][2];
  // do something with element
}

Additionally, one can use the fill() and filter() functions to fill and filter elements in an array respectively. To create a 2D array, one can insert arrays into another array.

For example, to create a 3×3 matrix, one could use the following code:

let matrix = [];
for (let i = 0; i < 3; i++) {
  let row = [];
  for (let j = 0; j < 3; j++) {
    row.push(i * 3 + j);
  }
  matrix.push(row);
}

Common operations on 2D arrays, such as transposing, flipping, or rotating the array.

Transposing

Swapping the rows and columns of a 2D array, so that the row elements become the column elements and vice versa.

// Transpose
function transpose(arr) {
  let row = arr.length;
  let col = arr[0].length;
  let result = [];
  for(let i = 0; i < col; i++) {
    let newArr = [];
    for(let j = 0; j < row; j++) {
      newArr.push(arr[j][i]);
    }
    result.push(newArr);
  }
  return result;
}

Flipping:

Flipping a 2D array along its horizontal or vertical axis, so that the elements in the array are mirrored.

// Flip Vertical
function flipVertical(arr) {
  let row = arr.length;
  let col = arr[0].length;
  for(let i = 0; i < row; i++) {
    for(let j = 0; j < col / 2; j++) {
      let temp = arr[i][j];
      arr[i][j] = arr[i][col - 1 - j];
      arr[i][col - 1 - j] = temp;
    }
  }
  return arr;
}

Rotating

Rotating a 2D array by 90, 180, or 270 degrees, so that the elements in the array are rearranged accordingly.

// Rotate 90
function rotate90(arr) {
  let row = arr.length;
  let col = arr[0].length;
  let result = [];
  for(let i = 0; i < col; i++) {
    let newArr = [];
    for(let j = 0; j < row; j++) {
      newArr.push(arr[row - 1 - j][i]);
    }
    result.push(newArr);
  }
  return result;
}

Best practices for working with 2D arrays in JavaScript

Such as choosing an appropriate data structure for your use case, or optimizing the performance of your code. Best practices for working with 2D arrays in JavaScript include creating an array of one-dimensional array objects, using the special syntax for a 2D array, and using methods such as creating an array of arrays or a matrix of rows and columns.

Creating an array of one-dimensional array objects

let array2D = [];

for (let i = 0; i < 3; i++) {
  array2D[i] = [];
  for (let j = 0; j < 3; j++) {
    array2D[i][j] = i + j;
  }
}

console.log(array2D); // [[0, 1, 2], [1, 2, 3], [2, 3, 4]]

In this example, we create an empty array called array2D and then use a nested loop to populate it with one-dimensional array objects. The outer loop runs 3 times, and the inner loop runs 3 times for each iteration of the outer loop, resulting in a total of 9 elements in the 2D array.

Using the special syntax for a 2D array

let array2D = [  [0, 1, 2],
  [3, 4, 5],
  [6, 7, 8]
];

console.log(array2D); // [[0, 1, 2], [3, 4, 5], [6, 7, 8]]

In this example, we use the special syntax for creating a 2D array by enclosing each row of the array in brackets and separating them with commas.

Creating an array of arrays:

let array1D = [0, 1, 2, 3, 4, 5, 6, 7, 8];
let array2D = [];

while (array1D.length) {
  array2D.push(array1D.splice(0, 3));
}

console.log(array2D); // [[0, 1, 2], [3, 4, 5], [6, 7, 8]]

In this example, we start with a one-dimensional array and use the push and splice methods to create an array of arrays. We use the push method to add elements to the array2D array, and we use the splice method to remove elements from the array1D array and add them to the array2D array in groups of 3.

Creating a matrix of rows and columns

let rows = 3;
let columns = 3;
let array2D = [];

for (let i = 0; i < rows; i++) {
  array2D[i] = [];
  for (let j = 0; j < columns; j++) {
    array2D[i][j] = i + j;
  }
}

console.log(array2D); // [[0, 1, 2], [1, 2, 3], [2, 3, 4]]

In this example, we use a nested loop to create a matrix of rows and columns. The outer loop runs 3 times, and the inner loop runs 3 times for each iteration of the outer loop, resulting in a 2D array with 3 rows and 3 columns.

Conclusion

2D and multi-dimensional arrays are important because they allow you to store and manipulate data in a structured and organized way. They are particularly useful when you need to work with data that has multiple dimensions, such as a spreadsheet or a grid of values.

For example, you might use a 2D array to store a table of data with rows and columns, where each element in the array represents a cell in the table. You could use a multi-dimensional array to store data for a 3D model or a set of images with multiple channels (such as red, green, and blue channels for a color image).

In addition to organizing data, 2D and multi-dimensional arrays can also make it easier to perform operations on the data. For example, you can use loops to iterate over the elements of the array and apply a certain operation to each element, or you can use built-in methods such as map and filter to manipulate the data in a more concise and efficient way.

Overall, 2D and multi-dimensional arrays are a powerful tool for storing and manipulating data in JavaScript and other programming languages.

Questions involving Multidimensional arrays:

5 Essential Data Structures and how to use them in JavaScript.

0

As a web developer, it is important to have a strong understanding of data structures. Data structures are used to organize, store, and retrieve data. They are the foundation upon which algorithms are built. There are many different types of data structures, but in this blog post, we will focus on seven essential data structures that every web developer should know.

Data Structure 1: Arrays

Arrays are one of the most basic data structures. An array is simply a collection of values of the same type. The values can be accessed by their index, which is their position in the array. Arrays are declared using square brackets, and values are separated by commas. For example:

const arr = [1, 2, 3];
console.log(arr[1]);   // 2

Array as a Stack:

Arrays can be used as stacks. Arrays can be used as stacks because they maintain the order of insertion. This means that the last element added to the array will be the first element removed (LIFO).

const stackExmaple = () => {
  const stack = [];
  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.push(5);
  console.log(stack);
  stack.pop();
  stack.pop();
  console.log(stack);
};
stackExmaple();

Array as a queue:

Arrays can also be used as queues. In a queue, elements are added to the end of the array and removed from the front. This is called a First-In-First-Out (FIFO) structure.

const queueExample = () => {
    const queue = [];
    queue.push(1);
    queue.push(2);
    queue.push(3);
    queue.push(4);
    queue.push(5);
    console.log(queue);
    queue.shift();
    queue.shift();
    console.log(queue);
    }
queueExample();

Data Structure 2: Maps

Objects in JavaScript

The Object type represents one of JavaScript’s data types and is used to store various keyed collections and more complex entities. Objects can be created using the Object() constructor or the object initializer / literal syntax({}).

Nearly all objects in JavaScript are instances of Object; a typical object inherits properties (including methods) from Object.prototype, although these properties may be shadowed (a.k.a. overridden). However, an Object may be deliberately created for which this is not true (e.g. by Object.create(null)), or it may be altered so that this is no longer true (e.g. with Object.setPrototypeOf).

Changes to the Object prototype object are seen by all objects through prototype chaining, unless the properties and methods subject to those changes are overridden further along the prototype chain. This provides a very powerful although potentially dangerous mechanism to override or extend object behavior.

Objects are important in web development because they allow developers to store data in a structured way and access it easily. They also provide a way to create custom functionality that can be reused across different web applications and components.

const obj = {
    name: "John",
    age: 30,
    city: "New York"
}

Map Object

A map is a data structure that stores key-value pairs. A map is different than an object because a map can store keys of any type, whereas an object can only store keys of the type string. In general, the Map object may be more suitable for applications that require a large number of key-value pairs, or that require complex keys (such as objects or arrays).

var map = new Map();
map.set([1,2,3], 'foo');
console.log(map.get([1,2,3])); // 'foo'

Data Structure 3: Linked List.

A linked list is a linear data structure in which elements are not stored in contiguous memory locations. It consists of a group of nodes, each of which has its own data and address to the next node. In an array, the elements are indexed, so you can instantly get to an element, but in a linked list, you have to start with the head and work your way through until you get to the desired element. The advantage of the linked list is that insertion and deletion are easier than with an array, because the elements in an array are stored in a consecutive location. Linked lists also have efficient memory consumption, because the size of the linked list can grow or shrink according to our requirements.

Linked List Tradeoffs:

There is no one method that is suited for all circumstances in computer programming and design. Depending on the situation, a linked list data structure might work well or cause problems. Some common tradeoffs involving linked list structures are listed below.

Linked lists have several advantages over dynamic arrays, including faster insertion and deletion of elements. With a reference to the desired node, insertion or deletion can be done in constant time. Without this reference, it would be a O(n) operation. Additionally, dynamic arrays can become fragmented over time, which impacts the performance of iteration.

Use Cases:

Linked lists are often used to implement stacks and queues. They can also be used to implement graphs and trees.

Here is a basic Linked List in JavaScript:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null,
    };
    this.tail = this.head;
    this.length = 1;
  }
  append(value) {
    const newNode = new Node(value);
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }
  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
  }
  printList() {
    const array = [];
    let currentNode = this.head;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next;
    }
    return array;
  }
  insert(index, value) {
    //check params
    if (index >= this.length) {
      return this.append(value);
    }
    const newNode = new Node(value);
    const leader = this.traverseToIndex(index - 1);
    const holdingPointer = leader.next;
    leader.next = newNode;
    newNode.next = holdingPointer;
    this.length++;
    return this.printList();
  }
  traverseToIndex(index) {
    //check params
    let counter = 0;
    let currentNode = this.head;
    while (counter !== index) {
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
  remove(index) {
    //check params
    const leader = this.traverseToIndex(index - 1);
    const unwantedNode = leader.next;
    leader.next = unwantedNode.next;
    this.length--;
    return this.printList();
  }
}

Other Linked List problems: Add Two Numbers

Data Structure 4: Trees:

Probably one of the most sought after data structures in computer science. A tree is a data structure that represents a hierarchical tree structure. It is composed of nodes, and each node can have one or more child nodes. The root node is the top node in the tree and does not have a parent node. Trees are useful for storing data that can be logically organized in a hierarchical manner.

There are many types of trees. Some examples.

1.) Binary Tree
2.) Binary Search Tree
3.) AVL Tree
4.) Balanced tree
5.) Red black tree
6.) 2-3 tree
7.) N-ary tree

If you’re a beginner we recommend focusing on 1 & 2 only. To implement a binary tree, read our post here

Data Structure 5: Graphs:


A graph data structure consists of a finite set of vertices, along with a set of unordered pairs of these vertices for an undirected graph, or a set of ordered pairs for a directed graph. These pairs are known as edges, and for a directed graph they may also be called arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate an edge value with each edge, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Source: Wikipedia

There are two common types of graphs:

Undirected Graphs: A graph in which edges have no direction. This means that each edge can be traversed in both directions

Directed Graphs: A directed graph is a graph in which edges have a direction. This means that each edge can only be traversed in one direction

Use Cases

– To represent a network of roads or a computer network

– To represent a social network

– To represent a database of relationships

Graph in JavaScript:

Undirected Graph:
Directed Graph:
var underectedGraph = {
    "a": ["c"],
    "b": ["c", "e"],
    "c": ["a", "b", "d", "e"],
    "d": ["c"],
    "e": ["c", "b"],
    "f": []
}

// code an directed graph in JavaScript

var directedGraph = {
    "a": ["c"],
    "b": ["c", "e"],
    "c": ["d"],
    "d": ["c"],
    "e": ["c"],
    "f": []
}

For more resources check out our blog and connect with us on Twitter.

Solving Leetcode 2. Add Two Numbers

0

From Leetcode.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

– We are given two non-empty linked lists representing two non-negative integers.

– The digits are stored in reverse order and each of the linked list’s nodes contain a single digit.

– We need to add the two numbers and return it as a linked list.

– We may assume that the two numbers do not contain any leading zero, except for the number 0 itself.

What is the question (Leetcode 2) asking?

To give you an example, given the two linked lists: 7->1->6 + 5->9->2 The sum is: 7->1->6->9 Explanation: 342 + 295 = 637.

How would you solve this problem?

There are many ways to solve this problem. One way would be to iterate through both lists, adding the values of each node together. If the sum of the two nodes is greater than 10, you would need to carry over the 1 to the next node. Another way to solve this problem would be to convert both linked lists into integers, add the integers together, and then convert the sum into a linked list.

The most optimal solution depends on the situation. If the linked lists are very long, it may be more efficient to convert them into integers and add the integers together. This is because adding two integers is a relatively simple operation, and it would avoid having to iterate through a long linked list. If the linked lists are not very long, it may be more efficient to iterate through both lists, adding the values of each node together. This is because iterating through a linked list is a relatively simple operation, and it would avoid having to convert the linked lists into integers.

I prefer the solution of iterating through both lists, adding the values of each node together. I prefer this solution because it is a relatively simple operation, and it would avoid having to convert the linked lists into integers.

Leetcode 2 Code solution.

Here is the code in JavaScript

var addTwoNumbers = function(l1, l2) {
    // create a new linked list to store the sum
    let sumList = new ListNode(0);
    let current = sumList;
    
    // create a carryover variable to keep track of values >= 10
    let carryover = 0;
    
    // iterate through both lists, adding the values of each node together
    while (l1 || l2) {
        
        // get the values of the current nodes in each list
        let val1 = l1 ? l1.val : 0;
        let val2 = l2 ? l2.val : 0;
        
        // add the values together, plus any carryover from the previous sum
        let sum = val1 + val2 + carryover;
        
        // if the sum is >= 10, set the carryover to 1
        if (sum >= 10) {
            carryover = 1;
        } else {
            // otherwise, reset the carryover to 0
            carryover = 0;
        }
        
        // create a new node with the sum (minus any carryover)
        let newNode = new ListNode(sum % 10);
        
        // set the current node's next value to the new node, and advance the current node
        current.next = newNode;
        current = newNode;
        
        // advance l1 and l2 to the next nodes
        if (l1) {
            l1 = l1.next;
        }
        if (l2) {
            l2 = l2.next;
        }
    }
    
    // if there is a carryover after iterating through both lists, add a new node with the carryover
    if (carryover === 1) {
        let newNode = new ListNode(1);
        current.next = newNode;
    }
    
    // return the sum list
    return sumList.next;
    
    
};

The time complexity is O(n), where n is the length of the longer linked list. The space complexity is O(n), where n is the length of the sum linked list.

The most optimal solution to this problem depends on the situation. If the linked lists are very long, it may be more efficient to convert them into integers and add the integers together. However, if the linked lists are not very long, it may be more efficient to iterate through both lists, adding the values of each node together. Above we showed the solution of iterating through both lists, adding the values of each node together, this is the simple operation, and we avoided having to convert the linked lists into integers.

Solving Leetcode 98. Validate Binary Search Tree

0

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
Input: root = [2,1,3] Output: true


Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. A single node tree is a BST

Code in JavaScript

var isValidBST = function(root) {
    const isValid = (root, low, high) => {
        if (!root) {return true}
        if (root.val <= low || root.val >= high) { return false }
        if (root.left && root.val <= root.left.val ) { return false }
        if (root.right && root.val >= root.right.val ) { return false }
        
        return isValid(root.left, Math.min(root.val, low), Math.min(root.val, high)) && isValid(root.right, Math.max(root.val, low), Math.max(root.val, high))
    }
    return isValid(root, -Infinity, Infinity)
};

Code in Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        res = []
        self.inOrder(root, res)
        return res == sorted(res) and len(res) == len(set(res))
        
    def inOrder(self, root, res):
        if not root: return []
        l = self.inOrder(root.left, res)
        if l:
            res.extend(l)
        res.append(root.val)
        r = self.inOrder(root.right, res)
        if r:
            res.extend()