Press "Enter" to skip to content

Posts published in “Algorithms”

LeetCode 154. Find Minimum in Rotated Sorted Array II

By stone on April 28, 2021

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

  • [4,5,6,7,0,1,4] if it was rotated 4 times.
  • [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

Example 1:

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

Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums is sorted and rotated between 1 and n times.

Idea:

Divide and Conquer

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    return searchMin(nums, 0, nums.length - 1);
};

function searchMin(nums, l, r) {
    // exit recursion:
    // only one or two elements in the array
    if (l + 1 >= r)
        return Math.min(nums[l], nums[r]);
    // this array is sorted
    if (nums[l] < nums[r])
        return nums[l];
    
    let mid = l + Math.floor((r - l) / 2);
    return Math.min(searchMin(nums, l , mid), searchMin(nums, mid + 1, r));
}

LeetCode 297. Serialize and Deserialize Binary Tree (javascript)

By stone on April 21, 2021

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000

Idea: (Recursion)

We can encodes the tree to a single string.
// # indicates reach to the leave
Convert above tree to 12##34##56##

Time Complexity O(n)

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    let res = [];
    serializer(root, res);
    return res.join(",");
};

var serializer = function(root, output) {
    if (root === null) {
        output.push("#");
        return;
    }
    output.push(root.val);
    serializer(root.left, output);
    serializer(root.right, output);
}

// Decodes your encoded data to tree.
var deserialize = function(data) {
    data = data.split(",");
    let index = 0;
    
    function deserializer(data) {
        if(index > data.length || data[index] === "#") {
            return null;
        }
        let root = new TreeNode(parseInt(data[index]));
        index++;
        root.left = deserializer(data);
        index++;
        root.right = deserializer(data);
        return root;
    }
    return deserializer(data);
};

LeetCode 279. Perfect Squares (javascript)

By stone on April 21, 2021

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

  • 1 <= n <= 104

Idea: (Dynamic Programing)

  • Time complexity: O(n * sqrt(n))
  • Space complexity: O(n)
dp[i] := return the least number of perfect square numbers that sum to i.
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} and 1 <= j * j <= i ex:[1, 4, 6, 9…]
// For example:
dp[5] = min{
dp[5 – 2*2] + 1 = dp[1] + 1 = (dp[1 – 1*1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1*1] + 1 = dp[4] + 1 = (dp[4 – 1*1] + 1) + 1 = dp[3] + 2 = 
dp[3 – 1*1] + 1 + 2 = dp[2 - 1*1] + 1 + 3 = dp[1 - 1*1] + 1 + 4 = 
dp[0] + 5 = 5
 };
so dp[5] = 2

Solution:

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    // Important: n + 1 length because we use dp[0]
    let dp = new Array(n + 1).fill(Number.MAX_VALUE);
    dp[0] = 0;
    for (let i = 1; i <= n; i++)
        for(let j = 1; j * j <= i; j++)
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    
    return dp[n];
};

LeetCode 977. Squares of a Sorted Array

By stone on April 20, 2021

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in non-decreasing order.

Solution 1: (Quick Sort)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums = nums.map(num => num * num);
    quickSort(nums, 0, nums.length - 1);
    return nums;
};

function quickSort(nums, left, right) {
    let index;
    if (nums.length > 1) {
        // index returned from partition
        index = partition(nums, left, right);
        // more elements on the left side of the pivot
        if (left < index - 1)
            quickSort(nums, left, index - 1);
        // more elements on the right side of the pivot
        if (index < right)
            quickSort(nums, index, right);
    }
    // you can return or not return, 
    // since we change nums, no need to return
    // return nums;
}

function partition(nums, start, end) {
    let l = start, r = end;
    let mid = Math.floor((start + end) / 2);
    let pivot = nums[mid];
    // Important: l <= r not l < r
    while (l <= r) {
        while(nums[l] < pivot)
            l++;
        while(nums[r] > pivot)
            r--;
        if (l <= r) {
            // swap
            [nums[l], nums[r]] = [nums[r], nums[l]];
            l++;
            r--;
        }
    }
    return l;
}

Solution 2: (Merge Sort)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums = nums.map(num => num * num);
    let temp = [];
    mergeSort(nums, 0, nums.length - 1, temp);
    return nums;
};

function mergeSort(nums, start, end, temp) {
    if (start >= end) return;
    let mid =  Math.floor((start + end) / 2);
    mergeSort(nums, start, mid, temp);
    mergeSort(nums, mid + 1, end, temp);
    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 = 0; i <= end; i++)
        nums[i] = temp[i];
}

LeetCode 79. Word Search (javascript)

By stone on April 19, 2021

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Idea:

DFS

Solution:

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    for (let x = 0; x < board[0].length; x++)
        for (let y = 0; y < board.length; y++)
            if (dfs(board, word, 0, x, y)) return true;
    return false;
};

function dfs(board, word, i, x, y) {
    // exit recursion:
    if (x < 0 || y < 0 || x >= board[0].length || y >= board.length || word[i] !== board[y][x])
        return false;
    // found the last letter
    if (i === word.length - 1)
        return true;
    
    let cur = board[y][x];
    // mark it 0 means already visit
    board[y][x] = 0;
    let found = dfs(board, word, i + 1, x + 1, y) || 
                dfs(board, word, i + 1, x - 1, y) ||
                dfs(board, word, i + 1, x, y + 1) ||
                dfs(board, word, i + 1, x, y - 1);
    // recover
    board[y][x] = cur;
    return found;
}

LeetCode 841. Keys and Rooms

By stone on April 18, 2021

There are N rooms and you start in room 0.  Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room. 

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length.  A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0). 

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. The number of keys in all rooms combined is at most 3000.

Idea:

DFS

Solution:

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    let visited = [];
    dfs(rooms, visited, 0);
    return visited.length === rooms.length;
};

function dfs(rooms, visited, roomNum){
    // exit recursion:
    if (visited.includes(roomNum)) return;
    
    visited.push(roomNum);
    // possible solution
    for (let key of rooms[roomNum])
        dfs(rooms, visited, key);
}

LeetCode 108. Convert Sorted Array to Binary Search Tree (javascript)

By stone on April 17, 2021

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in a strictly increasing order.

Idea:

Recursion + Divide and Conquer

Time complexity: O(n)
Space complexity: O(logn)

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 {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    return createBST(nums, 0, nums.length - 1);
};

function createBST(nums, l, r) {
    // exit recursion condition
    if (l > r) return null;
    
    let mid = l + Math.floor((r - l) / 2);
    let root = new TreeNode(nums[mid]);
    root.left = createBST(nums, l, mid - 1);
    root.right = createBST(nums, mid + 1, r);
    return root;
}

LeetCode 99. Recover Binary Search Tree (javascript)

By stone on April 16, 2021

You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Example 1:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

  • The number of nodes in the tree is in the range [2, 1000].
  • -231 <= Node.val <= 231 - 1

Idea:

Because inorder traverse BST, all values are sorted. We can use inorder traversal to find two nodes that have prev.val > root. val and swap them

Time complexity: O(n)
Space complexity: O(height)

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
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    // javascript can't pass value by reference 
    // so pass array object by reference
    let first = [null];
    let second = [null];
    let prev = [null];
    inorder(root, first, second, prev);
    [first[0].val, second[0].val] = [second[0].val, first[0].val];
};

function inorder(root, first, second, prev) {
    // Because inorder traverse BST, all values are sorted.
    // Using inorder traversal to find two nodes that have prev.val > root.val
    if (root === null) return;
    inorder(root.left, first, second, prev);
    if (prev[0] && prev[0].val > root.val) {
        if (first[0] === null) first[0] = prev[0];
        second[0] = root;
    }
    prev[0] = root;
    inorder(root.right, first, second, prev);
}

LeetCode 148. Sort List (javascript)

By stone on April 15, 2021

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

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

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 104].
  • -105 <= Node.val <= 105

Idea:

Merge Sort (use slow and fast pointer to find the middle of the linked list and split them)

Time Complexity: O(nlogn)

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    // empty or one node
    if (head === null || head.next === null) 
        return head;
    let mid = getMid(head);
    let left = sortList(head);
    let right = sortList(mid);
    return merge(left, right);
};

function merge(list1, list2) {
    let newHead = new ListNode();
    let tail = new ListNode();
    tail = newHead;
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
            tail = tail.next; 
        } else {
            tail.next = list2;
            list2 = list2.next;
            tail = tail.next; 
        }   
    }
    tail.next = (list1 !== null) ? list1 : list2;
    return newHead.next;
};

function getMid(head) {
    let slow = head;
    let fast = head;
    let midHead = null;
    while (fast !== null && fast.next !== null) {
        midHead = slow;
        slow = slow.next
        fast = fast.next.next;
    }
    let secondHalf = midHead.next;
    // !!!Important here:
    // disconnect, split them into two lists
    midHead.next = null;
    return secondHalf;
}

Project Euler #1 – Multiples of 3 and 5

By stone on April 14, 2021

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));