Print 2D matrix in spiral order

Given a 2D array, print it in spiral form.

Input:
        1    2   3   4
        5    6   7   8
        9   10  11  12
        13  14  15  16 

Output: 
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 

Below is the java implementation 

public class PrintMatrixInSpiral {

 private static int [][] matrix = { 
   {1,2,3,4},
   {5,6,7,8},
   {9,10,11,12},
   {13,14,15,16}};
 
 public static void main(String arg[])
 {
  printSpiral(matrix);
 }
 
 public static void printSpiral(int [][]matrix)
 {
  int top = 0;
  int bottom = matrix.length - 1;
  int left = 0;
  int right = matrix[0].length - 1;
  
  int loop = 0;
  
  while ( top < bottom && left < right )
  {
   /* print row horizontally */
   for( loop = top; loop <= right; loop++)
    System.out.println(matrix[top][loop]);
   
   top++;
   
   /* print last column in all rows */
   for( loop = top; loop <= bottom ; loop++ )
    System.out.println(matrix[loop][right]);
   
   right--;
   
   for( loop = right ; loop >= left; loop--)
    System.out.println(matrix[bottom][loop]);
   
   bottom--;
   
   for(loop = bottom; loop >= top; loop --)
    System.out.println(matrix[loop][left]);
   
   left++;
  }
 }
} 

Coin change problem

Find the minimum number of coins required to make change of N, given currencies of different values.

E.g.,

Input: Denominations {1,3,5,8,9},   Value: 28
Output: 4


This problem can be solved using dynamic programming approach. This is similar to Knapsack problem.

Below is Java implementation

public class CoinChange {

    public static void main(String args[])
    {
        int []denominations = {1,3,5,8,9};
        int value = 28;
        System.out.println("The minimum number of coins required to make change of "+value+" is:"+findMinimumCoinsRequired(denominations,value));
    }

    private static int findMinimumCoinsRequired(int[] denominations, int value) {
       
        int []dp = new int[value+1];       
        dp[0] = 0;

        for(int i = 1; i <= value; i++ )
        {
            dp[i] = Integer.MAX_VALUE;
            for( int j = 0; j < denominations.length; j++ )
            {
                if( denominations[j] <=  i  )
                {
                    dp[i] = Math.min(dp[i], dp[i - denominations[j]]+1);
                }
            }
        }
        return dp[value];
    }
}
 

Find minimum number of hops required to reach end of array.

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element).

E.g.
Input : {2,3,1,1,4}
Output: 2

We can solve this problem in multiple approaches. Here i am going to provide solution in greedy and dynamic programming model.

In greedy approach we find the maximum value to maximize the jump. In dynamic programming approach we compute the minimum number of hops required to reach each element and use these values for computing the result.

Below is the Java implementation of both approaches.

public class FindMinimumHops {
   
    public static void main(String args[])
    {
        int [] array = {2,3,1,1,4};
        System.out.println("Minimum number of hops to reach end is:"+findMinHopsUsingGreedy(array));       
        System.out.println("Minimum number of hops to reach end is:"+findMinHopsUsingDP(array));
    }

    private static int findMinHopsUsingGreedy(int[] array) {
        int maxHops = 0;
        int currentIndex = 0;
        int max = 0;
        int location = 0;
        while (currentIndex < array.length) {
            maxHops++;
            max = 0;
            for (int ctr = currentIndex + 1; ctr <= currentIndex
                    + array[currentIndex]; ctr++) {
                if (max < array[ctr]) {
                    max = array[ctr];
                    location = ctr;
                }
            }
            currentIndex += location;
        }
        return maxHops;
    }

    private static int findMinHopsUsingDP(int[] array) {
        int []dp = new int[array.length];
        dp[0] = 0;
        for(int i = 1; i < array.length; i++)
        {
            dp[i] = Integer.MAX_VALUE;
            for(int j= 0; j < i ; j++ )
                if( ( i-j ) <= array[j] )
                    dp[i] = Math.min(dp[i], dp[j]+1);
        }
       
        return dp[array.length - 1];
    }

}