The merge sort is a recursive sort of order n*log(n).

It is notable for having a worst case and average complexity of O(n*log(n)), and a best case complexity of O(n) (for pre-sorted input). The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements (which are both entirely sorted groups). Then merge the groups back together so that their elements are in order. This is how the algorithm gets its “divide and conquer” description.

Continue reading →

Problem Description
Easy level

Given a binary tree, return the inorder traversal of its nodes’ values. Binary Tree Inorder Traversal is to parse left child node, then root, then right child node

Example
Given binary tree {1,#,2,3},

return [1,3,2].
Continue reading →

Problem Description

Given a binary tree, return the preorder traversal of its nodes’ values.

Example
Given binary tree {1,#,2,3}:

Continue reading →

Problem description

The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case, so it caused this version and the following versions are all failed in the unit tests. Find the first bad version.

You can call isBadVersion to help you determine which version is the first bad one. The details interface can be found in the code’s annotation part.

Continue reading →

Problem description:
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.
Example
Given [4, 5, 6, 7, 0, 1, 2] return 0
Continue reading →

Problem:
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

Example

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Challenge

If the count of numbers is bigger than 2^32, can your code work properly?
Continue reading →

Problem: Given a rotated sorted array, recover the sorted array in-place.

For example:
{ 4, 5, 1, 2, 3 } –> {1, 2, 3, 4, 5}

Challenge requirement:
in-palce, O(1) extra space and O(n) time
Continue reading →

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:
1) Elements in a subset must be in non-descending order.
2) The solution set must not contain duplicate subsets.
Continue reading →

Given a set of distinct integers, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

Continue reading →

strstr (a.k.a find sub string), is a useful function in string operation. You task is to implement this function. For a given source string and a target string, you should output the “first” index(from 0) of target string in source string. Continue reading →