fork(2) download
copy 
  1.     import java.util.*;
  2.  
  3.     class Ideone{
  4.     	public static void main (String[] args) throws java.lang.Exception{
  5.     		new Ideone().run();
  6.     	}
  7.     	int N , M ;
  8.  
  9.     	void run(){
  10.     		N = 1000;
  11.     		M = 100;
  12.  
  13.     		// arr is a random NxM array
  14.     		int[][] arr = randomArray();
  15.     		long start = System.currentTimeMillis();
  16.     //		for(int i=0; i<N; i++){   // TO print the array. 
  17.     //			System. out.println(Arrays.toString(arr[i]));
  18.     //		}
  19.     		System.out.println(findPeakLinearTime(arr));
  20.     		long end = System.currentTimeMillis();
  21.     		System.out.println("time taken : " + (end-start));
  22.     	}
  23.  
  24.     	int findPeakLinearTime(int[][] arr){
  25.     		int rows = arr.length;
  26.     		int cols = arr[0].length;
  27.     		return kthLinearColumn(arr, 0, cols-1, 0, rows-1);
  28.     	}
  29.  
  30.     	// helper function that splits on the middle Column
  31.     	int kthLinearColumn(int[][] arr, int loCol, int hiCol, int loRow, int hiRow){
  32.     		if(loCol==hiCol){
  33.     			int max = arr[loRow][loCol];
  34.     			int foundRow = loRow;
  35.     			for(int row = loRow; row<=hiRow; row++){
  36.     				if(max < arr[row][loCol]){
  37.     					max = arr[row][loCol];
  38.     					foundRow = row;
  39.     				}
  40.     			}
  41.     			if(!correctPeak(arr, foundRow, loCol)){
  42.     				System.out.println("THIS PEAK IS WRONG");
  43.     			}
  44.     			return max;
  45.     		}
  46.     		int midCol = (loCol+hiCol)/2;
  47.     		int max = arr[loRow][loCol];
  48.     		for(int row=loRow; row<=hiRow; row++){
  49.     			max = Math.max(max, arr[row][midCol]);
  50.     		}
  51.     		boolean centralMax = true;
  52.     		boolean rightMax = false;
  53.     		boolean leftMax  = false;
  54.  
  55.     		if(midCol-1 >= 0){
  56.     			for(int row = loRow; row<=hiRow; row++){
  57.     				if(arr[row][midCol-1] > max){
  58.     					max = arr[row][midCol-1];
  59.     					centralMax = false;
  60.     					leftMax = true;
  61.     				}
  62.     			}
  63.     		}
  64.  
  65.     		if(midCol+1 < M){
  66.     			for(int row=loRow; row<=hiRow; row++){
  67.     				if(arr[row][midCol+1] > max){
  68.     					max = arr[row][midCol+1];
  69.     					centralMax = false;
  70.     					leftMax = false;
  71.     					rightMax = true;
  72.     				}
  73.     			}
  74.     		}
  75.  
  76.     		if(centralMax) return max;
  77.     		if(rightMax)  return kthLinearRow(arr, midCol+1, hiCol, loRow, hiRow);
  78.     		if(leftMax)   return kthLinearRow(arr, loCol, midCol-1, loRow, hiRow);
  79.     		throw new RuntimeException("INCORRECT CODE");
  80.     	}
  81.  
  82.     	// helper function that splits on the middle 
  83.     	int kthLinearRow(int[][] arr, int loCol, int hiCol, int loRow, int hiRow){
  84.     		if(loRow==hiRow){
  85.     			int ans = arr[loCol][loRow];
  86.     			int foundCol = loCol;
  87.     			for(int col=loCol; col<=hiCol; col++){
  88.     				if(arr[loRow][col] > ans){
  89.     					ans = arr[loRow][col];
  90.     					foundCol = col;
  91.     				}
  92.     			}
  93.     			if(!correctPeak(arr, loRow, foundCol)){
  94.     				System.out.println("THIS PEAK IS WRONG");
  95.     			}
  96.     			return ans;
  97.     		}
  98.     		boolean centralMax = true;
  99.     		boolean upperMax = false;
  100.     		boolean lowerMax = false;
  101.  
  102.     		int midRow = (loRow+hiRow)/2;
  103.     		int max = arr[midRow][loCol];
  104.  
  105.     		for(int col=loCol; col<=hiCol; col++){
  106.     			max = Math.max(max, arr[midRow][col]);
  107.     		}
  108.  
  109.     		if(midRow-1>=0){
  110.     			for(int col=loCol; col<=hiCol; col++){
  111.     				if(arr[midRow-1][col] > max){
  112.     					max = arr[midRow-1][col];
  113.     					upperMax = true;
  114.     					centralMax = false;
  115.     				}
  116.     			}
  117.     		}
  118.  
  119.     		if(midRow+1<N){
  120.     			for(int col=loCol; col<=hiCol; col++){
  121.     				if(arr[midRow+1][col] > max){
  122.     					max = arr[midRow+1][col];
  123.     					lowerMax = true;
  124.     					centralMax = false;
  125.     					upperMax   = false;
  126.     				}
  127.     			}
  128.     		}
  129.  
  130.     		if(centralMax) return max;
  131.     		if(lowerMax)   return kthLinearColumn(arr, loCol, hiCol, midRow+1, hiRow);
  132.     		if(upperMax)   return kthLinearColumn(arr, loCol, hiCol, loRow, midRow-1);
  133.     		throw new RuntimeException("Incorrect code");
  134.     	}
  135.  
  136.     	int[][] randomArray(){
  137.     		int[][] arr = new int[N][M];
  138.     		for(int i=0; i<N; i++)
  139.     			for(int j=0; j<M; j++)
  140.     				arr[i][j] = (int)(Math.random()*1000000000);
  141.     		return arr;
  142.     	}
  143.  
  144.     	boolean correctPeak(int[][] arr, int row, int col){//Function that checks if arr[row][col] is a peak or not
  145.     		if(row-1>=0 && arr[row-1][col]>arr[row][col])  return false;
  146.     		if(row+1<N && arr[row+1][col]>arr[row][col])   return false;
  147.     		if(col-1>=0 && arr[row][col-1]>arr[row][col])  return false;
  148.     		if(col+1<M && arr[row][col+1]>arr[row][col])   return false;
  149.     		return true;
  150.     	}
  151.     }
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
996374919
time taken : 1
https://ideone.com/K3ggGm
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!