Before we talk about autoboxing, we see three lines of codes:

Map<String, Integer> map = new HashMap<String, Integer>();
map.put("hello", 1);
map.put("hello", map.get("hello")+1);

Here we define this map’s value type is Integer, but we still can put int(1) into this map. Meanwhile, when we get this map’s value as Integer, we still can let Integer plus 1. Why? This is what we want to talk on this blog.

First, int is a primitive type; Integer is generics. We can’t put an int(or other primitive value) into a collection. Collections can only hold object references, so we have to box primitive values into appropriate wrapper class(which is Integer in the case of int). When we take the object out of the collection, we get the Integer that we put in; if we need an int, we must unbox the Integer using the intValue method.

Autoboxing means we can write:

map.put("hello", 1);

instead of :

map.put("hello", new Integer(1));

Autoboxing means the first version is implicitly converted to the second.

Auto-unboxing means we can write :

int a = map.get("hello");

instead of:

int a = map.get("hello").intValue();

This implicit call to intValue() means if the key isn’t found it, it will generate a NullPointerException.

All of this boxing and unboxing is a pain and clutters up our code. Here autoboxing and unboxing feature automate the process, eliminating the pain and the clutter.

Untitled Diagram.html -


hashCode() and equals() in Java

By default, the Java super class java.lang.Object provides two important methods for comparing objects: equals() and hashCode();

  • equals(Object obj): The default implementation provided by the JDK is based on memory location: two objects are equal if and only if they are stored in the same memory address.
  • hashCode(): By default, this method returns a random integer that is unique for each instance. This integer might change between several executions of the application and won’t stay the same.

The contraction between equals() and hashCode():

In some business scenarios, developers provide their own implementation in order to force their own equality mechanism regardless the memory addresses. It is not enough to just implement the equals() method. If two objects are equal according to the equals(Object) method, then calling the hashCode() method on each of the two objects must produce the same integer result.

Practical Example:

  1. We define a class called Coord as the following:
    public class Coord {
        private int i;
        private int j;
        public Coord(int x, int y) {
            this.i = x;
            this.j = y;
  2. Overriding equals()
    public boolean equals(Object obj) {
        return (obj instanceof Coord) && ((Coord)obj).i==i && ((Coord)obj).j==j;
  3. Override hashCode()
    public int hashCode() {
        int hashCode = 1;
        hashCode = 31*hashCode+i;
        hashCode = 31*hashCode+j;
        return hashCode;


In order to achieve a fully working custom equality mechanism, it is mandatory to override hashCode() each time you override equals().

  • If two objects are equal, they must have the same hash code.
  • If two objects have the same hash code, it doesn’t mean that they are equal.
  • Overriding equals() alone will make your business fail with hashing data structure like HashSet, HashMap, HashTable … etc
  • Overriding hashCode() alone doesn’t force Have to ignore memory addresses when comparing two objects.

Algorithms Tips (4) – Basic Data Structure

Here we record some basic data structures which are easily involved in coding.

  • PriorityQueue
    Sometimes, we want to sort hashmap by its value, we can introduce PriorityQueue to override its compare function to reach the goal. (Laster, I will add more compare function to popular PriorityQueue’s field.)

     Map<Integer, Integer> tweets = new HashMap();
     PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
       public int compare(Integer a, Integer b) {
         return tweets.get(b) - tweets.get(a);
         // tweets.get(a)-tweets.get(b) is increasing/ascending
         // tweets.get(b)-tweets.get(a) is downing trend
     pq.poll(); //return head and delete head 
     pq.peek(); // return head
  • Set
    If we want to add unique value to the output, we can use set as an intermedium variable to help to check during adding process.

    Set set = new HashSet();
    Iterator iterator = set.iterator();
    while(iterator.hasNext()) {
      String elem =;
  • TreeMap
    A TreeMap provides an efficient means of sorting key/value pairs in sorted order and allows rapid retrieval. Its elements will be sorted in an ascending key order.

    TreeMap tm = new TreeMap();
    tm.put("a", 2);
    tm.put("b", 1);
    tm.get("a"); // return 2
    tm.lastKey(); // return "b"
    tm.firstKey(); // return "a"
    TreeMap<Integer, HashSet> t = new TreeMap();
    // if HashSet's size is zero, we need to use t.remove(key) to 
    remove this element in TreeMap. Because its null value will 
    influence TreeMap's firstKey and lastKey result.
  • List
    Arrays.asList("a", "b");// initialize List with values
    // List to Array
    lists.toArray(new String[lists.size()]);

    For recursion method, we might need to copy the last result to current result. For example, for f(i-1), its result is left (List<Integer>) and for f(i), its result is to merge left with current value.
    Wrong version:

     List<List<Integer>> rec = new ArrayList<List<Integer>>():
     for(List<Integer> left: lefts) {

    Right version:

     List<List<Integer>> rec = new ArrayList<List<Integer>>():
     for(List<Integer> left: lefts) {
       ArrayList<Integer> elem = new ArrayList<Integer>(left);

    The problem of the wrong version is that it will change left’s content. For example, if left=[[], [1]] and nums[1]=2, the wrong version’s output is [[2],[1,2],[2],[1,2]]. For the right version, it creates a new ArrayList to physically build a new list, so later add method won’t change original content. So the right output is [[], [1], [2], [1,2]].

  • Stack
    Stack<String> s = new Stack();
  • String
    int integer = 1;
    String t = String.valueOf(integer);

The string is very common, so the only special point is to convert to char[] when needed.

  •  char[] arr = str.toCharArray();
     String t = String.valueOf(arr);
     String t1 = new String(arr);


Algorithm Tips (3) – Building Suitable Data Structure

The more LeetCode questions we practice, the more rules we find. We can split all questions to serval categories, such as Stack, Map/HashMap, Dynamic Programming, etc. It looks good to use these existing data structure to improve the solution, but sometimes, we still need to build our own suitable data structure to fit some questions’ special scenario.

Today I take “Binary Tree Maximum Path Sum” as an example. (Later, I will enhance this post by adding more examples.)


Given a binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.


For any node, it has two cases, one is single side(not circle), the other is go-through-circle. We need to record the two cases for each node and then to be provided to parent’s node to evaluate. So it is quite clear to solve the problem. Now you can use int[] which contains 2 elements to code it, but we all know it is not the good one and hard to read. The better solution is to build our own data structure to describe the two cases clearly.

private class ResultType {
  int singlePath, maxPath;
  ResultType(int singlePath, int maxPath) {
    this.singlePath = singlePath;
    this.maxPath = maxPath;

Here we conclude above two cases to two parameters: singlePath is to record the maximum path for single side(not circle) and maxPath to record the maximum value for the current node, including circle case and non-circle case. So the whole codes are here:

 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode(int x) { val = x; }
 * }
public class Solution {
   private class ResultType {
     int singlePath, maxPath;
     ResultType(int singlePath, int maxPath) {
       this.singlePath = singlePath;
       this.maxPath = maxPath;
   public int maxPathSum(TreeNode root) {
     ResultType res = helper(root);
     return res.maxPath;
   public ResultType helper(TreeNode root) {
     if (root == null) 
       return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);
     ResultType left = helper(root.left);
     ResultType right = helper(root.right);
     int singlePath = Math.max(0, 
             Math.max(left.singlePath, right.singlePath)) + root.val;
     int maxPath = Math.max(left.maxPath, right.maxPath);
     maxPath = Math.max(maxPath, 
             Math.max(left.singlePath, 0)+
                      Math.max(right.singlePath, 0)+root.val);
     return new ResultType(singlePath, maxPath);

We see parent’s singlePath = Max(their children’s singlePath + root value) and parent’s maxPath = Max( children’s maxPath,  children’s singlePath + root value).

Meanwhile, we comparing singlePath with zero, to determine whether to involve it or not.

Another clever point is to return Integer.MIN_VALUE, not zero for the empty node. This is very clever to solve the case, like only one node with a negative value. Because in this case, this negative value is still the maximum value for this node.

Algorithm Tips (2) – Avoiding Data Overflow

Today we talk about overflow. This is a very shy problem when interviewing. And it is also a very good way to distinguish whether you are a good programmer or just so-so programmer.

When I interviewed in a big company (I forgot its name, maybe eBay), the interviewer asked me to write a sum function. So easy?! In fact, No. You have to consider overflow for your solution.

Concept of Overflow and Underflow

First, let’s understand what’s overflow and what’s underflow. Overflow and underflow are related to a data type. Every data type has its own range. For example, int, in Java, you can use Integer.MIN_VALUE and Integer.MAX_VALUE to know its range. In Java arithmetic operators, it doesn’t report overflow and underflow problem and never throws an error exception. It just simply swallows it.

  • int operators:
    When the value of an operation is larger than 32 bits, then the low 32 bits only taken into consideration and the high order bits are discarded. And when its most significant bit(MSB) is 1 then the value is treated as negative.
  • floating point operators:
    Overflow will result in Infinity and underflow will result as 0.0.

Solutions to avoid overflow or underflow

Second, there are several ways to avoid it.

  • using long to replace int
  • using uint to replace int
  • using double to apply intermediate variable
  • use the mod method to avoid it, This is a very common solution in LeetCode, within the question, it already obviously reminds you to use mod 100000007 if the answer is very large.


Finally, I list my solution for LeetCode-576 (Out of Boundary Paths) (Here I don’t list the content of the question, you can read it from LeetCode’s website. ) to help you understand how to avoid overflow issue. Meanwhile, it is a good way to see how to use three dimensions array to fix the problem with dynamic programming method.

public class Solution {
  public int findPaths(int m, int n, int N, int i, int j) {
    final int MOD = 1000000007;
    if (N == 0) return 0;
    long[][][] dp = new long[m][n][N+1]; //k:1-N
    for(int ii=0; ii<m;ii++) {
      for(int jj=0; jj<n;jj++) {
        int count = 0;
        if (ii-1<0) count++;         if (ii+1>=m) count++;
        if (jj-1<0) count++;         if (jj+1>=n) count++;
        dp[ii][jj][1] = count;
    for(int k=2; k<=N;k++) {
      for(int ii=0; ii<m; ii++) {
        for(int jj=0; jj<n; jj++) {
          long count = 0;
          if (ii-1>=0) count += dp[ii-1][jj][k-1];
          if (jj-1>=0) count += dp[ii][jj-1][k-1];
          if (ii+1<m) count += dp[ii+1][jj][k-1];
          if (jj+1<n) count += dp[ii][jj+1][k-1];
          dp[ii][jj][k] = count%MOD;
    long rec = 0;
    for(int k=1; k<=N; k++) {
      rec += dp[i][j][k];
    return (int)(rec%MOD);

Another simple LeetCode question also requires us to consider overflow issue: Valid Binary Search Tree. Here is the solution which considers using Long to replace Integer to avoid overflow.

 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode(int x) { val = x; }
 * }
public class Solution {
 public boolean isValidBST(TreeNode root) {
   return isValidBSTCheck(root, Long.MIN_VALUE, Long.MAX_VALUE);
 public boolean isValidBSTCheck(TreeNode root, long min, long max) {
   if (root == null) return true;
   if (root.val > min && root.val < max) {
     return isValidBSTCheck(root.left, min, root.val) && isValidBSTCheck(root.right, root.val, max);
   } else return false;