Apart from vanilla BFS introduced in Intro to Graph Algorithms – BFS & DFS, there’s another variant of BFS called bi-directional BFS. Instead of searching from source to target, bi-directional BFS starts with the source and the target at the same time, and search the graph simultaneously. The improvement of time complexities is shown as below, as referring to @Huahua.

Continue reading “BFS and Bi-directional BFS”## [Leetcode]1537. Get the Maximum Score

You are given twoContinue reading “[Leetcode]1537. Get the Maximum Score”sortedarrays of distinct integers`nums1`

and`nums2.`

Avalidis defined as follows: Choose array nums1 or nums2 to traverse (from index-0). Traverse the current array from left to right. If you are reading any value that is present inpath`nums1`

and`nums2`

you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).Scoreis defined as the sum of uniques values in a valid path. Return the maximumscoreyou can obtain of all possiblevalid paths. Since the answer may be too large, return it modulo 10^9 + 7.

## [Leetcode]1286. Iterator for Combination

Design an Iterator class, which has: A constructor that takes a stringContinue reading “[Leetcode]1286. Iterator for Combination”`characters`

ofsorted distinctlowercase English letters and a number`combinationLength`

as arguments. A functionnext()that returns the next combination of length`combinationLength`

inlexicographical order. A functionhasNext()that returns`True`

if and only if there exists a next combination.Constraints:`1 <= combinationLength <= characters.length <= 15`

There will be at most`10^4`

function calls per test. It's guaranteed that all calls of the function`next`

are valid.

## [Leetcode]31. Next Permutation

ImplementContinue reading “[Leetcode]31. Next Permutation”next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must bein-placeand use only constant extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.`1,2,3`

→`1,3,2`

`3,2,1`

→`1,2,3`

`1,1,5`

→`1,5,1`

## [Leetcode]238. Product of Array Except Self

Given an arrayContinue reading “[Leetcode]238. Product of Array Except Self”`nums`

ofnintegers wheren> 1, return an array`output`

such that`output[i]`

is equal to the product of all the elements of`nums`

except`nums[i]`

.Note:Please solve itwithout divisionand in O(n).Follow up:Could you solve it with constant space complexity? (The output arraydoes notcount as extra space for the purpose of space complexity analysis.)Example:Input:`[1,2,3,4]`

Output:`[24,12,8,6]`

## [Leetcode]560. Subarray Sum Equals K

Given an array of integers and an integerContinue reading “[Leetcode]560. Subarray Sum Equals K”k, you need to find the total number of continuous subarrays whose sum equals tok.Example 1:Input:nums = [1,1,1], k = 2Output:2

## [Leetcode]442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤Continue reading “[Leetcode]442. Find All Duplicates in an Array”n(n= size of array), some elements appeartwiceand others appearonce. Find all the elements that appeartwicein this array. Could you do it without extra space and in O(n) runtime?

## [Leetcode]3. Longest Substring Without Repeating Characters

Given a string, find the length of theContinue reading “[Leetcode]3. Longest Substring Without Repeating Characters”longest substringwithout repeating characters.Example 1:Input:"abcabcbb"Output:3Explanation:The answer is`"abc"`

, with the length of 3.