Algorithms | Learn for Master - Part 8
  • Leetcode – Graph valid tree solution based on Union find set

    Graph Valid Tree
    Given n nodes labeled from 0 to n – 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

    For example:

    Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

    Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

    Hint:

    Given n = 5 and edges = [[0, 1], [1, 2],

    [Read More...]
  • Leetcode – Meeting rooms solution in Java

    Meeting Rooms
    Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

    For example, Given [[0, 30],[5, 10],[15, 20]], return false.

    Analysis

    We can sort the intervals using the start time. Then we check whether there is conflict.  For instance. for this two pairs,  [0, 30],[5, 10] As 5 is smaller than 30, the person cannot attend both. 

    When we do the check, we should record the latest end time before the current interval. For current interval,

    [Read More...]
  • Leetcode – Color Sort

    Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

    Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

    Note:
    You are not suppose to use the library’s sort function for this problem.

    Follow up:
    A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s,

    [Read More...]
  • Morris Traversal: Inorder Tree Traversal without recursion and without stack (Java)

    morris inorder traverse example

    Tree traversal is often implemented using Stack or Recursion. In this case, the space complexity is O(h), where h is the height of the tree. We describe a method based on Morris Traversal for tree traversal using O(1) space. 

    The basic idea of Morris Traversal is that: For current Node Cur, we use the right most leaf of its left child to record the location of Cur.

    Suppose we start from root, after running 

    preOfRoot’s right child will point to root. Now we can traverse the left branch of the tree.

    [Read More...]
  • 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]. 
    [Read More...]
  • 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.  

    [Read More...]
  • 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 = [2], amount = 3
    return -1.

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

    [Read More...]
  • 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.

    [Read More...]
  • 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.

    [Read More...]
  • Aho-Corasick Algorithm

    aho-corasick

    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,

    [Read More...]
Page 8 of 8« First...45678