• Maximum XOR of Two Numbers in an Array

    Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

    Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

    Could you do this in O(n) runtime?


    The following method is the easiest to understand:



    [Read More...]
  • [Leetcode] Find Permutation

    By now, you are given a secret signature consisting of character ‘D’ and ‘I’. ‘D’ represents a decreasing relationship between two numbers, ‘I’ represents an increasing relationship between two numbers. And our secret signature was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature “DI” can be constructed by array [2,1,3] or [3,1,2], but won’t be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can’t represent the “DI” secret signature.

    On the other hand,

    [Read More...]
  • [Leetcode] Optimal Account Balancing

    A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill’s lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person’s ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].

    Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

    [Read More...]
  • [LeetCode] Android Unlock Patterns

    Given an Android 3×3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

    Rules for a valid pattern:

    1. Each pattern must connect at least m keys and at most n keys.
    2. All the keys must be distinct.
    3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern.
    [Read More...]
  • Leetcode Group Shifted Strings

    Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

    Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

    For example, given: [“abc”, “bcd”, “acef”, “xyz”, “az”, “ba”, “a”, “z”],

    Note: For the return value, each inner list’s elements must follow the lexicographic order.

    A better example:

    [“eqdf”, “qcpr”]

    ((‘q’ –

    [Read More...]
  • [Leetcode] Fraction to Recurring Decimal

    Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

    If the fractional part is repeating, enclose the repeating part in parentheses.

    For example,

    • Given numerator = 1, denominator = 2, return “0.5”.
    • Given numerator = 2, denominator = 1, return “2”.
    • Given numerator = 2, denominator = 3, return “0.(6)”.


    1. No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
    2. Try a long division on 4/9,
    [Read More...]
  • [LeetCode] Shortest Distance from All Buildings

    You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

    • Each 0 marks an empty land which you can pass by freely.
    • Each 1 marks a building which you cannot pass through.
    • Each 2 marks an obstacle which you cannot pass through.

    For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

    The point (1,2) is an ideal empty land to build a house,

    [Read More...]
  • Maximum Product of Word Lengths

    Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

    Example 1:

    Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]
    Return 16
    The two words can be “abcw”, “xtfn”.

    Example 2:

    Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”]
    Return 4
    The two words can be “ab”, “cd”.

    Example 3:

    Given [“a”, “aa”,

    [Read More...]
  • Number of Connected Components in an Undirected Graph

    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 find the number of connected components in an undirected graph.

    Example 1:

         0              3

         |                |

         1 — 2      4

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

    Example 2:

         0              4 

         |                |

         1 — 2 — 3

    Given n = 5 and edges = [[0,

    [Read More...]
  • Wiggle Sort II

    Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

    (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
    (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

    You may assume all input has valid answer.

    Follow Up:
    Can you do it in O(n) time and/or in-place with O(1) extra space?


    The virtual index idea in the post https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing
    is very brilliant!

    [Read More...]
Page 1 of 912345...Last »