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.

[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?

[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:

[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

[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.

[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.