/** Precondition: the puzzle grid contains the distinct values 0 through  side^2 - 1
   *  @return true if the tiles in the puzzle are all arranged in increasing order
   *               (the hole value 0 may be in any position);
   *          false otherwise
  */
  public boolean isDone()
  {
    int prev = 0;

    for (int r = 0; r < side; r++)
    {
      for (int c = 0; c < side; c++)
      {
        int num = values[r][c];
        if (num != 0)
        {
          if (num != prev + 1)
            return false;
          prev = num;
        }
      }
    }
    return true;
  }

  /** Initializes the puzzle by placing numbers 0 through side^2 - 1 into random locations
   */
  public void initialize()
  {
    ArrayList<Integer> temp = new ArrayList<Integer>();
    for (int j = 0; j < side * side; j++)
      temp.add(new Integer(j)); 1

    for (int r = 0; r < side; r++)
    {
      for (int c = 0; c < side; c++)
      {
        int i = (int)(Math.random() * temp.size());
        values[r][c] = temp.get(i).intValue();
        temp.remove(i); 2
      }
    }
  }

1. These three lines were given.
   
   
2. Or:

         values[r][c] = temp.remove(i).getValue();
   

   Or simply

         values[r][c] = temp.remove(i);
   

   due to autounboxing.

O(n²) ¹

Notes:

1. Because the remove method in an ArrayList on average takes O(n) time.

O(n)