142. Linked List Cycle II Leetcode Java

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

Solution:

Following the previous problem, we have to find the starting point.

According to the previous analysis. We know that, if there is a cycle, these two pointers will meet at some point in the cycle and this point will satisfy the equation: a+b =(m-2n)c. As we know c is the cycle length, so if we travel a steps from b, we will reach the starting point of the cycle ath position. In addition if we travel a steps from start point of list, we will reach the starting point of the cycle as well. The algorithm is based on this observation. Once we find the meeting point, we set one of the pointer back to starting point of the list and let those two points both walk one step each time till they meet again. The meeting point will be the starting point of the cycle.

 public ListNode detectCycle(ListNode head) {  
    if(head==null || head.next==null) return null;  
    ListNode walker=head;  
    ListNode runner=head.next;  
    while(runner!=null && runner.next!=null && walker!=runner){  
      walker=walker.next;  
      runner=runner.next.next;  
    }  
    if(walker!=runner) return null;  
    runner=runner.next;  
    walker=head;  
    while(walker!=runner){  
      walker=walker.next;  
      runner=runner.next;  
    }  
    return walker;  
   }  

141. Linked List Cycle Leetcode Java

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Solution:

Floyd's cycle detection algorithm. Assume there is a cycle, and the cycle start at ath point. And the cycle length is c. We set two pointers one is tortoise and the other one is hare as two times faster than tortoise. And if there is a cycle, they will meet eventually at some point in the cycle. Assume this point is b steps away from ath point. So a+mc+b=2(a+nc+b). where m and n are the number of cycles that hare and tortoise traveled respectively. a+b =(m-2n)c. There must exist b to satisfy the equation. And so if they can meed at some point, there must be a cycle. The contraposition of this argument is simple to understand: If there is no cycle=> they can't meet. 

  public boolean hasCycle(ListNode head) {  
    if(head==null || head.next==null) return false;  
    ListNode walker=head;  
    ListNode runner=head.next;  
    while(runner!=null && runner.next!=null && walker!=runner){  
      walker=walker.next;  
      runner=runner.next.next;  
    }  
    return walker==runner;  
   }  

140. Word Break II Leetcode Java

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution:

Recursion:

Iteratively check s.substring(start,i), if dictionary contains this substring, recursively check if s.substring(i, end) can be break to the rest of words in the dictionary.

Need to take care of the first word, because all other words will be presented in the final result start with a whitespace except the first word.

Another tip is if the word is not breakable by calling the method of previous problem: Word Break, simply return an empty list rather than go through all the recursion steps.

 public List<String> wordBreak(String s, Set<String> dict) {  
    List<String> res=new ArrayList<String>();  
    if(s==null || !isBreakable(s,dict)) return res;  
    helper(s,0,new StringBuilder(),res,dict);  
    return res;  
   }  
   public void helper(String s, int start, StringBuilder items, List<String> res, Set<String> dict){  
     if(start>=s.length()){  
       res.add(items.toString());  
       return;  
     }  
     if(start!=0) items.append(" ");  
     for(int i=start;i<s.length();i++){  
       if(dict.contains(s.substring(start,i+1))){  
         items.append(s.substring(start,i+1));  
         helper(s,i+1,items,res,dict);  
         items.delete(items.length()+start-i-1,items.length());  
       }  
     }  
     if(start!=0) items.deleteCharAt(items.length()-1);  
   }  
   public boolean isBreakable(String s, Set<String> dict){  
     boolean[] res=new boolean[s.length()+1];  
     res[0]=true;  
     for(int i=0;i<s.length();i++){  
       for(int j=0;j<=i;j++){  
         if(res[j]&&dict.contains(s.substring(j,i+1))){  
           res[i+1]=true;  
           break;  
         }  
       }  
     }  
     return res[s.length()];  
   }  

139. Word Break Leetcode Java

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution:

Dynamic programming

The recursion equation is straightforward, for res[i], if there exist an index j between 0 and i can make res[j]&&dict.contains(s.substring(j,i)) true, then res[i] will be true. 

 public boolean wordBreak(String s, Set<String> dict) {  
     if(s==null) return false;  
     if(s.length()==0) return true;  
     boolean[] res=new boolean[s.length()+1];  
     res[0]=true;  
     for(int i=0;i<s.length();i++){  
       for(int j=0;j<=i;j++){  
         if(res[j] && dict.contains(s.substring(j,i+1))){  
           res[i+1]=true;  
           break;  
         }  
       }  
     }  
     return res[s.length()];  
   }  

138. Copy List with Random Pointer Leetcode Java

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

/**

 * Definition for singly-linked list with a random pointer.

 * class RandomListNode {

 *     int label;

 *     RandomListNode next, random;

 *     RandomListNode(int x) { this.label = x; }

 * };

 */

Solution:

1, HashMap

This solution is very intuitive. Basically, we build a hashmap to mapping the given nodes to the created nodes. When we traversal the list, if cur.random is in the map, we put the created newCur.random = map.get(cur.random), otherwise create a new node with cur.random.lable and map it to cur.random. We do the same thing for cur.next. So when we finish the traversal, we will get a copy of the list with random pointer.
Time complexity: O(n)  O(n) extra space.

  public RandomListNode copyRandomList(RandomListNode head) {  
    if(head==null) return null;  
    RandomListNode newHead=new RandomListNode(head.label);  
    HashMap<RandomListNode, RandomListNode> map=new HashMap<RandomListNode,RandomListNode>();  
    map.put(head,newHead);  
    RandomListNode cur=head;  
    RandomListNode newCur=newHead;  
    while(cur!=null){  
      if(cur.random!=null){  
        if(map.containsKey(cur.random)) newCur.random=map.get(cur.random);  
        else{  
          RandomListNode newNode=new RandomListNode(cur.random.label);  
          newCur.random=newNode;  
          map.put(cur.random,newNode);  
        }  
      }  
      if(cur.next!=null){  
        if(map.containsKey(cur.next)) newCur.next=map.get(cur.next);  
        else{  
          RandomListNode newNode=new RandomListNode(cur.next.label);  
          newCur.next=newNode;  
          map.put(cur.next,newNode);  
        }  
      }  
      cur=cur.next;  
      newCur=newCur.next;  
    }  
    return newHead;  
   }  

2, two pointer
This is solution is very clever. We create the copy of given node cur,  and set the image as the real.next: copied(Cur)=cur.next; Then we can connect the random pointer simply by setting cur.next.random=cur.random.next. which equivalent to set copied(Cur).random=copied(Cur.random). The last step is to separate the copied list from original list. What I did is use a counter, for odd counter it means the processing node is from original list, so cur.next= copied(cur).next. For even counter it means the processing node is from copied list. We separate the list one node a time from original list and copied list in turn.
Time complexity: O(n)  no extra space.

  public RandomListNode copyRandomList(RandomListNode head) {  
    if(head==null) return null;  
    RandomListNode cur=head;  
    while(cur!=null){  
      RandomListNode temp=new RandomListNode(cur.label);  
      temp.next=cur.next;  
      cur.next=temp;  
      cur=temp.next;  
    }  
    cur=head;  
    while(cur!=null){  
      if(cur.random!=null){  
        cur.next.random=cur.random.next;  
      }  
      cur=cur.next.next;  
    }  
    RandomListNode newHead=head.next;  
    cur=head;  
    RandomListNode newCur=newHead;  
    int i=1;  
    while(cur!=null){  
      if(i%2==1){  
        cur.next=newCur.next;  
        cur=cur.next;  
      }  
      else{  
        newCur.next=cur.next;  
        newCur=newCur.next;  
      }  
      i++;  
    }  
    return newHead;  
   }  

137. Single Number II Leetcode Java

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

More general than previous problem.

Since the array contains only integer, we can use a counter to count the numbers of each bits(total 32 bits for integer). All those elements appears three times, the counts of each bits are able to divided by 3.  So the remainder of bit count will be the single number.

Time complexity:O(32*n)=O(n) constant space.

 public int singleNumber(int[] A) {  
    if(A==null || A.length==0) return 0;  
    int[] dig=new int[32];  
    for(int i=0;i<32;i++){  
      for(int j=0;j<A.length;j++){  
        dig[i]+=(A[j]>>i) & 1;  
      }  
    }  
    int res=0;  
    for(int i=0;i<32;i++){  
      dig[i]=dig[i]%3;  
      res+=(dig[i]<<i);  
    }  
    return res;  
   }  

136. Single Number Leetcode Java

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

This solution is not a general solution for this kind of problem. Please refer next problem: 137. Single Number II for a general solution.

This solution use a special bit operator to distinguish the single number: the xor exclusive or(^) bit operator. Two main facts that used in this problem. 

1. x^x=0;

2. 0^x=x;

So if we use the exclusive or for each number in the array, we will find the single one. Because all elements appear twice will cancelled out to 0, and leave the single one ^ 0= single one.

Time complexity: O(n)

  public int singleNumber(int[] A) {  
    if(A==null || A.length==0) return 0;  
    int res=0;  
    for(int i=0;i<A.length;i++){  
      res=res^A[i];  
    }  
    return res;  
   }  

135. Candy Leetcode Java

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Solution:

Two rounds correction.

1st round from left to right, and only consider left neighbor.  If the left neighbor has higher rating, set candy of current child as 1, otherwise set as one more candy as its left neighbor's candies. 

2nd round from right to left, and only consider right neighbor. Correct those who has less or equal candies with higher rating than its right neighbor.

For 1st round, it will make sure all the children with higher rating than its left neighbor will get more candies. And it is the minimum distribution method, because we only give 1 extra. For 2nd round, it will make sure all the children with higher rating than its right neighbor will get more candies. Because we only increase the candy numbers in this round, it will satisfy the conditions for both neighbors. 
Time complexity: O(n)

  public int candy(int[] ratings) {  
    if(ratings==null || ratings.length==0) return 0;  
    int[] candies= new int[ratings.length];  
    candies[0]=1;  
    for(int i=1;i<ratings.length;i++){  
      if(ratings[i]>ratings[i-1]) candies[i]=candies[i-1]+1;  
      else candies[i]=1;  
    }  
    int sum=candies[ratings.length-1];  
    for(int i=ratings.length-2;i>=0;i--){  
      if(ratings[i]>ratings[i+1]){  
        candies[i]=Math.max(candies[i+1]+1,candies[i]);  
      }  
      sum+=candies[i];  
    }  
    return sum;  
   }  

134. Gas Station Leetcode Java

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Solution:

This problem is a very good problem and really need some critical thinking. 

Some observation here:

Set budget[i]=gas[i]-cost[i]

1.If budget[i]<0 => we can't go to (i+1)th gas station.

2. If Sum(budget[i]:budget[j])<0 we can't go to j from i.

3. If Sum(budget[0]:budget[n])<0, we can't make a cycle.

Those are some obvious observations, Following are some patterns behind the scene. 

1.If we calculate sum(budget[i]: budget[j]) until sum becomes negative, which means sum(budget[i]:budget[j-1])>=0 but sum(budget[i]:budget[j])<0, the car can't go from i to j and it can't go to j from any point between i and j-1, because it is station j make the summation negative, so any station between i and j-1, let's say x will make sum(budget[x]:budget[j])<0. In addition any station between i and j can't be the starting point because they can't even reach j. The starting point must between j+1 and n.

2. According to the previous conclusion, we can divide the cycle to several pieces, first couple pieces contain a negative sequence so that sum(budget[start]: budget[end])<0. And the last piece contains a positive sequence to make it reach to n (if there is no such positive sequence end at n, it definitely can't make a cycle). Assume the cycle has been divided to those pieces: 0-> i1 (negative, i1 can be 0); i1+1->i2(negative); i2+1-> i3(negative); i3+1 -> n (positive). Let's set the sum of the 3 negative sequences as negSum, and the sum of budget[i3+1]->budget[n] as posSum, if posSum+negSum>0, which means, we can start from i3+1 ->n->0->i1->i2->i3->i3+1, because the posSum will compensate each negative sequence and still can reach itself. 

The algorithm is a little greedy here, we sum the budget for every station, if the sum becomes negative, we know the start point won't be any station before the current station. 

And we can know this is a negative sequence, add the sum to negSum. Unless we can find a station that can reach n, that station is a valid candidate of making a cycle. The last step is to check if the gain can from start to n can compensate the loss from 0 to start. 

Time complexity: O(n)

  public int canCompleteCircuit(int[] gas, int[] cost) {  
    if(gas==null || gas.length==0 || gas.length!=cost.length) return -1;  
    int start=0;  
    int posSum=0;  
    int negSum=0;  
    for(int i=0;i<gas.length;i++){  
      int budget=gas[i]-cost[i];  
      posSum+=budget;  
      if(posSum<0){  
        negSum+=posSum;  
        posSum=0;  
        start=i+1;  
      }   
    }  
    return (negSum+posSum>=0)? start:-1;  
   }  

133. Clone Graph Leetcode Java

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution:

/**

 * Definition for undirected graph.

 * class UndirectedGraphNode {

 *     int label;

 *     List<UndirectedGraphNode> neighbors;

 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

 * };

 */

Because nodes are label uniquely, we can build a hashmap to mapping the labels with the created nodes. BFS the original graph, if the label of visited node has been created, connect it with its neighbor. Otherwise create a new one with the label, connect it with its neighbor and put it into the map.

 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {  
     if(node==null) return node;  
     HashMap<Integer, UndirectedGraphNode> map=new HashMap<Integer, UndirectedGraphNode>();  
     LinkedList<UndirectedGraphNode> q=new LinkedList<UndirectedGraphNode>();  
     q.offer(node);  
     map.put(node.label, new UndirectedGraphNode(node.label));  
     while(!q.isEmpty()){  
       UndirectedGraphNode un=q.poll();  
       for(UndirectedGraphNode temp : un.neighbors){  
         if(map.containsKey(temp.label)) map.get(un.label).neighbors.add(map.get(temp.label));  
         else{  
           UndirectedGraphNode newNode=new UndirectedGraphNode(temp.label);  
           map.put(temp.label, newNode);  
           map.get(un.label).neighbors.add(newNode);  
           q.offer(temp);  
         }  
       }  
     }  
     return map.get(node.label);  
   }  

132. Palindrome Partitioning II Leetcode Java

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution:

Dynamic programming.

First of all, if we know the minimum cut of s.substring(0,i), let's say res[i], then for the minimum cut of s.substring(0,i+1) let's say res[i+1] must be <=res[i]+1. Because a single character(s.charAt(i)) must be a valid palindrome. Further more, if any index between 0 to i (let's say j) can make s.subString(j,i+1) a valid palindrome, then res[i+1]<=res[j-1]+1. So if we search such j between 0 to i, and if this partition can make res[i+1] smaller or lesser, we then update res[i+1] to the smaller one. In this way, we can find the minimum cut for palindrome partition of s.

Tips: Set the cut for s.substring(0,0) as res[0]=-1, this way can avoid to take special care of the case when s.substring(0,i+1) itself is a valid palindrome, then simply set res[i+1]=res[0]+1=0. No cut is needed.

In order to check the valid palindrome more efficient, a dictionary is built upfront use the same method as the previous problem: Palindrome Partitioning 

  public int minCut(String s) {  
    if(s==null || s.length()==0) return 0;  
    boolean[][] dict=getDict(s);  
    int[] res= new int[s.length()+1];  
    res[0]=-1;  
    for(int i=1;i<=s.length();i++){  
      res[i]=res[i-1]+1;  
      for(int j=0;j<i-1;j++){  
        if (dict[j][i-1]){  
          res[i]=Math.min(res[i],res[j]+1);  
        }  
      }  
    }  
    return res[s.length()];  
   }  
   public boolean[][] getDict(String s){  
     boolean[][] dict=new boolean[s.length()][s.length()];  
     for(int i=s.length()-1;i>=0;i--){  
       for(int j=i;j<s.length();j++){  
         dict[i][j]=(j-i<=1 || dict[i+1][j-1]) && s.charAt(i)==s.charAt(j);  
       }  
     }  
     return dict;  
   }  

131. Palindrome Partitioning Leetcode Java

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution:

First of all, build a dictionary to get all palindrome substring from i to j. 

Then recursively get all valid palindrome partitions.

The recursion steps:

Base case/terminating case:

When start>=s.length() output this valid partition.

Try s.substring(start,i) if it is a valid palindrome then recursively to find next valid palindrome substring starting at index i+1. 

Back track and then try s.substring(start, i+1)...

  public List<List<String>> partition(String s) {  
     List<List<String>> res=new ArrayList<List<String>>();  
     if(s==null || s.length()==0) return res;  
     boolean[][] dict=getDict(s);  
     helper(dict,s,0,new ArrayList<String>(), res);  
     return res;  
   }  
   public void helper(boolean[][] dict, String s,int start, List<String> items, List<List<String>> res){  
     if(start>=s.length()){  
      List<String> temp=new ArrayList<String>(items);  
      res.add(temp);  
      return;  
     }  
     for(int i=start; i<s.length();i++){  
       if(dict[start][i]){  
         items.add(s.substring(start,i+1));  
         helper(dict,s,i+1,items,res);  
         items.remove(items.size()-1);  
       }  
     }  
   }  
   public boolean[][] getDict(String s){  
     boolean[][] dict=new boolean[s.length()][s.length()];  
     for(int i=s.length()-1;i>=0;i--){  
       for(int j=i;j<s.length();j++){  
         dict[i][j]= (j-i<=1 || dict[i+1][j-1])&& s.charAt(i)==s.charAt(j);  
       }  
     }  
     return dict;  
   }  

130. Surrounded Regions Leetcode Java

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Solution:

From the description of the problem, we know that if 'O' is surrounded by 'X' it will be flipped. The way a 'O' is not surrounded is that, there exist a path that lead this 'O' to the boundaries of the board. Eg. the only one placed on the bottom boundary is not surrounded by 'X'. 

Let's think it in the opposite way:

1. any 'O' on the boundary is not surrounded by 'X'. Let's call this 'O' BO;

2. all 'O's that are BO's neighbors are not surrounded by 'X', neighbors means left, right, bottom, up. 

3. all 'O' that can reached by BO are not surrounded by 'X'. Reached by BO means, there exist a path from BO to the 'O' and the path is consisted of only 'O's. 

Clearly, we can do DFS/BFS starting from all BOs and mark all the reachable 'O' as "Don't flip" and flip all other 'O's to 'X'

Tips: use '*' to mark the position as "Don't flip". Flip after search by flip 'O' to 'X' and restore '*' to 'O'.

  public void solve(char[][] board) {  
     if(board==null || board.length==0 || board[0].length==0) return;  
     for(int i=0;i<board.length;i++){  
       if (board[i][0]=='O') helper(board,i,0);  
       if (board[i][board[0].length-1]=='O') helper(board,i,board[0].length-1);  
     }  
     for(int j=0;j<board[0].length;j++){  
       if(board[0][j]=='O') helper(board,0,j);  
       if(board[board.length-1][j]=='O') helper(board,board.length-1,j);  
     }  
     for(int i=0;i<board.length;i++){  
       for(int j=0;j<board[0].length;j++){  
         if(board[i][j]=='O') board[i][j]='X';  
         if(board[i][j]=='*') board[i][j]='O';  
       }  
     }  
   }  
   public void helper(char[][] board, int i, int j){  
      LinkedList<Integer> q=new LinkedList<Integer>();  
      int ind=i*board[0].length+j;  
      board[i][j]='*';  
      q.offer(ind);  
      while(!q.isEmpty()){  
        int temp=q.poll();  
        int row=temp/board[0].length;  
        int col=temp%board[0].length;  
        if(row-1>=0 && board[row-1][col]=='O') {  
          q.offer(temp-board[0].length);  
          board[row-1][col]='*';    
        }  
        if(row+1<board.length && board[row+1][col]=='O'){  
          q.offer(temp+board[0].length);  
          board[row+1][col]='*';  
        }  
        if(col-1>=0 && board[row][col-1]=='O'){  
          q.offer(temp-1);  
          board[row][col-1]='*';  
        }  
        if(col+1<board[0].length && board[row][col+1]=='O') {  
          q.offer(temp+1);  
          board[row][col+1]='*';  
      }  
   }  
  }  

129. Sum Root to Leaf Numbers Leetcode Java

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Solution:

Recursion:

Recursion equation: V(root)=curSUM*10+V(left)+V(right). 

Base case: root==null-> return 0, if root is leaf, return curSUM*10+root.val;

    public int sumNumbers(TreeNode root) {  
     return helper(root,0);  
   }  
   public int helper(TreeNode root, int cur){  
     if(root==null) return 0;  
     if(root.left==null && root.right==null) return cur*10+root.val;  
     return helper(root.left, cur*10+root.val)+helper(root.right,cur*10+root.val);  
   }  

128. Longest Consecutive Sequence Leetcode Java

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solution:

Intuitive solution: Sort the the array, and check all consecutive sequences and find the longest. Time complexity:O(nlogn)

Advance solution 1: consider it as intervals, eg. let's use the example given in the problem, [100](interval with size 1); [4]; [200]; [1]; when we process 3, we find that, it is mergeable with[4], [3,4]; after that when we process 2, we find that it can be merged with both [1], [3,4] => [1,2,3,4], so I use a hashmap to store the intervals information: start/end with the length, for each processing integer, check if the map contains its consecutive numbers if yes, then this number can be merged with stored intervals. Then update the stored intervals accordingly. 

Time complexity: O(n). O(n) extra space 

 public int longestConsecutive(int[] num) {  
    if(num==null || num.length==0) return 0;  
    int res=1;  
    HashMap<Integer, Integer> map=new HashMap<Integer,Integer>();  
    for(int i=0;i<num.length;i++){  
      if(map.containsKey(num[i])) continue;  
      if(map.containsKey(num[i]-1) && map.containsKey(num[i]+1)){  
        int start=num[i]-map.get(num[i]-1);  
        int end=num[i]+map.get(num[i]+1);  
        map.put(start,end-start+1);  
        map.put(end,end-start+1);  
        map.put(num[i],1);  
        res=Math.max(res,end-start+1);  
      }  
      else if(map.containsKey(num[i]-1)){  
        int start=num[i]-map.get(num[i]-1);  
        map.put(start,num[i]-start+1);  
        map.put(num[i],num[i]-start+1);  
        res=Math.max(res,num[i]-start+1);  
      }  
      else if(map.containsKey(num[i]+1)){  
        int end=num[i]+map.get(num[i]+1);  
        map.put(end,end-num[i]+1);  
        map.put(num[i],end-num[i]+1);  
        res=Math.max(res,end-num[i]+1);  
      }  
      else map.put(num[i],1);  
    }  
    return res;  
   }  

Advance solution 2:
Use a hashset to store all the integers, determine the upper boundary and lower boundary by checking if the hashset contains the consecutive numbers one by one. If yes, remove the number in the hashset. So the total time will be O(2*n)=O(n). O(n) extra space

  public int longestConsecutive(int[] num) {  
    if(num==null || num.length==0) return 0;  
    int res=1;  
    HashSet<Integer> helper=new HashSet<Integer>();  
    for(int i=0;i<num.length;i++){  
      helper.add(num[i]);  
    }  
    for(int i=0;i<num.length;i++){  
      if(!helper.contains(num[i])) continue;  
      int temp=num[i];  
      int r=1;  
      while(helper.contains(temp+r)){  
        helper.remove(temp+r);  
        r++;  
      }  
      int l=1;  
      while(helper.contains(temp-l)){  
        helper.remove(temp-l);  
        l++;  
      }  
      res=Math.max(l+r-1,res);  
    }  
    return res;  
   }  

127. Word Ladder Leetcode Java

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:

BFS

Consider this transformation as a graph, each word is node, and two nodes are connected by an edge if they are transformable. The shortest length from start to end can be found by using Breadth first search. 

I use a queue to implement the BFS, each time when we process a node and visit its neighbors by checking if current node can be transfer to another node in the dictionary. We replace each char in the current node string to any other letters from 'a' to 'z', because the dictionary only contains words. By doing so, we can improve the time complexity,because 26 is a constant. Once we we touch the end word, we can directly output the levels/ lengths.

Time complexity: O(m*n) where m is the dictionary's size and n is the word's length.  

 public int ladderLength(String start, String end, Set<String> dict) {  
     if(start==null||start.length()==0 || start.length()!=end.length()) return 0;  
     LinkedList<String> q=new LinkedList<String>();  
     HashSet<String> used=new HashSet<String>();  
     q.offer(start);  
     used.add(start);  
     int level=1;  
     int curL=0;  
     int lastL=1;  
     while(!q.isEmpty()){  
       String cur=q.poll();  
       lastL--;  
       char[] temp=cur.toCharArray();  
       for(int i=0;i<temp.length;i++){  
         char c=temp[i];  
         for(char j='a';j<='z';j++){  
           temp[i]=j;  
           String replaced=new String(temp);  
           if(replaced.equals(end)) return level+1;  
           if(dict.contains(replaced) && !used.contains(replaced)){  
             q.offer(replaced);  
             used.add(replaced);  
             curL++;  
           }  
         }  
         temp[i]=c;  
       }  
       if(lastL==0){  
         level++;  
         lastL=curL;  
         curL=0;  
       }  
     }  
     return 0;  
   }  

125. Valid Palindrome Leetcode Java

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Solution:

The solution is simple. Two pointers, one from left to right, the other one from right to left. Only consider alphabetic characters and ignore all other characters. Return false once we find the unmatched chars. Otherwise, move two pointers towards each other till they meet.
Time complexity: O(n)

 public boolean isPalindrome(String s) {  
    if(s==null) return false;  
    int l=0;  
    int r=s.length()-1;  
    while(l<r){  
      if(!isValidChar(s.charAt(l))){  
        l++;  
        continue;  
      }  
      if(!isValidChar(s.charAt(r))){  
        r--;  
        continue;  
      }  
      if(Character.toLowerCase(s.charAt(l))!=Character.toLowerCase(s.charAt(r))) return false;  
      l++;  
      r--;  
    }  
    return true;  
   }  
   public boolean isValidChar(char c){  
     return (c<='z'&& c>='a') || (c<='Z' && c>='A') || (c<='9' && c>='0');   
   }