Algorithm | Learn for Master - Part 7
• ### Range Minimum Query – Segment Tree (Java)

Given an array, there is a popular problem to search the minimum value in a range [a, b]. This is called Range Minimum Query. This post describes a method to solve the range minimum query problem using Segment Tree.

The basic idea of a Segment tree is as follows:

Given an array A with size n:  the index of the array looks like this [0, 1, 2, …., n-1],

1. The root of the Tree contains the minimum value of the whole array, or the minimum value in the range [0, n – 1].
• ### Shortest Path Problems

Given a weighted graph G Given a weighted graph G (V,E), =(V,E), and a source vertex s, find the minimum weighted path from s to every other vertex in G

Unweighted graph

If the graph is unweighted, we can solve this problem using Bread First Search.

Weighted Graph

For Weighted Graph, we solve this problem use Dijkstra’s algorithm.

shortest path between all pairs of vertices

Given G(V,E), find a shortest path between all pairs of vertices.

Solutions: (brute -force) Solve Single Source Shortest Path for each vertex as source.

• ### LeetCode – Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Hint:

1. Try two pointers.
• ### LeetCode-Coin Change Problem (Python)

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = , amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

• ### LeetCode – Next Permutation (Python)

Implement 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 be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

The solution is the Pandit’s algorithm

1 Pandit’s algorithm
The article in Wikipedia describes the algorithm invented by Narayana Pandit to changes the list in-place to generate the next permutation given a list or Array A.

• ### Selection Sort Algorithm (Python)

Selection sort is one of the simplest sorting algorithms. This tutorial described how to implement selection sort algorithm in python.

The basic idea of selection sort is that it repeatedly select the smallest item in list A[i+1:], and exchange it with the item at A[i].

It works as follows:

1. Find the smallest item in the array, and exchange it with the first entry.
2. Find the next smallest item in the array, and exchange it with the second entry.
3. Continue such a process until the whole array is sorted.

• ### Aho-Corasick Algorithm Problem:

Given an input text and an a dictionary, find all occurrences of all words in the input text.
Example:

We can solve this problem using KMP algorithm, but it is not efficient.

The solution is Aho-Corasick automation (AC automaton), which is one of the most famous string pattern match algorithms. See https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm for an introduction.

By using AC automaton, we can solve the problem in O(n + m +  z), where n is the total length of the words in the dictionary, m is the length of the string T,