Count the Number of 1’s in each row

Count the Number of 1’s in each row:

Given a boolean matrix with every row sorted, find the row with maximum number of 1s.

http://www.geeksforgeeks.org/amazon-interview-experience-set-225-for-1-year-experienced/

package core.geeks;

import java.io.PrintStream;

public class MaxNum1SortedMatrix {

       static PrintStream out = java.lang.System.out;

       public static void main(String[] args) {

              int[][] sortedMatrix = {{0,0,0,1,1,1},

                                                       {0,0,1,1,1,1},

                                                       {0,0,0,0,1,1},

                                                       {1,1,1,1,1,1},

                                                       {0,0,1,1,1,1}};

              int row = sortedMatrix.length-1;

              int column = sortedMatrix[0].length-1;

              int[] resultArr = new int[row+1];

             

              for (int i = 0; i <=row; i++) {

                     int[] temp = sortedMatrix[i];

                     resultArr[i] = column - binarySerachIdx(temp)+1;

              }

             

              for (int i = 0; i < resultArr.length; i++) {

                     System.out.println(resultArr[i]);

              }

       }

       private static int binarySerachIdx(int[] temp) {

              int start = 0; int mid = temp.length/2;

              while(start<mid) {

                     if(temp[mid]==1 && mid>0 && temp[mid-1]==1) {

                           mid = mid-1;

                          

                     } else if(temp[mid]==0 && mid<temp.length) {

                           start = mid;

                           mid = temp.length-1;

                     } else {

                           return mid;

                     }

              }

              return 0;

       }

}

Output:

3

4

2

6

4

Next Greater Element

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Input : {0,1,2,6,8,87,12,43,23,54,66}

0 --> 87

1 --> 87

2 --> 87

6 --> 87

8 --> 87

87 --> -1

12 --> 66

43 --> 66

23 --> 66

54 --> 66

66 --> -1

package core.geeks;

import java.io.IOException;

public class NextGreatestElementUnsortedArr {

       public static void main(String[] args) throws IOException {

             

              int[] arr = new int[]{0,1,2,6,8,87,12,43,23,54,66};

             

              int[] maxDynaArr = new int[arr.length];

             

              maxDynaArr[arr.length-1] = -1;

             

              if(arr[arr.length-1]>arr[arr.length-2]) {

                     maxDynaArr[arr.length-2] = arr[arr.length-1];

              } else {

                     maxDynaArr[arr.length-2] = -1;

              }

             

              int preTemp = Math.max(Integer.MIN_VALUE, maxDynaArr[arr.length-2]);

             

              for(int i=arr.length-3;i>=0;i--) {

                    

                     int temp = Math.max(arr[i+1],maxDynaArr[i+2]);

                    

                     preTemp = Math.max(preTemp,temp);

                     if(preTemp>arr[i]) {

                           maxDynaArr[i] = preTemp;

                     } else {

                           maxDynaArr[i] = -1;

                     }

                    

              }

             

              for (int i = 0; i < maxDynaArr.length; i++) {

                     System.out.println(arr[i] + " --> "+maxDynaArr[i]);

              }

       }

}

Spiral Matrix in Java

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

package core.geeks;

public class SpriralMatrix {

       public static void main(String[] args) {

              int[][] array = {  {0, 1, 2, 3, 4},

                           {5, 6, 7, 8, 9},

                           {10, 11, 12, 13, 14},

                           {15, 16, 17, 18, 19}};

              printSpiral(array);

       }

       private static void printSpiral(int[][] array) {

              int left=0; int right = array[0].length-1;

              int top = 0; int bottom = array.length-1;

              int count = 0;

              while(right>=left && top <= bottom) {

                    

                     if(count==0) {

                           // print top row

                           for(int i = left;i<=right;i++) {

                                  System.out.print(" "+array[top][i]);

                           }

                           top++;

                     } else if(count==1) {

                          

                           // print right most column

                           for(int i = top;i<=bottom;i++) {

                                  System.out.print(" "+array[i][right]);

                           }

                           right--;

                          

                     } else if(count==2) {

                           // print bottom row in reverse order.

                           for(int i = right;i>=left;i--) {

                                  System.out.print(" "+array[bottom][i]);

                           }

                           bottom--;

                     } else if(count==3) {

                           // print right most column

                           for(int i = bottom;i>=top;i--) {

                                  System.out.print(" "+array[i][left]);

                           }

                           left ++;

                     }

                     count = (count+1)%4;

              }

       }

}

Output:

0 1 2 3 4 9 14 19 18 17 16 15 10 5 6 7 8 13 12 11