Press "Enter" to skip to content

Posts tagged as “javascript”

List some handy functions in Javascript

Array.isArray()

The isArray() method checks if the specified parameter is an array. Returns a true if is an array.

Array.isArray('string'); // false
Array.isArray(123); // false
Array.isArray(['I am Array']); // true
Array.isArray({key: value}); // false

Array.find()

The find() method is used to get the value of the first element in the array that satisfies the provided condition.

array.find(function(currentValue, index, arr),thisValue)
['apple','bannna','pear'].find(function(name) {
    return name === 'apple';
});

// or ES6 arrow functions
['apple','bannna','pear'].find(name => name === 'apple');

const people = [
  { name: 'Tom', username: 'tom2020' },
  { name: 'Jason', username: 'jason009' },
  { name: 'Rose', username: 'rose123' },
];
people.find(person => person.name === 'Tom');
// output: { name: 'Tom', username: 'tom2020' }

// find array item with index of 3
const atIndex = items.find(function(element, index){
  return index === 3
})

// display array item found
console.log(atIndex)

Array.filter()

The filter() method returns an array containing elements of the target array that match the set test. The callback function containing a test is passed as an argument to the filter method.

const filteredArray = targetArray.filter(callbackFunction(element[,index[,array]])[, thisArg])
const names = ['Kevin', 'Peter', 'Jason', 'Epso', 'Hang'];

// Filter the array for names having 'o'
const nameHasO = names.filter(name => name.includes('o'));

Another good example: Boolean() is also a function that returnstrue when true,

or false when if the value is omitted or is 0-0nullfalseNaNundefined, or the empty string ("").

var array = [1, 2, "b", 0, {}, "", NaN, 3, undefined, null, 5];

var newArray = array.filter(Boolean);  // [1, 2, "b", {}, 3, 5]; 

Array.every()

The every method checks that each element in an array passes a set test. This method will return true if all the elements pass the test. Otherwise returns false.

array.every(callback(element[, index[, array]])[, thisArg])
const students = [{name: 'Tom', score: 70} , {name: 'Jason', score: 80}, {name: 'King', score: 95}];

// Test callback function
const studentsPassed = students.every(student => student.score >= 60);

console.log(studentsPassed) // Output: true

Array.some()

This method checks if any of the elements contained in an array passes a set test. If at least one of the elements passes this test, true is returned. This method only returns a Boolean.

const bool = array.some(callback(element[, index[, array]])[, thisArg])
const cities = [{city: 'Oakland', zipCode: '94602'}, {city: 'San Francisco'}];

// Verify properties of an object
let hasZipCode = cities.some(function(city){
  return !!city.zipCode;
})
console.log(hasZipCode); // Output: true

Array.toString() 

This method returns a String representation of the elements within the calling array. This method is somewhat similar to the join(',') method.

['Hello', 'World!'].toString()
// 'Hello,World!'
['1', '2', '3', '4'].toString()
// '1,2,3,4'

Array slice() vs. splice() vs. split()

According to the documentation: The slice() method returns a shallow copy of a portion of an array into a new array object selected from begin to end (end not included). The original array will not be modified.

Argument 1: Required. An integer that specifies where to start the selection (The first element has an index of 0). Use negative numbers to select from the end of an array.

Argument 2: Optional. An integer that specifies where to end the selection. If omitted, all elements from the start position and to the end of the array will be selected. Use negative numbers to select from the end of an array.

let array = [1,2,3,4,5]
console.log(array.slice(2));
// output: [3, 4, 5], returned selected element(s).
 
console.log(array.slice(-2));
// output: [4, 5], returned selected element(s).
console.log(array);
// output: [1, 2, 3, 4, 5], original array remains intact.
 
           -5 -4 -3 -2 -1
            |  |  |  |  |
let array2=[6, 7, 8, 9, 10];
             |  |  |  |  |
             0  1  2  3  4
console.log(array2.slice(2,4));
// output: [8, 9]
 
console.log(array2.slice(-2,4));
// output: [9]
 
console.log(array2.slice(-3,-1));
// output [8, 9]

The splice() method changes an existing array by removing, adding and/or replacing specified elements from it. The method mutates the original array and returns an array of all elements removed from the array. An empty array is returned if no elements are removed.

  • The splice() method returns the removed item(s) in an array and slice() method returns the selected element(s) in an array, as a new array object.
  • The splice() method changes the original array and slice() method doesn’t change the original array.
  • The splice() method can take n number of arguments:
let array = [1,2,3,4,5];
console.log(array.splice(2));
// output: [3, 4, 5], returned removed item(s) as a new array object.
 
console.log(array);
// output: [1, 2], original array altered.
 
var array2 = [6,7,8,9,10];
console.log(array2.splice(2,1));
// output: [8]
 
console.log(array2.splice(2,0));
// output: [] , no item(s) selected means no item(s) removed.
 
console.log(array2);
// output: [6,7,9,10]
 
let array3 = [11,12,13,14,15];
console.log(array3.splice(2,1,"apple","banana"));
// output: [13]
 
console.log(array3);
// output: [11, 12, "apple", "banana", 14, 15]
 
           -5 -4 -3 -2 -1
            |  |  |  |  |
var array4=[16,17,18,19,20];
             |  |  |  |  |
             0  1  2  3  4
 
console.log(array4.splice(-2,1,"string"));
// output:  [19]
 
console.log(array4);
// output: [16, 17, 18, "string", 20]

Split ( )

Slice( ) and splice( ) methods are for arrays. The split( ) method is used for strings. It divides a string into substrings and returns them as an array. Syntax:

string.split(separator, limit);

  • Separator: Defines how to split a string… by a comma, character etc.
  • Limit: Limits the number of splits with a given number
let str = "How are you doing today?";
let newStr = str.split(" ", 3);
// newStr: ['How','are','you']

This page will be updated every time if I find something interesting.

Project Euler #1 – Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

console.log([...Array(1000).keys()]
    .filter(n => n % 3 === 0 || n % 5 === 0)
    .reduce((acc, n) => acc + n));

LeetCode 912. Sort an Array (javascript)

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

  • 1 <= nums.length <= 50000
  • -50000 <= nums[i] <= 50000

Idea:

Use Merge Sort Template

Solution:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    if (nums === null || nums.length === 0) return;
    let temp = [];
    mergeSort(nums, 0, nums.length - 1, temp);
    return nums;
};

function mergeSort(nums, start, end, temp) {
    if (start >= end) return;
    // deal with first half
    mergeSort(nums, start, Math.floor((start + end) / 2), temp);
    // deal with second half
    mergeSort(nums, Math.floor((start +end) / 2) + 1, end, temp);
    // merge
    merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
    let mid = Math.floor((start + end) / 2);
    let l_index = start;
    let r_index = mid + 1;
    let index = start;
    while (l_index <= mid && r_index <= end) {
        if (nums[l_index] < nums[r_index]) {
            temp[index++] = nums[l_index++];
        } else {
            temp[index++] = nums[r_index++];
        }
    }
    while (l_index <= mid) {
        temp[index++] = nums[l_index++];
    }
    while (r_index <= end) {
        temp[index++] = nums[r_index++];
    }
    for (let i = start; i <= end; i++) {
        nums[i] = temp[i];
    }
}

LeetCode 129. Sum Root to Leaf Numbers (javascript)

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

  • For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers.

leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.

Idea:

Use DFS Template

Solution 1:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    if (root === null) return;
    let res = [];
    let cur = [];
    dfs(root, res, cur);
    let sum = 0;
    for (let num of res) {
        sum += num;
    }
    return sum;
};

function dfs(root, res, cur) {
    // exit recursion:
    if (root === null) return;
    // found leaf, save the number
    if (root.left === null && root.right === null) {
        cur.push(root.val);
        res.push(parseInt(cur.join('')));
        cur.pop();
        return;
    }
    
    // possible solution
    if (root !== null) {
        cur.push(root.val);
        dfs(root.left, res, cur);
        dfs(root.right, res, cur);
        cur.pop();
    }
    return;
}

Solution 2: (Version 2)

var sumNumbers = function(root) {
    if (root === null) return;
    let res = [0];
    let cur = [0];
    dfs(root, res, cur);
    return res[0];
};

function dfs(root, res, cur) {
    // exit recursion:
    if (root === null) return;
    // found leaf, save the number
    if (root.left === null && root.right === null) {
        cur[0] = cur[0] * 10 + root.val;
        res[0] += cur[0];
        cur[0] = (cur[0] - root.val) / 10;
        return;
    }
    
    // possible solution
    if (root !== null) {
        cur[0] = cur[0] * 10 + root.val;
        dfs(root.left, res, cur);
        dfs(root.right, res, cur);
        cur[0] = (cur[0] - root.val) / 10;
    }
    return;
}

LeetCode 198. House Robber (javascript)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Idea:

Dynamic Programing

Try to look for a pattern, see comments in the code.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    // one house
    if (nums.length === 1) return nums[0];
    
    // dp[i] = max money can be taken after visited i houses
    let dp = new Array(nums.length);
    dp[1] = nums[0];
    dp[2] = Math.max(nums[0], nums[1]);
    // two houses
    if (nums.length === 2) return dp[2];
    
    // more houses - try to look for a pattern
    // dp[3] = Math.max(dp[2], dp[1] + nums[2]);
    // dp[4] = Math.max(dp[3], dp[2] + nums[3]);
    // ...
    for (let i = 3; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }
    return dp[nums.length];
};

LeetCode 167. Two Sum II – Input array is sorted (javascript)

Given an array of integers numbers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]

Constraints:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in increasing order.
  • -1000 <= target <= 1000
  • Only one valid answer exists.

Solution 1: (Two pointer)

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let l = 0;
    let r = numbers.length - 1;
    while (l < r) {
        let sum = numbers[l] + numbers[r];
        if (sum === target) break;
        else if (sum > target) r--;
        else l++;
    }
    // this question use 1-indexed
    return [l + 1, r + 1];
};

Solution 2: (Hash table)

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

LeetCode 74. Search a 2D Matrix (javascript)

Write an efficient algorithm that searches for a value in an m x n 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.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

Solution 1: (DFS)

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    return dfs(matrix, target, 0, 0);
};

function dfs(matrix, target, x, y) {
    let rows = matrix.length;
    let cols = matrix[0].length;
    
    // exit recursion condition, reach to the end;
    if (y === rows) return false;
    
    // traverse from left to right, then next row
    let nextX = (x + 1) % cols;
    let nextY = nextX === 0 ? y + 1 : y;

    // found return true or not found, DFS next element
    if (matrix[y][x] === target) 
        return true;
    else
        return dfs(matrix, target, nextX, nextY);

    return false;
}

Solution 2: (Binary Search) Better and Faster!

  • Time complexity: O(log(mn))
  • Space complexity: O(1)
var searchMatrix = function(matrix, target) {
    let cols = matrix[0].length;
    // 	treat 2D as 1D, use binary search
    let l = 0;
    let r = matrix.length * cols;
    while (l < r) {
        let mid = l + Math.floor((r - l) / 2);
        let row = Math.floor(mid / cols);
        let col = mid % cols;
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return false;
};

LeetCode 37. Sudoku Solver (javascript)

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:


Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

Idea:

Create 3 tracking arrays:
  1 - 9 occur once in whole row, whole col, whole box.
  [ith row][number] [ith col][number] [ith box][number]
  ex: [ith row][N] = 1 means ith row already use number N
DFS/Backtracking
  Travese the board from left to right, row by row
  Try to fill 1-9, success return,
      if not success, recover data and try next element

Solution:

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    // 1 - 9 occur once in whole row, whole col, whole box
    // [ith row][number] [ith col][number] [ith box][number]
    // ex: [ith row][N] = 1 means ith row already use number N
    let rows = Array.from(new Array(9), () => new Array(10).fill(0));
    let cols = Array.from(new Array(9), () => new Array(10).fill(0));
    let boxes = Array.from(new Array(9), () => new Array(10).fill(0));
    
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const c = board[i][j];
            if (c !== '.') {
                let num = parseInt(c);
                let bx = Math.floor(j / 3);
                let by = Math.floor(i / 3);
                rows[i][num] = 1;
                cols[j][num] = 1;
                boxes[by * 3 + bx][num] = 1;
            }
        }
    }
    dfs(board, 0, 0, rows, cols, boxes);
};

function dfs(board, x, y, rows, cols, boxes) {
    // exit recursion condition, reach to the end;
    if (y === 9) return true;
    
    // traverse from left to right, then next row
    let nextX = (x + 1) % 9;
    let nextY = nextX === 0 ? y + 1 : y;
    
    // already has number, DFS next element
    if (board[y][x] !== '.') return dfs(board, nextX, nextY, rows, cols, boxes);
    
    // fill number from 1 - 9
    for (let i = 1; i <= 9; i++) {
        let bx = Math.floor(x / 3);
        let by = Math.floor(y / 3);
        let box_index = by * 3 + bx;
        // if not breaking the following 3 rules
        if (!rows[y][i] && !cols[x][i] && !boxes[box_index][i]) {
            // modify, fill the number
            rows[y][i] = 1;
            cols[x][i] = 1;
            boxes[box_index][i] = 1;
            board[y][x] = i.toString();
            // Try to fill next element, if success return true, or recover
            if (dfs(board, nextX, nextY, rows, cols, boxes)) return true;
            // recover data
            board[y][x] = '.';
            boxes[box_index][i] = 0;
            cols[x][i] = 0;
            rows[y][i] = 0;
        }
    }
    return false;
}

LeetCode 200. Number of Islands (javascript)

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

Idea:

Traverse connected components: Use DFS to traverse 4 directions and mark them “0” if found “1”

Solution:

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let row = grid.length;
    if (row === 0) return 0;
    let col = grid[0].length;
    let res = 0;
    for (let x = 0; x < col ; x++) {
        for (let y = 0; y < row; y++) {
            if (grid[y][x] === "1") {
                res++;
                dfs(grid, x, y, col, row);
            }
        }
    }
    return res;
};

var dfs = function(grid, x, y, n, m) {
    // over boundry cases and not "1" => return
    if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] === "0") return;
    
    // already visited mark it "0"
    grid[y][x] = "0";
    // traverse 4 directions if any "1" => mark them "0"
    dfs(grid, x + 1, y, n, m);
    dfs(grid, x - 1, y, n, m);
    dfs(grid, x, y + 1, n, m);
    dfs(grid, x, y - 1, n, m);
}

LeetCode 230. Kth Smallest Element in a BST (javascript)

Given the root of a binary search tree, and an integer k, return the kth (1-indexedsmallest element in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

Idea:

 Recursive Inorder Traversal

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    const nums = [];
    inorder(root, nums);
    return nums[k - 1];
};

function inorder(root, nums) {
    if (root === null) return;
    inorder(root.left, nums);
    nums.push(root.val);
    inorder(root.right, nums);
}