Maximum Contiguous Subsequence Sum in Linearithmic Time Recursively in Java

There are different solutions to maximum subsequence sum problem with varying complexities such as linear, quadratic and cubic.

There is also a linearithmic solution for the maximum subsequence sum problem implemented in Java.

This linearithmic solution is achieved by applying a divide-and-conquer algorithm design strategy.

Algorithm divides the input array into two different parts from the middle and then searches the max sum
1-) in the first half
2-) in the second half
3-) in the sub array that crosses the mid point of the array

1st and 2nd cases are achieved with recursive calls.

3rd case is achieved by as described at :

"by finding the largest sum in the first half that includes the last element in the first half, and the largest sum in the second half that includes the first element in the second half."

package basics;

public class MaxSubSumLinearithmic {

 public static int maxSubSum(int[] inArr) {
  return maxSubSum( inArr, 0, inArr.length-1 );
 }

 public static int maxSubSum(int[] inArr, int left, int right) {

  if (left == right)
   if (inArr[left] > 0)
    return inArr[left];
   else
    return 0;

  int mid = (left + right) / 2;
  int maxLSum = maxSubSum( inArr, left, mid);
  int maxRSum = maxSubSum( inArr, mid+1, right);

  int maxLBorderSum = 0, leftBorderSum = 0;
  for (int i = mid; i >= left; i--) {
   leftBorderSum += inArr[i];
   if ( leftBorderSum > maxLBorderSum )
    maxLBorderSum = leftBorderSum;
  }

  int maxRBorderSum = 0, rightBorderSum = 0;
  for (int i = mid + 1; i <= right; i++) {
   rightBorderSum += inArr[i];
   if ( rightBorderSum > maxRBorderSum )
    maxRBorderSum = rightBorderSum;
  }

  return getMax3( maxLSum, maxRSum, maxLBorderSum+maxRBorderSum );
 }
 
 private static int getMax3( int a, int b, int c )
 {
      return a > b ? a > c ? a : c : b > c ? b : c;
 }

 public static void main(String[] args) {

  int input[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 3, -16, 100, -4, 5 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 11, -4, 13, -5, 2 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -15, -23, -476, -3, -292 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));
 }
}

Create a MaxSubSumLinearithmic.java file in your workspace.

When the main method inside the MaxSubSumLinearithmic class executed it is going to print :

Max Sub Array Sum Result = 7
Max Sub Array Sum Result = 101
Max Sub Array Sum Result = 20
Max Sub Array Sum Result = 0


References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Divide and Conquer Solution to Max Sub Sum

Finding-maximum-contiguous-subsequence-sum-using-divide-and-conquer-approach

Max Sub Array Problem Definition from Wikipedia

Finding Maximum of Three Integers in Java

Finding maximum of three integers problem helps to understand if-else branching and conditionals topic in a better way.

Following is the implementation of the find maximum of three integers in Java.

package basics;

public class ThreeComparator {

 public static int max3( int a, int b, int c )
 {
  if( a>b )
  {
   if( a > c )
       return a;
   else
       return c;
  }
  else if( b>c )
  {
                 return b;
  }
  else
  {
   return c;
  }
  
 }
 
 public static void main(String[] args) {
  
  int a = 4;
  int b = 3;
  int c = 5;
  
  System.out.println("Maximum of "+a+" , "+b+" and "+c+" is = "+max3( a,b,c ));
  System.out.println("Maximum of "+a+" , "+c+" and "+b+" is = "+max3( a,c,b ));
  System.out.println("Maximum of "+b+" , "+a+" and "+c+" is = "+max3( b,a,c ));
  System.out.println("Maximum of "+b+" , "+c+" and "+a+" is = "+max3( b,c,a ));
  System.out.println("Maximum of "+c+" , "+a+" and "+b+" is = "+max3( c,a,b ));
  System.out.println("Maximum of "+c+" , "+b+" and "+a+" is = "+max3( c,b,a ));
  
  System.out.println("Maximum of 4 , 5 and 4 is = "+max3( 4,5,4 ));
  System.out.println("Maximum of 41 , 41 and 41 is = "+max3( 41,41,41 ));
  System.out.println("Maximum of 11 , 21 and 31 is = "+max3( 11,21,31 ));  
 }
}

Create a ThreeComparator.java file in your workspace.

When the main method inside the ThreeComparator class executed it is going to print :

Maximum of 4 , 3 and 5 is = 5
Maximum of 4 , 5 and 3 is = 5
Maximum of 3 , 4 and 5 is = 5
Maximum of 3 , 5 and 4 is = 5
Maximum of 5 , 4 and 3 is = 5
Maximum of 5 , 3 and 4 is = 5
Maximum of 4 , 5 and 4 is = 5
Maximum of 41 , 41 and 41 is = 41
Maximum of 11 , 21 and 31 is = 31

Power of a Number Implementation Recursive in Java

Calculation of exponentiation returns the value of the base number a raised to the exponent n.

Following is the recursive implementation of the power method in Java.

package basics;

public class PowerCalculator {

 public static long pow(long base, int n) {
  
  if (n == 0)
      return 1;
  
  if (n == 1)
      return base;
  
  if (n%2==0)
      return pow( base*base, n/2 );
  else
      return pow( base*base, n/2 )*base;
 }

 public static void main(String[] args) {
  
  long base = 2;
  int exponent = 4;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
  base = 3;
  exponent = 5;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
  base = 5;
  exponent = 4;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
 }
}

Create a PowerCalculator.java file in your workspace.

When the main method inside the PowerCalculator class executed it is going to print :

Result of 2 to the 4 is = 16
Result of 3 to the 5 is = 243
Result of 5 to the 4 is = 625


References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Exponentiation in Wiki

Math pow method

Java 7 Math.pow implementation

For big numbers you can use Java-BigInteger

Greatest Common Divisor GCD Implementation Recursive and Iterative in Java

The greatest common divisor (gcd) of two integers is the largest positive integer that divides the numbers without a remainder.

For example, the GCD of 8 and 12 is 4.

package basics;

public class GCD {

 public static long gcdRecursive(long a, long b) {
  
  if (a == 0)
   return b;
  if (b == 0)
   return a;
  if (a > b)
   return gcdRecursive(b, a % b);
  
  return gcdRecursive(a, b % a);
 }

 public static long gcdIterative(long m, long n) {
  
  while ( m!=0 && n != 0 ) {
   long remainder = m % n;
   m = n;
   n = remainder;
  }
  return m+n;
 }
 
 public static void main(String[] args) {
  
  System.out.println("Recursive GCD of 50 and 0 = "+gcdRecursive(50,0));
  System.out.println("Recursive GCD of 0 and 50 = "+gcdRecursive(0,50));
  System.out.println("Recursive GCD of 50 and 10 = "+gcdRecursive(50,10));
  System.out.println("Recursive GCD of 40 and 9 = "+gcdRecursive(40,9));
  System.out.println("Recursive GCD of 8 and 12 = "+gcdRecursive(8,12));
  System.out.println();
  
  System.out.println("Iterative GCD of 50 and 0 = "+gcdIterative(50,0));
  System.out.println("Iterative GCD of 0 and 50 = "+gcdIterative(0,50));
  System.out.println("Iterative GCD of 50 and 10 = "+gcdIterative(50,10));
  System.out.println("Iterative GCD of 40 and 9 = "+gcdIterative(40,9));
  System.out.println("Iterative GCD of 8 and 12 = "+gcdRecursive(8,12));
 }

}

Create a GCD.java file in your workspace.

When the main method inside the GCD class executed it is going to print :

Recursive GCD of 50 and 0 = 50
Recursive GCD of 0 and 50 = 50
Recursive GCD of 50 and 10 = 10
Recursive GCD of 40 and 9 = 1
Recursive GCD of 8 and 12 = 4


Iterative GCD of 50 and 0 = 50
Iterative GCD of 0 and 50 = 50
Iterative GCD of 50 and 10 = 10
Iterative GCD of 40 and 9 = 1
Iterative GCD of 8 and 12 = 4


References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Wikipedia = Greatest Common Divisor

Maximum Contiguous Subsequence Sum in Quadratic Time in Java

Finding the maximum contiguous subsequence sum of an array of integers among other subsequences is one of the basic problems about operations on arrays, indices and complexity analysis.

For the array {-2, -3, 4, -1, -2, 1, 5, -3}   the maximum subsequence sum contains elements
"4, -1, -2, 1, 5" so the sum = 4+(-1)+(-2)+1+5 = 7.

Using two for loops gives the solution so it is a quadratic O(n²) solution to maximum contiguous subsequence sum in quadratic time in Java.

Removing one of the extra for loops also helps to get rid of expensive operations so the quadratic time becomes preferable to cubic time solution.

package basics;

public class MaxSubSumQuadratic {

 public static int maxSubSum(int[] inArr) {

  int maxSum = 0;

  for (int i = 0; i < inArr.length; i++) {
   
   int thisSum = 0;
   
   for (int j = i; j < inArr.length; j++) {
   
    thisSum += inArr[j];

    if (thisSum > maxSum)
     maxSum = thisSum;
    
   }   
  }

  return maxSum;
 }

 public static void main(String[] args) {

  int input[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 3, -16, 100, -4, 5 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 11, -4, 13, -5, 2 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -15, -23, -476, -3, -292 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));
 }

}

Create a MaxSubSumQuadratic.java file in your workspace.

When the main method inside the MaxSubSumQuadratic class executed it is going to print :

Max Sub Sum Result = 7
Max Sub Sum Result = 101
Max Sub Sum Result = 20
Max Sub Sum Result = 0



References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Maximum Contiguous Subsequence Sum in Linear Time in Java

Finding the maximum contiguous subsequence sum of an array of integers among other subsequences is one of the basic problems about operations on arrays, indices and complexity analysis.

For the array {-2, -3, 4, -1, -2, 1, 5, -3}   the maximum subsequence sum contains elements
"4, -1, -2, 1, 5" so the sum = 4+(-1)+(-2)+1+5 = 7.

Using one for loop gives the solution so it is a linear O(n) solution to maximum contiguous subsequence sum in linear time in java.

In this solution inside the for loop, if the currently added item leads to a larger result then the previous maximum then this becomes the new maximum.

If the newly added item leads to a negative sum result then the current sum is assigned the "0".

This solution works for the arrays that contain at least one positive integer.

package basics;

public class MaxSubSumLinear {

 public static int maxSubSum(int[] inArr) 
 {  
  int maxSum = 0, currentSum = 0;

  for (int j = 0; j < inArr.length; j++) {
   currentSum += inArr[j];

   if ( currentSum > maxSum)
    maxSum = currentSum;
   else if ( currentSum < 0)
    currentSum = 0;
  }

  return maxSum;
 }

 public static void main(String[] args) {

  int input[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 3, -16, 100, -4, 5 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 11, -4, 13, -5, 2 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -15, -23, -476, -3, -292 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));
 }

}

Create a MaxSubSumLinear.java file in your workspace.

When the main method inside the MaxSubSumLinear class executed it is going to print :

Max Sub Sum Result = 7
Max Sub Sum Result = 101
Max Sub Sum Result = 20
Max Sub Sum Result = 0

References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Maximum Contiguous Subsequence Sum in Cubic Time in Java

Finding the maximum contiguous subsequence sum of an array of integers among other subsequences is one of the basic problems about operations on arrays, indices and complexity analysis.

For the array {-2, -3, 4, -1, -2, 1, 5, -3}   the maximum subsequence sum contains elements
"4, -1, -2, 1, 5" so the sum = 4+(-1)+(-2)+1+5 = 7.

Three different indexes defined to solve this problem which are i,j and k respectively.

Because of there are 3 for loops used to solve its time complexity is O(n³).

This solution works for the arrays that contain at least one positive integer.

package basics;

public class MaxSubSumCubic {

 public static int maxSubSum( int[] inArr )
 {
  int maxSum = 0;
  
  for (int i = 0; i < inArr.length; i++) {
   for( int j=i; j<inArr.length; j++ )
   {
    int currentSum = 0;
    
    for( int k=i; k<= j; k++ )
     currentSum += inArr[k];
    
    if( currentSum > maxSum )
     maxSum = currentSum;
   }
  }
  
  return maxSum;
 }
 
 public static void main(String[] args) {
  
  int input[] = {-2, -3, 4, -1, -2, 1, 5, -3};
  
  System.out.println("Max Sub Sum Result = "+maxSubSum(input));
  
  input = new int[]{ -2, 3, -16, 100, -4, 5 };
  
  System.out.println("Max Sub Sum Result = "+maxSubSum(input));
  
  input = new int[]{ -2, 11, -4, 13, -5, 2 };
  
  System.out.println("Max Sub Sum Result = "+maxSubSum(input));
  
  input = new int[]{ -15, -23, -476, -3, -292};
  
  System.out.println("Max Sub Sum Result = "+maxSubSum(input));
 }
}

Create a MaxSubSumCubic.java file in your workspace.

When the main method inside the MaxSubSumCubic class executed it is going to print :

Max Sub Sum Result = 7
Max Sub Sum Result = 101
Max Sub Sum Result = 20
Max Sub Sum Result = 0

References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Print Digits of A Number in Forward Or Backward Order in Java

Printing the separate digits of a number is another common example of using modulo operator.

Forward order display of separate digits of a number can be achieved with a recursive method and backward order display of separate digits of a number can be achieved with an iterative method in Java.

package basics;

public class PrintDigits {

 public static void printDigitsOfNumberInForwardOrder( int number )
 {
      if( number/10 > 0 )
          printDigitsOfNumberInForwardOrder(number/10);
  
      System.out.print(number%10+" ");
 }
 
 public static void printDigitsOfNumberInReverseOrder( int number )
 {
      while ( number > 0) {
          System.out.print(number%10+" ");
          number /= 10;
      }  
 }
 
 public static void main(String[] args) {
  
      int number = 1234;
      System.out.print("Digits of "+number+" in forward order are = ");
      printDigitsOfNumberInForwardOrder(number);
  
      number = 123429345;
      System.out.print("\nDigits of "+number+" in forward order are = ");
      printDigitsOfNumberInForwardOrder(number);
  
      number = 678123478;
      System.out.print("\nDigits of "+number+" in forward order are = ");
      printDigitsOfNumberInForwardOrder(number);
  
      number = 678123478;
      System.out.print("\nDigits of "+number+" in backward order are = ");
      printDigitsOfNumberInReverseOrder(number);
 }
}

Create a PrintDigits.java file in your workspace.

When the main method inside the PrintDigits class executed it is going to print :

Digits of 1234 in forward order are = 1 2 3 4
Digits of 123429345 in forward order are = 1 2 3 4 2 9 3 4 5
Digits of 678123478 in forward order are = 6 7 8 1 2 3 4 7 8
Digits of 678123478 in backward order are = 8 7 4 3 2 1 8 7 6

Static Generic Recursive Binary Search Algorithm In Java

Binary Search algorithm can be implemented recursively in a generic way in Java.

Generic recursive binary search method accepts input parameters as any item that implements Comparable interface.

Static binary search method was tested with Integer, Double and String type of parameters where each of them individually implements Comparable interface.

package basics;

import java.util.Arrays;

public class GenericRecursiveBinarySearch {

  public static <T extends Comparable<T>> int index( T[] items, T item )
  {
      return index( items, item, 0, items.length-1 );
  }
  
  public static <T extends Comparable<T>> int index( T[] items, T key, int low, int high )
  {
      if ( key == null )
          return -1;
   
      if( low > high  )
          return -1;
    
      int mid = low+(high-low)/2;
    
      if( key.compareTo( items[mid] ) > 0 )
          return index(items, key, mid+1, high);
      else if( key.compareTo( items[mid] ) < 0 )
          return index( items, key, low, mid-1 );
      else
          return mid;
  }  

  public static void main(String[] args) {

      Integer[] items = { 22, 55, 66, 11, 32, 56, 67, 89, 95, 10 };

      Arrays.sort(items);
      System.out.print("Sorted Integer Array = ");
      for (Integer item : items) {
           System.out.print(item+" ");
      }
  
      int foundIndex = index(items, Integer.valueOf(22));
      System.out.println("\nInteger Array Contains item 22 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(11));
      System.out.println("Integer Array Contains item 11 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(67));
      System.out.println("Integer Array Contains item 67 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(10));
      System.out.println("Integer Array Contains item 10 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(101));
      System.out.println("Integer Array Contains item 101 at index = " + foundIndex);

      foundIndex = index(items, null);
      System.out.println("Integer Array Contains item null at index = " + foundIndex);

      String[] strItems = { "alk", "abc", "adk", "zyt", "fre", "nhy" };
      Arrays.sort(strItems);

      System.out.print("\nSorted String Array = ");
      for (String item : strItems) {
           System.out.print(item+" ");
      }
  
      foundIndex = index(strItems, "alk");
      System.out.println("\nString Array Contains item alk at index = " + foundIndex);

      foundIndex = index(strItems, "nhy");
      System.out.println("String Array Contains item nhy at index = " + foundIndex);

      foundIndex = index(strItems, "zyt");
      System.out.println("String Array Contains item zyt at index = " + foundIndex);

      foundIndex = index(strItems, "zyts");
      System.out.println("String Array Contains item zyts at index = " + foundIndex);

      foundIndex = index(strItems, "null");
      System.out.println("String Array Contains item null at index = " + foundIndex);

      Double[] dItems = { 11.3, 13.3, 6.0, 9.6, 45.7, 23.2 };
      Arrays.sort(dItems);

      System.out.print("\nSorted Double Array = ");
      for (Double item : dItems) {
           System.out.print(item+" ");
      }
  
      foundIndex = index(dItems, 13.3);
      System.out.println("\nDouble Array Contains item 13.3 at index = " + foundIndex);

      foundIndex = index(dItems, 14.3);
      System.out.println("Double Array Contains item 14.3 at index = " + foundIndex);

      foundIndex = index(dItems, 23.0);
      System.out.println("Double Array Contains item 23.0 at index = " + foundIndex);

 }
}

Binary search works for sorted arrays so before calling binary search on arrays call Arrays.sort to sort array items.

Create a GenericRecursiveBinarySearch.java file in your workspace.

When the main method inside the GenericRecursiveBinarySearch class executed it is going to print :

Sorted Integer Array = 10 11 22 32 55 56 66 67 89 95
Integer Array Contains item 22 at index = 2
Integer Array Contains item 11 at index = 1
Integer Array Contains item 67 at index = 7
Integer Array Contains item 10 at index = 0
Integer Array Contains item 101 at index = -1
Integer Array Contains item null at index = -1

Sorted String Array = abc adk alk fre nhy zyt
String Array Contains item alk at index = 2
String Array Contains item nhy at index = 4
String Array Contains item zyt at index = 5
String Array Contains item zyts at index = -1
String Array Contains item null at index = -1

Sorted Double Array = 6.0 9.6 11.3 13.3 23.2 45.7
Double Array Contains item 13.3 at index = 3
Double Array Contains item 14.3 at index = -1
Double Array Contains item 23.0 at index = -1

Static Generic Iterative Binary Search Algorithm In Java

In order take advantage of Generics in Java, binary search method can be implemented generically.

Binary search works for sorted Arrays so Arrays.sort method is used before using binarySearch method.

Any type that implements Comparable interface is accepted by the generic iterative search method.

Built-in String, Integer and Double classes in Java implement Comparable interface so search method accepts these parameters.

package basics;

import java.util.Arrays;

public class GenericIterativeBinarySearch {

 public static <T extends Comparable<T>> boolean search( T[] items, T item ) {

  if (item == null) {
   return false;
  }

  int low = 0;
  int high = items.length - 1;

  while (low <= high) {

   int ix = low + (high - low) / 2;

   if (item.compareTo(items[ix]) < 0) {
    high = ix - 1;
   } else if (item.compareTo(items[ix]) > 0) {
    low = ix + 1;
   } else {
    return true;
   }
  }

  return false;
 }


 public static void main(String[] args) {

  Integer[] items = { 22, 55, 66, 11, 32, 56, 67, 89, 95, 10 };

  Arrays.sort(items);

  boolean found = search(items, Integer.valueOf(22) );
  System.out.println("Integer Array Contains item 22 = "+found);

  found = search(items, Integer.valueOf(11) );
  System.out.println("Integer Array Contains item 11 = "+found);

  found = search(items, Integer.valueOf(67) );
  System.out.println("Integer Array Contains item 67 = "+found);

  found = search(items, Integer.valueOf(10) );
  System.out.println("Integer Array Contains item 10 = "+found);

  found = search(items, Integer.valueOf(101) );
  System.out.println("Integer Array Contains item 101 = "+found);  
  
  found = search(items, null );
  System.out.println("Integer Array Contains item null = "+found); 
  
  String[] strItems = { "alk", "abc", "adk", "zyt", "fre", "nhy" };
  Arrays.sort(strItems);
  
  found = search( strItems, "alk" );
  System.out.println("String Array Contains item alk = "+found);
  
  found = search( strItems, "nhy" );
  System.out.println("String Array Contains item nhy = "+found);
  
  found = search( strItems, "zyt" );
  System.out.println("String Array Contains item zyt = "+found);
  
  found = search( strItems, "zyts" );
  System.out.println("String Array Contains item zyts = "+found);
  
  found = search( strItems, "null" );
  System.out.println("String Array Contains item null = "+found);
  
  Double[] dItems = { 11.3, 13.3, 6.0, 9.6, 45.7, 23.2 };
  Arrays.sort(dItems);
  
  found = search( dItems, 13.3 );
  System.out.println("Double Array Contains item 13.3 = "+found);
  
  found = search( dItems, 14.3 );
  System.out.println("Double Array Contains item 14.3 = "+found);
  
  found = search( dItems, 23.0 );
  System.out.println("Double Array Contains item 23.0 = "+found);  
  
 }
}

Create a GenericIterativeBinarySearch.java file in your workspace.

When the main method inside the GenericIterativeBinarySearch class executed it is going to print :

Integer Array Contains item 22 = true
Integer Array Contains item 11 = true
Integer Array Contains item 67 = true
Integer Array Contains item 10 = true
Integer Array Contains item 101 = false
Integer Array Contains item null = false
String Array Contains item alk = true
String Array Contains item nhy = true
String Array Contains item zyt = true
String Array Contains item zyts = false
String Array Contains item null = false
Double Array Contains item 13.3 = true
Double Array Contains item 14.3 = false
Double Array Contains item 23.0 = false

Find Permutations of a String Recursively in Java

In order to print all the permutations of a String a recursive method can be implemented.

In this recursive String permutation solution a StringBuilder instance is used as compared to other common String permutation implementations in Java.

package basics;

public class StringUtils {

 public static void permute( String str ) {
  print("", str);
 }

 private static void print(String leftPart, String str ) {

  int sLength = str.length();
  if ( sLength == 0) {
   return;
  } else if ( sLength == 1) {
   System.out.println(leftPart + str);
   return;
  }

  StringBuilder buffer = new StringBuilder(str);

  for (int i = 0; i < sLength; i++) {
   char temp = buffer.charAt(i);
   buffer.setCharAt(i, buffer.charAt(0));
   buffer.setCharAt( 0, temp );
   print( leftPart + temp, buffer.substring(1, sLength) );
  }
  
 }
 
 public static void main(String[] args) {
  
  String val = "abc"; 
  System.out.println("All Permutations of "+val);
  permute(val);  
  val = "abcd";
  System.out.println("All Permutations of "+val);
  permute(val);
  
 }

}

Create a StringUtils.java file in your workspace.

When the main method inside the StringUtils class executed it is going to print :

All Permutations of abc
abc
acb
bac
bca
cab
cba
All Permutations of abcd
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Palindrome String Check Recursively in Java

Palindrome String checking is one of the primitive exercises for String processing char-by-char.

Palindrome String check can also be implemented recursively in Java. This recursive implementation is not efficient as the iterative one because it calls String.substring() subsequently.

package basics;

public class StringUtils {

 public static boolean isPalindrome( String str )
 {
  int sLength = str.length();
  if ( sLength < 2) {
   return true;
  } else if ( str.charAt(0) != str.charAt( sLength-1 ) ) {
   return false; 
  } else if ( sLength == 2 ) {
   return true;
  } else { 
   return isPalindrome( str.substring( 1, sLength-1 ));
  }
  
 }
 
 public static void main(String[] args) {
  
  String str = "madam";
  boolean result = isPalindrome(str);
  System.out.println(str+" is Palindrome = "+result);
  
  str = "qqaacc";
  result = isPalindrome(str);
  System.out.println(str+" is Palindrome = "+result);
  
  str = "cocoococ";
  result = isPalindrome(str);
  System.out.println(str+" is Palindrome = "+result);
 }
}

Create a StringUtils.java file in your workspace.

When the main method inside the StringUtils class executed it is going to print :

madam is Palindrome = true
qqaacc is Palindrome = false
cocoococ is Palindrome = true

Find Max Integer From The First N Integers of Unsorted Array Recursively in Java

Searching a sorted integer array for a specific integer is a general use-case for most of the time.

But if it is required to search an unsorted array for the first N elements in order to find the maximum element then it is required to apply a different solution.

In order to find the maximum of first N elements of an unsorted array recursively following method can be used.

package basics;

public class NumberUtils {

 public static int getMaxItemFromSubArray( int[] inArray, int index ) {
  
  if( index <= 0 || index>inArray.length )
   return -1;
  
  if ( index == 1 ) {
   return inArray[0]; 
  }
  
  int m = getMaxItemFromSubArray( inArray, index-1 ); 
  
  if ( inArray[ index-1 ] > m) {
   return inArray[ index-1 ];
  } else {
   return m;
  }
  
 }

 public static void main(String[] args) {

  int[] items = { 0, 5, 73, 33, 201, 3, 441 };
  int maxItem = getMaxItemFromSubArray( items , 0 );
  System.out.println("Max Item is = " + maxItem);  
  
  maxItem = getMaxItemFromSubArray( items , 8 );
  System.out.println("Max Item is = " + maxItem);  
  
  maxItem = getMaxItemFromSubArray( items , 3 );
  System.out.println("Max Item is = " + maxItem);  
  
  maxItem = getMaxItemFromSubArray( items , 4 );
  System.out.println("Max Item is = " + maxItem); 
  
  maxItem = getMaxItemFromSubArray( items , 5 );
  System.out.println("Max Item is = " + maxItem); 
  
  maxItem = getMaxItemFromSubArray( items , 6 );
  System.out.println("Max Item is = " + maxItem); 
  
  maxItem = getMaxItemFromSubArray( items , 7 );
  System.out.println("Max Item is = " + maxItem); 
  
 }
}

Create a NumberUtils.java file in your workspace.

When the main method inside the NumberUtils class executed it is going to print :

Max Item is = -1
Max Item is = -1
Max Item is = 73
Max Item is = 73
Max Item is = 201
Max Item is = 201
Max Item is = 441

Sum of the Squares of the First n Numbers Recursively in Java

Formula for the sum of the squares of the first n numbers is described with the following equation in mathematics.

 f(n) = [n(n+1)(2n+1)]/6

In order to get the result for the sum of the first n integers in Java a recursive method can be used.

package basics;

public class NumberUtils {

 public static int sumOfFirstNSquares( int number )
 {
  if( number == 0 )
   return 0;
  
  return sumOfFirstNSquares(number-1)+(number*number);
 }
 
 public static void main(String[] args) {
  
  int sum = sumOfFirstNSquares(5);
  System.out.println("Sum is = "+sum);
  
  sum = sumOfFirstNSquares(7);
  System.out.println("Sum is = "+sum);
  
  sum = sumOfFirstNSquares(11);
  System.out.println("Sum is = "+sum);
 }
}

Create a NumberUtils.java file in your workspace.

If you are willing to work with real big numbers in Java then a BigInteger can be a solution.

When the main method inside the NumberUtils class executed it is going to print :

Sum is = 55
Sum is = 140
Sum is = 506

Print Singly Linked List in Reverse Order Recursively in Java

Arrays have got constant size restriction when they are created so it is expensive to resize them dynamically in an application. Instead of using arrays for resizing dynamic structure requirements, singly linked list data structure can be used.

Singly linked list has got a node based structure where each node has got next and data fields.

Above is a singly linked list with 1-2-3-4-5 elements.

In order to print data elements of each node of a singly linked list data structure in Java following forwardPrint and reversePrint methods can be used.

reversePrint is a recursive method and assumes that the head node is not null.

package basics;

public class LinkedList {

 static class Node
 {
  Node next;
  int data;
 }

 private Node head;
 
 public LinkedList(Node pHead) {
  head = pHead; 
 } 
 
 public void forwardPrint()
 {
  forwardPrint(head);
 }
 
 private void forwardPrint( Node node )
 { 
  Node current = head;
  while( current!=null )
  {
   System.out.println(current.data);
   current = current.next;
  }
 }
 
 public void reversePrint()
 {
  reversePrint(head);
 }
 
 private void reversePrint( Node node )
 {
  if( node.next != null )
   reversePrint(node.next);
  
  System.out.println(node.data);
 }
 
 public static void main(String[] args) {
  
  Node node1 = new Node();
  node1.data = 1;
  Node node2 = new Node();
  node2.data = 2;
  Node node3 = new Node();
  node3.data = 3;
  Node node4 = new Node();
  node4.data = 4;
  Node node5 = new Node();
  node5.data = 5;
  node1.next = node2;
  node2.next = node3;
  node3.next = node4;
  node4.next = node5;
  node5.next = null;
  
  LinkedList list = new LinkedList(node1);
  System.out.println("Forward Print Linked List = ");
  list.forwardPrint();
  System.out.println("Backward Print Linked List = ");
  list.reversePrint();
 }
}

Node objects are created separately and node1 object sent as the head of the linked list. Create a LinkedList.java file in your workspace.

When the main method inside the LinkedList class executed it is going to print :

Forward Print Linked List =
1
2
3
4
5
Backward Print Linked List =
5
4
3
2
1

Reverse int Array Iteratively in Java

A reverse of a primitive int array can be achieved by swapping elements from the start with the end iteratively.

If the swap operation of the primitive array elements starts from the index 0 then it is going to be enough to iterate till the half of the array.

Following is the in-place where there is no need to create-allocate a new array for reversing primitive array items implementation in Java.

package basics;

public class IterativeArrayReverse {

 private static void reverseArray( int[] inArr )
 {
     if ( inArr==null || inArr.length==0 )
         return ;
        
     int len = inArr.length;
     for( int i=0; i<len/2; i++ )
         swap(inArr, i, len-i-1);
 }
 
 private static void swap( int[] inArr, int i, int j )
 {
     int temp = inArr[i];
     inArr[i] = inArr[j];
     inArr[j] = temp;
 }
 
 public static void main(String[] args) {
  
     int[] arr = { 1,2,3,4,5,6 };
     System.out.println("Before Reverse");
     for( int i=0; i<arr.length; i++ )
         System.out.printf("%s ", arr[i]);  
  
     reverseArray( arr );
  
     System.out.println("\nAfter Reverse");
     for( int i=0; i<arr.length; i++ )
         System.out.printf("%s ", arr[i]);
  
     int[] arr2 = {4,3,6,2,7,8,9,5};
     System.out.println("\n\nBefore Reverse");
     for( int i=0; i<arr2.length; i++ )
         System.out.printf("%s ", arr2[i]);  
  
     reverseArray( arr2 );
  
     System.out.println("\nAfter Reverse");
     for( int i=0; i<arr2.length; i++ )
         System.out.printf("%s ", arr2[i]);
 }
}

Create a IterativeArrayReverse.java file in your workspace.

When the main method inside the IterativeArrayReverse class executed it is going to print :

Before Reverse
1 2 3 4 5 6
After Reverse
6 5 4 3 2 1

Before Reverse
4 3 6 2 7 8 9 5
After Reverse
5 9 8 7 2 6 3 4

Generic Method to Print Array Elements in Java

Generics in Java enable programmers to provide compile-time type-safety.

There are some main benefits of using generics in Java such as :

1-) Strong type-checking
2-) Elimination of casts
3-) Provide a way to develop generic algorithms

Methods can also be designed in a generic fashion in Java, too. Following generic method prints all the elements of an array one-by-one in a for-loop for both wrapper types and custom defined types.

package basics;

public class GenericPrint {

 static class Employee
 {
  String name;
  Employee(String pName)
  {
   name = pName;
  }
  
  public String toString() {
   return "[Employee Name = "+name+" ]";
  }
 }
 
 // Generic method
 public static <T> void print( T[] inParam )
 {
  for( T t: inParam )
  {
   System.out.printf("%s ", t);
  }
 }
 
 
 public static void main(String[] args) {
  
  String[] strArr = {"D1","D2","D3","D4"};  
  print(strArr);
  
  Integer[] intArr = { 1,2,3 };
  System.out.println();
  print(intArr);
  
  Double[] dArr = { 5.5, 6.6, 7.7 };
  System.out.println();
  print(dArr);
    
  Employee e1 = new Employee("Emply1");
  Employee e2 = new Employee("Emply2");
  Employee e3 = new Employee("Emply3");
  
  Employee[] empArr = { e1, e2, e3 };
  
  System.out.println();
  print(empArr);  
 } 
}

Create a GenericPrint.java file in your workspace.

When the main method inside the GenericPrint class executed it is going to print :

D1 D2 D3 D4
1 2 3
5.5 6.6 7.7
[Employee Name = Emply1 ] [Employee Name = Emply2 ] [Employee Name = Emply3 ]

Shell Sort Comparable Array Items in Java

Shell sort is considered as an extension of insertion sort algorithm.

Insertion sort algorithm is not suggested for large input sets but shell sort comes with increased speed achievements for insertion sort algorithm.

Shell sort achieves speed improvement by exchanging of input entries that are away from each other and produces partially sorted input data sets.

Space and time complexity values are :

Worst case performance : О(n²)
Best case performance : О(n log² n)
Average case performance : depends on gap sequence

Space complexiy :  О(n) total, O(1) auxiliary

There is an animation for the shell sort algorithm at :

Following is the Java implementation of the Shell Sort algorithm where the sort method accepts an array of Comparable items as input parameter.

package basics;

public class ShellSort {

 public static void sort(Comparable[] a) {

  // Sort a[] into increasing order.
  int N = a.length;
  int h = 1;
  while (h < N / 3)
   h = 3 * h + 1;
  
  // h-sort the array.
  while (h >= 1) { 
   for (int i = h; i < N; i++) { 
    for (int j = i; j >= h && (a[j].compareTo(a[j - h]) < 0); j -= h) {
     Comparable temp = a[j];
     a[j] = a[j - h];
     a[j - h] = temp;
    }
   }
   h = h / 3;
  }

 }

 public static void main(String[] args) {

  String[] strArr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };

  System.out.println("Before Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println("\n");

  sort(strArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println();

  Integer[] intArr = { 9, 8, 7, 6, 6, 5, 4, 3, 2, 2, 1 };

  System.out.println();
  System.out.println("Before Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println("\n");

  sort(intArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println();
 }
}

Create a ShellSort.java file in your workspace.

When the main method inside the ShellSort class executed it is going to print :

Before Sort =
S O R T E X A M P L E

After Sort =
A E E L M O P R S T X

Before Sort =
9 8 7 6 6 5 4 3 2 2 1

After Sort =
1 2 2 3 4 5 6 6 7 8 9


Because sort method accepts an array or Comparable items, so it is safe to send an array of items where each item implements Comparable interface in Java.

Integer and String classes in Java implement Comparable interface so it is acceptable to send this types as parameters to sort method.

Insertion Sort Comparable Array Items in Java

Insertion sort is one of the most common sorting algorithms.

Insertion sort algorithm achieves expected output by applying following steps :

1-) Start from the beginning index
2-) Compare next element with the previous item
3-) If current element is smaller than the previous element than swap elements
4-) Repeat step 3 until a sorted array is achieved

Space and time complexity values are :

Worst case performance О(n²)
Best case performance О(n)
Average case performance О(n²)

There is an animation for the insertion sort algorithm at :

Following is the Java implementation of the Insertion Sort algorithm where the sort method accepts an array of Comparable  items as input parameter.

package basics;

public class InsertionSort {

 public static void sort(Comparable[] a) {

  // Sort a[] into increasing order.
  int N = a.length;
  
  // Insert a[i] among a[i-1], a[i-2], a[i-3]....
  for (int i = 1; i < N; i++) { 
   for ( int j = i; j > 0 && ( (a[j].compareTo( a[j-1]))< 0 ); j--)
   {
       Comparable temp = a[j];
       a[j] = a[j - 1];
       a[j - 1] = temp;    
   }    
  }

 }

 public static void main(String[] args) {

  String[] strArr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };

  System.out.println("Before Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println("\n");

  sort(strArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println();

  Integer[] intArr = { 9, 8, 7, 6, 6, 5, 4, 3, 2, 2, 1 };

  System.out.println();
  System.out.println("Before Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println("\n");

  sort(intArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println();
 }
}

Create an InsertionSort.java file in your workspace.

When the main method inside the InsertionSort class executed it is going to print :

Before Sort =
S O R T E X A M P L E

After Sort =
A E E L M O P R S T X

Before Sort =
9 8 7 6 6 5 4 3 2 2 1

After Sort =
1 2 2 3 4 5 6 6 7 8 9


Because sort method accepts an array or Comparable items, so it is safe to send an array of items where each item implements Comparable interface in Java.

Integer and String classes in Java implement Comparable interface so it is acceptable to send this types as parameters to sort method.

Selection Sort Comparable Array Items in Java

Selection sort is one of the in-place sorting algorithms.

It is considered simple to implement but not efficient for large inputs.

General steps :

1-) Start from the beginning index
2-) Find the minimum
3-) Swap the found minimum with the item at the starting position of the set
4-) Do it until the last item is reached


Space and time complexity values are :

Worst case performance О(n²)
Best case performance О(n²)
Average case performance О(n²)

Worst case space complexity O(n) total, O(1) auxiliary

Following is the Java implementation of the Selection Sort algorithm where the sort method accepts an array of Comparable items as input parameter.

package basics;

public class SelectionSort {

   public static void sort(Comparable[] a) { 
  
    int N = a.length;
  
    for (int i = 0; i < N; i++) { 

        int minIndex = i;
        for (int j = i + 1; j < N; j++)
        if ( a[j].compareTo(a[minIndex])<0 )
             minIndex = j;

        if (minIndex != i) {
            Comparable temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
  
  }

  public static void main(String[] args) {
  
    String[] strArr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };
  
    System.out.println("Before Sort = " );
    for (int i = 0; i < strArr.length; i++)
     System.out.print(strArr[i] + " ");
    System.out.println("\n");
  
    sort(strArr);
  
    System.out.println("After Sort = " );
    for (int i = 0; i < strArr.length; i++)
     System.out.print(strArr[i] + " ");
    System.out.println();
  
    Integer[] intArr = { 9,8,7,6,6,5,4,3,2,2,1 };
  
    System.out.println();
    System.out.println("Before Sort = " );
    for (int i = 0; i < intArr.length; i++)
     System.out.print(intArr[i] + " ");
    System.out.println("\n");
  
    sort(intArr);
  
    System.out.println("After Sort = " );
    for (int i = 0; i < intArr.length; i++)
     System.out.print(intArr[i] + " ");
    System.out.println();
  }
}

Create a SelectionSort.java file in your workspace.

When the main method inside the SelectionSort class executed it is going to print :

Before Sort =
S O R T E X A M P L E

After Sort =
A E E L M O P R S T X

Before Sort =
9 8 7 6 6 5 4 3 2 2 1

After Sort =
1 2 2 3 4 5 6 6 7 8 9


Because sort method accepts an array or Comparable items, it is safe to send an array of items where each item implements Comparable interface in Java.

Custom Reverse Primitive Integer Array in Java

In order to reverse an integer primitive array in java an in-place algorithm can be used.

General algorithm for reversing an integer array is :

1-) Traverse the array until the midpoint found in a loop construct
2-) Implement a swap algorithm to exchange values of the items in the array

Following is a utility method used to reverse an existing array in java.

package basics;

public class ArrayUtility {
 
 static int[] reverse( int[] input )
 {
     if( input==null || input.length==0 )
         return null;
        
     int N = input.length;
  
     for( int i=0; i<N/2; i++ )
     {
        int temp = input[i];
        input[i] = input[N-i-1];
        input[N-i-1] = temp;
     }
  
     return input;
 } 

 public static void main(String[] args) {
  
  int[] original = {22,55,66,11,32,56,67,89,95,10};
  
  System.out.print("Original Array = ");
  for( int i = 0; i<original.length; i++ )
   System.out.print( original[i]+" " );
  
  int[] reverseArray = reverse( original );
 
  System.out.print("\nReversed Array = ");
  for (int i = 0; i <reverseArray.length; i++)
   System.out.print(reverseArray[i]+" ");  
 }
 
}

Create a ArrayUtility.java file in your workspace.

When the main method inside the ArrayUtility class executed it is going to print :

Original Array = 22 55 66 11 32 56 67 89 95 10
Reversed Array = 10 95 89 67 56 32 11 66 55 22

Custom Deep Copy Primitive Integer Array in Java

There are different methods to create copies of an array. Deep copy is considered as an expensive method when compared to shallow copying.

Following is a utility method used to copy an existing array into a new freshly created array in java.

package basics;

import java.util.Arrays;

public class ArrayUtility {
 
 static int[] copy( int[] input )
 {
     if ( input==null || input.length==0 )
         return null;
        
     int N = input.length;
     int[] copy = new int[N];
     for( int i = 0; i<N ; i++ )
         copy[i] = input[i];
  
     return copy;
 } 

 public static void main(String[] args) {
  
  int[] original = {22,55,66,11,32,56,67,89,95,10};
  
  int[] copyArray = copy( original );
  
  boolean result = Arrays.equals( original, copyArray );
  
  System.out.println( "Arrays are equal = "+result ); 

  System.out.print("\nOriginal Array = ");
  for( int i = 0; i< original.length; i++ )
       System.out.print( original[i]+" " );
  

  System.out.print("\nCopy Array = ");
  for (int i = 0; i < copyArray.length; i++)
    System.out.print(copyArray[i]+" ");
  
 }
}

Create a ArrayUtility.java file in your workspace.

When the main method inside the ArrayUtility class executed it is going to print :

Arrays are equal = true

Original Array = 22 55 66 11 32 56 67 89 95 10
Copy Array = 22 55 66 11 32 56 67 89 95 10

Recursive Binary Search Algorithm in Java

Binary Search is one of the most effective search algorithms used for searching a list of sorted items.

Known complexities for average, best and worst cases are considered as follows :

Worst case performance       =  O(log n)
Best case performance         =  O(1)
Average case performance   =  O(log n)

Following is the recursive implementation of binary search algorithm in Java.

package basics;

import java.util.Arrays;

public class RecursiveBinarySearch {

 public static int index( int[] input, int key )
 {
     return index( input, key, 0, input.length-1 );
 }
 
 public static int index( int[] input, int key, int low, int high )
 {
     if( low>high )
         return -1;
  
     int mid = low+(high-low)/2;
  
     if( key>input[mid] )
         return index(input, key, mid+1, high);
     else if( key<input[mid] )
         return index( input, key, low, mid-1 );
     else
         return mid;
 }
 
 public static void main(String[] args) {
  
  int[] list = {22,55,66,11,32,56,67,89,95,10};
  
  Arrays.sort(list);
  
  System.out.print("Sorted Array = ");
  for (int i = 0; i < list.length; i++) {
   System.out.print(list[i]+" ");
  }
  
  int itemIndex = index(list, 22);
  System.out.println("\n\nItem = "+22+", Index = "+itemIndex);
  
  itemIndex = index(list, 11);
  System.out.println("Item = "+11+", Index = "+itemIndex);
  
  itemIndex = index(list, 67);
  System.out.println("Item = "+67+", Index = "+itemIndex);
  
  itemIndex = index(list, 10);
  System.out.println("Item = "+10+", Index = "+itemIndex);

  itemIndex = index(list, 101);
  System.out.println("Item = "+101+", Index = "+itemIndex);
  
 }
}

Create a RecursiveBinarySearch.java file in your workspace.

When the main method inside the RecursiveBinarySearch class executed it is going to print :

Sorted Array = 10 11 22 32 55 56 66 67 89 95

Item = 22, Index = 2
Item = 11, Index = 1
Item = 67, Index = 7
Item = 10, Index = 0
Item = 101, Index = -1

Iterative Binary Search Algorithm in Java

Binary Search is one of the most effective search algorithms used for searching a list of sorted items.

Known complexities for average, best and worst cases are considered as follows :

Worst case performance       =  O(log n)
Best case performance          =  O(1)
Average case performance   =  O(log n)

Following is the iterative implementation of binary search algorithm in Java.

package basics;

import java.util.Arrays;

public class IterativeBinarySearch {
 
 public static int index( int[] input, int key )
 {
    int low = 0;
    int high = input.length-1;  
    while( low<=high )
    {
       int mid = low+(high-low)/2;
       if( key<input[mid] )
          high = mid-1;
       else if( key>input[mid] )
          low = mid+1;
       else
          return mid;
    }
    return -1;
 }
 
 public static void main(String[] args) {
  
  int[] list = {22,55,66,11,32,56,67,89,95,10};
  
  Arrays.sort(list);
  
  int itemIndex = index(list, 22);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 11);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 67);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 10);
  System.out.println(itemIndex);

  itemIndex = index(list, 101);
  System.out.println(itemIndex);
 }
 
}

Create a IterativeBinarySearch.java file in your workspace.

When the main method inside the IterativeBinarySearch class executed it is going to print :

2
1
7
0
-1

Generic NonRecursive BottomUp Merge Sort in Java

MergeSort can also be implemented with a non-recursive bottom-up approach.

Non-recursive bottom-up merge-sort runs in O(nlogn) time as recursive version does.

It is considered a bit faster than recursive merge-sort in practice because it does not make recursive-calls.

There is a detailed description about this implementation at here.

package interviewquestions;

import java.util.Comparator;

public class MergeSortRoutine {

 public static <K> void merge(K[] in, K[] out, Comparator<K> comp, int start, int inc) {

  int end1 = Math.min(start + inc, in.length);
  int end2 = Math.min(start + 2 * inc, in.length);
  int x = start;
  int y = start + inc;
  int z = start;
  
  while (x < end1 && y < end2)
   if (comp.compare(in[x], in[y]) < 0)
    out[z++] = in[x++];
   else
    out[z++] = in[y++];
  
  if (x < end1)
   System.arraycopy(in, x, out, z, end1 - x);
  else if (y < end2)
   System.arraycopy(in, y, out, z, end2 - y);
 }

 public static <K> void mergeSortBottomUp(K[] orig, Comparator<K> comp) {
  
  int n = orig.length;
  K[] src = orig;
  K[] dest = (K[]) new Object[n];
  K[] temp;
  for (int i = 1; i < n; i *= 2) { 
   
   for (int j = 0; j < n; j += 2 * i)
    merge(src, dest, comp, j, i);
   
   temp = src;
   src = dest;
   dest = temp;
  }
  if (orig != src)
   System.arraycopy(src, 0, orig, 0, n);
 }

 private static class IntComparator<T extends Comparable<T>> implements Comparator<T> {
  public int compare(T a, T b) {
   return a.compareTo(b);
  }
 }

 public static void main(String[] args) {

  Integer[] inputArr = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };

  System.out.println("Before sorting integer array with generic mergesort ");
  for (int i = 0; i < inputArr.length; i++) {
   System.out.print(inputArr[i] + " ");
  }

  mergeSortBottomUp(inputArr, new IntComparator<Integer>());

  System.out.println("\nAfter sorting integer array with generic mergesort ");
  for (int i = 0; i < inputArr.length; i++) {
   System.out.print(inputArr[i] + " ");
  }

  String[] values = { "asd", "basd", "cwe", "awe", "vasd" };

  System.out.println("\n\nBefore sorting String array with generic mergesort ");
  for (int i = 0; i < values.length; i++) {
   System.out.print(values[i] + " ");
  }

  mergeSortBottomUp(values, new IntComparator<String>());

  System.out.println("\nAfter sorting String array with generic mergesort ");
  for (int i = 0; i < values.length; i++) {
   System.out.print(values[i] + " ");
  }
  
 }
}

Above Non-recursive bottom-up Mergesort works for types that implements Comparable interface. Generic Comparator class instace is passed as a parameter to the generic mergeSortBottomUp method.

Create a MergeSortRoutine.java file in your workspace.

When the main method inside the MergeSortRoutine class executed it is going to print :

Before sorting integer array with generic mergesort
45 23 11 89 77 98 4 28 65 43
After sorting integer array with generic mergesort
4 11 23 28 43 45 65 77 89 98

Before sorting String array with generic mergesort
asd basd cwe awe vasd
After sorting String array with generic mergesort
asd awe basd cwe vasd

Generic Recursive Merge Sort in Java

Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. 

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Merge sort animation. The sorted elements are represented by dots.

package interviewquestions;

import java.util.Arrays;
import java.util.Comparator;

public class MergeSortRoutine {

   public static <K> void merge(K[] S1, K[] S2, K[] S, Comparator<K> comp) {

     int i = 0, j = 0;
     while (i + j < S.length) {
         if (j == S2.length || (i < S1.length && comp.compare(S1[i], S2[j]) < 0))
            S[i + j] = S1[i++]; 
         else
            S[i + j] = S2[j++]; 
     }

   }

   public static <K> void mergeSort(K[] S, Comparator<K> comp) {

     int n = S.length;
     if (n < 2)
        return; 

     int mid = n / 2;
     K[] S1 = Arrays.copyOfRange(S, 0, mid); 
     K[] S2 = Arrays.copyOfRange(S, mid, n);

     mergeSort(S1, comp); 
     mergeSort(S2, comp);

     merge(S1, S2, S, comp);
   }

   private static class IntComparator<T extends Comparable<T>> implements Comparator<T> {
     public int compare(T a, T b) {
      return a.compareTo(b);
     } 
   }

   public static void main(String[] args) {

     Integer[] inputArr = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };  
  
     System.out.println("Before sorting integer array with generic mergesort ");
     for (int i = 0; i < inputArr.length; i++) {
       System.out.print(inputArr[i]+" ");
     }
    
     mergeSort( inputArr, new IntComparator<Integer>() );
  
     System.out.println("\nAfter sorting integer array with generic mergesort ");
     for (int i = 0; i < inputArr.length; i++) {
       System.out.print(inputArr[i]+" ");
     }
  
     String[] values = { "asd","basd","cwe", "awe", "vasd" };
  
     System.out.println("\n\nBefore sorting String array with generic mergesort ");
     for (int i = 0; i < values.length; i++) {
       System.out.print(values[i]+" ");
     }
  
     mergeSort(values, new IntComparator<String>());
  
     System.out.println("\nAfter sorting String array with generic mergesort ");
     for (int i = 0; i < values.length; i++) {
       System.out.print(values[i]+" ");
     }
   }
}

Above Mergesort works for types that implements Comparable interface. Generic Comparator class instace is passed as a parameter to the generic mergeSort method.

Create a MergeSortRoutine.java file in your workspace.

When the main method inside the MergeSortRoutine class executed it is going to print :

Before sorting integer array with generic mergesort
45 23 11 89 77 98 4 28 65 43
After sorting integer array with generic mergesort
4 11 23 28 43 45 65 77 89 98

Before sorting String array with generic mergesort
asd basd cwe awe vasd
After sorting String array with generic mergesort
asd awe basd cwe vasd

Generic Recursive Find Depth of Binary Tree in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Depth of a binary tree is defined as the maximum length of all paths.

If a binary tree has only one node, its depth is 1. Following sample binary tree can be used as a test input.

There is a detailed and helpful description also at this link. 

package interviewquestions;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public int depth() {
       return depth(root);
   }

   private int depth(Node<T> pNode) {
  
     if (pNode == null)
         return 0;

     int left = depth(pNode.getLeftChild());
     int right = depth(pNode.getRightChild());
       
     int result = (left>right) ? (left+1) : (right+1);
     return result;
   }
  
}

public class BinaryTreeOperations {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    System.out.println("Depth of Binary Tree = "+binaryTree.depth()); 
 }

}

Create a BinaryTreeOperations.java file in your workspace.

When the main method inside the BinaryTreeOperations class executed it is going to print :

Depth of Binary Tree = 3

Generic Iterative Depth-First Binary Tree Traversal with Stack in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root(selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

DFS requires the use of a data structure called Stack, which is a Last In First Out (LIFO) structure.

                                       Depth-First Traversal Sequence: 1 - 2 - 4 - 5 - 3 - 6

package interviewquestions;

import java.util.Stack;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void depthFirst()
   {
     depthFirst( root );   
   }
 
   private void depthFirst( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     Stack<Node<T>> stack = new Stack<Node<T>>();
     stack.add(pNode);

     while (!stack.isEmpty()) {
         Node<T> node = stack.pop();

         if (node.getRightChild() != null)
             stack.add(node.getRightChild());
         if (node.getLeftChild() != null)
             stack.add(node.getLeftChild());
         System.out.print(node.getData());
     }

   }
  
}

public class DepthFirstTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.depthFirst();  
 }

}

Create a DepthFirstTraversal.java file in your workspace.

When the main method inside the DepthFirstTraversal class executed it is going to print :

1
2
4
5
3
6

Generic Iterative Breadth-First Binary Tree Traversal with Queue in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors. 

Breadth-first traversal is also known as level-order traversal. BFS requires the use of a data structure called Queue, which is a First In First Out (FIFO) structure.

                                         Breadth-First Traversal Sequence: 1 - 2 - 3 - 4 - 5 - 6

package interviewquestions;

import java.util.LinkedList;
import java.util.Queue;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void breadthFirst()
   {
     breadthFirst( root );   
   }
 
   private void breadthFirst( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     Queue<Node<T>> queue = new LinkedList<Node<T>>();
     queue.add((Node<T>) pNode);
  
     while (!queue.isEmpty()) {
          Node<T> node = (Node<T>) queue.remove();
          System.out.print(" " + node.getData());
   
          if (node.getLeftChild()!= null)
              queue.add(node.getLeftChild());
          if ( node.getRightChild() != null)
              queue.add(node.getRightChild());
     }      

   }
  
}

public class BreadthFirstTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.breadthFirst();  
 }

}

Create a BreadthFirstTraversal.java file in your workspace.

When the main method inside the BreadthFirstTraversal class executed it is going to print :

1
2
3
4
5
6