Algorithms | Learn for Master - Part 3
  • Union and Intersection of two sorted arrays (Java)

    Given two sorted arrays or lists, get their union and intersection.

    For example, if the input arrays are:
    int[] list1 = {1, 3, 4, 5, 6, 7}
    int[] list2 = {2, 3, 5, 6}
    Then the union is {1, 2, 3, 4, 5, 6, 7} and the Intersection is {3, 5, 6}.

    Analysis

    We can solve this problem using the same idea of merging sorted list.

    Union of two sorted lists algorithm

     define two index variables p1 and p2, initialized as 0

    define List<Integer> 

    [Read More...]
  • LeetCode move zeroes

    Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

    For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

    Note:

    1. You must do this in-place without making a copy of the array.
    2. Minimize the total number of operations.

     Analysis
     

    We can use a pointer zeroIndex to always point to the index of the first 0. We scan the array, if we encounter a non-zero element,

    [Read More...]
  • Leetcode Invert Binary Tree

    Invert a binary tree.

    to

    Trivia:
    This problem was inspired by this original tweet by Max Howell:

    Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

    Analysis

    This problem can be solved by using both recursion and bread first traverse or Level order traverse. 

    We first invert the left tree and right tree, then put the inverted right tree as the left child,

    [Read More...]
  • LeetCode Shortest Word Distance I II and III

    Shortest Word Distance I

    Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

    For example, Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

    Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = “makes”, word2 = “coding”, return 1.

    Note

    You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

    Analysis

    We can scan the list and use two pointers to record the most recent indexes of the two words.

    [Read More...]
  • Leetcode – Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

    Analysis:

    This problem can be easily solved using a recursive algorithm.  As

    maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right) + 1 if root != null;

    and maxDepth(root) == 0 if root == null;

    Java solution:

     

    https://leetcode.com/problems/maximum-depth-of-binary-tree/

    [Read More...]
  • Leetcode – Add Digits

    Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

    For example:

    Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

    Follow up:
    Could you do it without any loop/recursion in O(1) runtime?

    Hint:

    1. A naive implementation of the above process is trivial. Could you come up with other methods?
    2. What are all the possible results?
    3. How do they occur,
    [Read More...]
  • Leetcode – Wall and Gates

    You are given a m x n 2D grid initialized with these three possible values.

    1. -1 – A wall or an obstacle.

    2. 0 – A gate.

    3. INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

    For example,

    [Read More...]
  • LeetCode - Flip Game

    You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–“. The game ends when a person can no longer make a move and therefore the other person will be the winner.

    Write a function to compute all possible states of the string after one valid move.

    For example, given s = “++++”, after one move, it may become one of the following states:

    If there is no valid move,

    [Read More...]
  • LeetCode – Flip Game II

    You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–“. The game ends when a person can no longer make a move and therefore the other person will be the winner.

    Write a function to determine if the starting player can guarantee a win.

    For example, given s = “++++”, return true. The starting player can guarantee a win by flipping the middle “++” to become “+–+”.

    Follow up:
    Derive your algorithm’s runtime complexity.

    [Read More...]
  • Leetcode – Palindrome Permutation

    Given a string, determine if a permutation of the string could form a palindrome.

    For example, “code” -> False, “aab” -> True, “carerac” -> True.

    Hint:

    Consider the palindromes of odd vs even length. What difference do you notice? Count the frequency of each character. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

    Analysis

    A native solution is to generate the permutation of the string, then check whether it is a palindrome. 

    A better solution is suggested from the above hint.

    [Read More...]
Page 3 of 812345...Last »