Press "Enter" to skip to content

Posts published in “Algorithms”

LeetCode 1143. Longest Common Subsequence (javascript)

Given two strings text1 and text2, return the length of their longest common subsequenceIf there is no common subsequence, return 0.

subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

  • For example, "ace" is a subsequence of "abcde".

common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English characters.

Idea:

Dynamic Programing

Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i-1] and text2[0:j-1]
dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])

Solution:

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    // Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i-1] and text2[0:j-1]
    // dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])
    let dp = Array.from(new Array(text1.length + 1), () => new Array(text2.length + 1));
    
    // final result dp[i + 1][j + 1] contains length of LCS  
    // for text1[0..i] and text2[0..j], so use <=
    for (let i = 0; i <= text1.length; i++) {
        for (let j = 0; j <= text2.length; j++) {
            // base case:
            if (i === 0 || j === 0) 
                dp[i][j] = 0;
            else if (text1[i - 1] === text2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    // dp[text1.length][text2.length] contains length of LCS  
    // for text1[0..text1.length-1] and text2[0..text2.length-1]
    return dp[text1.length][text2.length];
}

LeetCode 300. Longest Increasing Subsequence (javascript)

Given an integer array nums, return the length of the longest strictly increasing subsequence.

subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

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

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Idea:

dp[i] represents the length of the longest increasing subsequence of nums[0...i]
dp[0] = 1
dp[i] = max(dp[j]'s) + 1 if j < i when nums[i] > nums[j]
result: find the max of all dp[i]'s

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let dp = new Array(nums.length);
    dp[0] = 1;
    for (let i = 0; i < nums.length; i++) {
        // local max
        let max = 0;
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                max = Math.max(dp[j], max);
            }
        }
        dp[i] = max + 1;
    }
    // result: find the max of all dp[i]'s
    return Math.max(...dp);
};

118. Pascal’s Triangle (javascript)

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

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

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

  • 1 <= numRows <= 30

Solution:

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    let res = [[1]];
    
    while(numRows > 1) {
        let previous = res[res.length - 1];
        // The first row element is always 1.
        let cur = [1];
        for (let i = 1; i < previous.length; i++) {
            // generate: sum of the elements above-and-to-the-left and above-and-to-the-right.
            cur.push(previous[i - 1] + previous[i]);
        }
        // The last row element is always 1.
        cur.push(1);
        res.push(cur.concat());
        numRows--;
    }
    return res;
};

LeetCode 70. Climbing Stairs (javascript)

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

  • 1 <= n <= 45

Idea:

Dynamic programing

dp[i] represents how many distinct ways climb i stairs to the top
dp[1] = 1;
dp[2] = 2;
dp[3] = dp[2] + d[1];
dp[4] = dp[3] + d[2];
...
dp[i] = dp[i - 1] + dp[i - 2];

Solution:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let dp = Array.from(new Array(n + 1));
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

LeetCode 64. Minimum Path Sum (javascript)

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.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

Idea:

Dynamic Programing

save space: we just use the original grid to calcuate the min path sum
grid[i][j] represent the min path sum of i x j grid
grid[i][j] = get the min of previous grid(top/left) + current val

Solution:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    // save space: we just use the original grid to calcuate the min path sum
    // grid[i][j] = min path sum of i x j grid
    let m = grid.length;
    let n = grid[0].length;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // grid[0][0] itself contains the min path sum
            if (i === 0 && j === 0) continue;
            // first row: grid[i][j] = previous grid(left) + current val
            if (i === 0) grid[i][j] += grid[i][j - 1];
            // first column: grid[i][j] = previous grid(top) + current val
            else if (j === 0) grid[i][j] += grid[i - 1][j];
            // grid[i][j] = get the min of previous grid(top/left) + current val
            else grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
        }
    }
    return grid[m - 1][n - 1];
}

LeetCode 62. Unique Paths (javascript)

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?

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:

Input: m = 7, n = 3
Output: 28

Example 4:

Input: m = 3, n = 3
Output: 6

Constraints:

  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 109.

Idea:

Dynamic Programing

dp[m][n] = unique paths of m x n grid
// base case:
dp[1][1] = 1; 
// dp[i][j] = top(unique paths) + left(unique paths)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

Solution:

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // one row or one column dp[i][1] = dp[1][j] = 1; Let's fill them all 1
    let dp = Array.from(new Array(m), () => new Array(n).fill(1));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // dp[i][j] = top(unique paths) + left(unique paths)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

LeetCode 53. Maximum Subarray (javascript)

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

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -105 <= nums[i] <= 105

Idea:

Dynamic Programing

  • Base case: dp[0] = nums[0];
  • dp[i] = Math.max(dp[i – 1] + nums[i], nums[i]);

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    // dp[i] the largest sum of subarray in nums[0...i]
    let dp = new Array(nums.length);
    // basic case:
    dp[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    }
    return Math.max(...dp);
};

LeetCode 5. Longest Palindromic Substring (javascript)

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case),

Idea:

Dynamic Programing

dp[i][j] = if the substring from i to j is a palindrome = true
dp[i][j] = dp[i+1][j-1] and s[i] === s[j]
base case:
dp[i][i] = true; 
dp[i][i+1] = s[i] === s[i+1];
  • Time complexity : O(n2)
  • Space complexity : O(n2)

Solution:

var longestPalindrome = function(s) {
    let len = s.length;
    if (s === null || len === 1) return s;
    let dp = Array.from(new Array(len), () => new Array(len));
    let res = "";
    let max = 0;
    
    for (let j = 0; j < len; j++) {
        // remember i <= j
        for (let i = 0; i <= j; i++) {
            let isSame = s[i] === s[j];
            
            // one and two letters palindromes only check s[i] === s[j]
            // more than 2, check subset dp[][] && s[i] === s[j]
            dp[i][j] = j - i <= 2 ? isSame : dp[i + 1][j - 1] && isSame;
            
            // any new max palindrome, update max and longest result
            if (dp[i][j] && j - i + 1 > max) {
                max = j - i + 1;
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}

LeetCode 34. Find First and Last Position of Element in Sorted Array (javascript)


Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109

Idea:

Binary Search

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let leftBound = -1;
    let rightBound = -1;
    let l = 0;
    let r = nums.length - 1;
    
    while (l <= r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            leftBound = mid;
            r = mid - 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    l = 0;
    r = nums.length - 1;
    while (l <= r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            rightBound = mid;
            l = mid + 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return [leftBound, rightBound];
};

LeetCode 33. Search in Rotated Sorted Array (javascript)

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

Idea:

Binary Search: the idea is to create a recursive function that takes l and h as range in input and the key.

1) Find middle point mid = (l + h)/2
2) If key is present at middle point, return mid.
   Edge case check(not found): if (l > h) return -1;
3) Else If nums[l..mid] is sorted
    a) If key to be searched lies in range from nums[l]
       to nums[mid], recur for nums[l..mid].
    b) Else recur for nums[mid+1..h]
4) Else (nums[mid+1..h] must be sorted)
    a) If key to be searched lies in range from nums[mid+1]
       to nums[h], recur for nums[mid+1..h].
    b) Else recur for nums[l..mid] 

Solution:

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

function searching(nums, l, h, target) {
    // basic case: not found
    if (l > h) return -1;
    
    let mid = Math.floor((l + h) / 2);
    // basic case: found
    if (target === nums[mid]) return mid;
    
    // if nums[l...mid] is sorted
    if (nums[l] <= nums[mid]) { /// make sure is <=
        if (target >= nums[l] && target <= nums[mid])
            return searching(nums, l, mid - 1, target);
        else
            return searching(nums, mid + 1, h, target)
    }
    
    // if nums[l...mid] is notesorted, then nums[mid+1..h] must be sorted
    if (target >= nums[mid] && target <= nums[h])
        return searching(nums, mid + 1, h, target);
    else
        return searching(nums, l, mid - 1, target);
}