Find Duplicate Numbers in An Integer Array

Give an array contains n+1 number which range from 1 to n. Find the duplicates.

e.g. 1, 2, 3, 3 -> 3
1, 3, 2, 4, 3 -> 3

Requirements
Space o(1)
Time o(n)

Since there are 1..n number in n+1 size array, every number can link to other using the form num -> array[num].
Note if there are duplicates amount 1 to n, then there will be different numbers links to the same number.

For example: 1->3->4->3 which forms a loop, now the problem becomes finding the starting of loop.

which can be done by https://en.wikipedia.org/wiki/Cycle_detection

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];
     
        while(slow!=fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
     
        slow = 0;
        while(slow!=fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
     
        return slow;
    }
}

regular expression match

Recently I coded in JS a lot. Its simplicity to make writing code extremely concise.

	function regEx(p, w, i, j) {
	if( i == p.length && j == w.length )
	return true;
	if ( j == w.length || i == p.length )
	return false;
	//if second char is *
	if ( i+1<p.length && p.charAt(i+1) == '*' ){
	//match pre char 0 time
	if(regEx(p, w, i+2, j))
	return true;
	//match pre char 1+ times
	for(let k = j; k<w.length && (p.charAt(i)==w.charAt(k) || p.charAt(i) == '.'); k++) {
	if(regEx(p, w, i+2, k+1))
	return true;
	}
	}
	if(p.charAt(i) == w.charAt(j) || p.charAt(i) == '.') {
	if(regEx(p, w, i+1, j+1))
	return true;
	}
	return false;
	}

view raw reg.js hosted with ❤ by GitHub

[LeetCode] Flatten Nested List Iterator

Many questions looks pretty hard, and we came up lots of lines of code and tried to cover every corner cases. But in the end the perfect solution is always the simplest with least lines of code. The question is the example.

This is the link to the problem: flatten-nested-list-iterator

Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

The solution is pretty straightforward,  if we treat the nested list to a tree, with nested list as children nodes, its parent is the list encloses it. Then we can use pre-order traversal of the tree to find the all of the integers and print them out. But to implement the iterator, we also need a stack to keep track the parent list when we travel the children lists underneath it. Remember the solution of pre-order traversal of binary search using stack?

	public class NestedIterator implements Iterator<Integer> {
	//pointer the curr list we are examing
	List<NestedInteger> curr;
	//the index of the item in the list
	int pos;
	//all of the parent lists
	Stack<List<NestedInteger>> stack;
	//and the corresponding position in the parent lists before we go down to the childrent list
	Stack<Integer> posStack;
	public NestedIterator(List<NestedInteger> nestedList) {
	this.curr = nestedList;
	this.pos = 0;
	this.stack = new Stack<>();
	this.posStack = new Stack<>();
	}
	@Override
	public Integer next() {
	Integer result = null;
	result = curr.get(this.pos).getInteger();
	pos++;
	return result;
	}
	@Override
	public boolean hasNext() {
	//when the input is empty OR when we finish everything
	if(this.pos >= curr.size() && this.stack.isEmpty()){
	return false;
	}
	while(this.pos<curr.size() || !this.stack.isEmpty()){
	if(this.pos<curr.size()){
	if(this.curr.get(this.pos).isInteger())
	return true;
	else{
	if(curr.get(this.pos).getList().size()>0){
	//save parent and current postion in parent list
	this.stack.push(this.curr);
	this.posStack.push(this.pos);
	//then go down to the children level
	this.curr = curr.get(this.pos).getList();
	this.pos = 0;
	}else{
	this.pos++ ;
	}
	}
	}else{
	this.curr = this.stack.pop();
	this.pos = this.posStack.pop() + 1;
	}
	}
	return false;
	}
	}

view raw FlattenNestedListIterator hosted with ❤ by GitHub

[LeetCode] Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ - 1.
For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

There are several key observations to solve this:
1. the number can be divided into numbers of 3 digits long;
2. for every 3 digits, words like ""Thousand", "Millions", "Billion" are added
3. if the last two digits of the 3 digits form a number falls between 10 to 19, we treat them together; otherwise we treat them separately.
4. read the digits from left to right until we process all digits

Here is the source code:

	public String numberToWords(int num) {
	if(num==0)
	return "Zero";
	Map<Integer, String> map = new HashMap<>();
	map.put(3, "Thousand");
	map.put(6, "Million");
	map.put(9, "Billion");
	String[] store = new String[]{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
	String[] store1 = new String[]{"Ten","Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
	String[] store2 = new String[]{"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
	//pointer starts from the right and move to the left
	int index = 0;
	//stack to store the words
	Stack<String> stack = new Stack<>();
	while(num>0){
	//store thousand, million or billion only there is digits in last 3
	if(index%3==0 && index>0 && num%1000>0){
	stack.push(map.get(index));
	}
	if(index%3==0){
	//if the last digits fall into [10 - 19]
	if(num%100>9 && num%100<20){
	stack.push(store1[num%10]);
	index++;
	num /=10;
	}else{
	if(num%10>0){
	stack.push(store[num%10]);
	}
	}
	}else if(index%3==1){
	if(num%10>1){
	stack.push(store2[num%10]);
	}
	}else{
	if(num%10>0){
	stack.push("Hundred");
	stack.push(store[num%10]);
	}
	}
	//move the pointer to left
	index++;
	//chop the last digit
	num /= 10;
	}
	StringBuilder sb = new StringBuilder();
	while(!stack.empty()){
	sb.append(stack.pop());
	sb.append(" ");
	}
	return sb.toString().trim();
	}

view raw numberToWords.java hosted with ❤ by GitHub

[LeetCode] Patching Array

From leetcode
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
Example 1:
nums = [1, 3], n = 6
Return 1.
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.
Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Let's look at the example 1, let curr be the current number in the arrray, cover be the maximum number the numbers being covered from 1.
When curr = 1, cover = 1;
When curr = 3, since there is gap between cover and curr, we need to fill it in, so insert 2, and update cover to 1 + 2 + 3 = 6;
Done.

Example 2.
curr = 1, cover = 1;
curr = 5, fill in the gap between 1 and 5, insert 2, cover = 1+2 = 3, gap is still there between 3 and 5, insert cover+1=4, update cover = 1+2+3=6, no gap any more, update cover = 1+2+3+5=11
curr = 10, no gap, and update cover = 11+10=21
21>20, Done.

So the two most important findings are
1) when we insert a number, the coverage will be increased by that number,
2) next insert number will be the coverage+1.

So our algorithm is following:
let cover=0, insert=0
1. go through the numbers (curr) in the list until cover >= n
  while curr > cover+1 and cover<n,
    insert cover+1
    update cover = cover + cover+1
    increase insert by 1

2. while cover < n
        insert cover+1
        update cover = cover + cover+1
        increase insert by 1

	public class Solution {
	public int minPatches(int[] nums, int n) {
	if(n<1)
	return 0;
	int count = 0;
	//use long to take care of the case that cover is larger than Integer.MAX_VALUE
	long cover = 0;
	for(int i=0, len=nums.length; n>cover && i<len; i++){
	while(n>cover && nums[i]>cover+1){
	//insert cover+1
	count++;
	cover += cover +1;
	}
	cover += nums[i];
	}
	while(n>cover){
	//insert cover+1
	count++;
	cover += cover +1;
	}
	return count;
	}
	}

view raw minPatches.java hosted with ❤ by GitHub

[LeetCode] Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Image we go through the input string, if we see number, we know we have to go down the tree until we encounter the "#", if we see "#", we will stop going down the tree and return. If we use a recursive function to process the input string, for a valid preorder string, we should successfully process all of the whole string. For invalid one we either prematurely terminate the process or go beyond the length of string.

	public class Solution {
	public boolean isValidSerialization(String preorder) {
	String[] tem = preorder.split(",");
	int[] index = new int[]{0};
	rec(tem, index);
	return index[0] == tem.length-1;
	}
	private void rec(String[] tem, int[] index){
	if(index[0]>=tem.length)
	return;
	if(tem[index[0]].equals("#"))
	return;
	index[0]++;
	rec(tem, index);
	index[0]++;
	rec(tem, index);
	}
	}

view raw isValidSerialization.java hosted with ❤ by GitHub

[LeetCode] LRU Cache

One of straightforward implementation of LRUCache is to use JDK's LinkedHashMap. However to implement it correctly, overriding its removeOldestEntry() method is not enough.

We need to use the correct LinkedHashMap constructor with correct arguments to make sure it behaves as LRU cache. Below is the doc from JDK:

"A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). "

And here is the code which passed the LeetCode tests and beat 90% Java implementation in terms of the runtime.

	public class LRUCache {
	LinkedHashMap<Integer, Integer> cache;
	public LRUCache(int capacity){
	cache = new LinkedHashMap<Integer, Integer>(capacity, (float) 0.75, true){
	@Override
	protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
	return this.size() > capacity;
	}
	};
	}
	public List<Integer> getValuesAsList(){
	return new ArrayList<>(cache.values());
	}
	public int get(int key) {
	Integer result = cache.get(key);
	if(result==null)
	result = -1;
	return result;
	}
	public void set(int key, int value) {
	cache.put(key, value);
	}
	}

view raw LRUCache.java hosted with ❤ by GitHub