2D Peak Finding

Peak Finding: 1D and 2D
http://courses.csail.mit.edu/6.006/fall11/notes.shtml
http://courses.csail.mit.edu/6.006/fall10/notes.shtml

T(n) = T(n/2) + O(1)
Divide and Conquer
• Very powerful design tool:
– Divide input into multiple disjoint parts
– Conquer each of the parts separately 
(using recursive call)
• Occasionally, we need to combine results 
from different calls
1D
Consider the middle element of the array 
and compare with neighbors
– If A[n/2-1]>A[n/2]
then search for a peak among A[1]… A[n/2-1]
– Else, if A[n/2]<A[n/2+1]
then search for a peak among A[n/2]… A[n]
– Else A[n/2] is a peak! 
(since A[n/2-1]≤A[n/2] and A[n/2] ≥A[n/2+1] )

2D
Algorithm I:
– For each column j, find its global maximum B[j]
– Apply 1D peak finder to find a peak (say B[j]) 
of B[1...m]
O(n*m)

Algorithm II => O(nlogm)• Pick middle column ( j=m/2 )
• Find global maximum a=A[i,m/2] in that column
(and quit if m=1)
• Compare a to b=A[i,m/2-1] and c=A[i,m/2+1]
• If b>a 
then recurse on left columns
• Else, if c>a
then recurse on right columns
• Else a is a 2D peak!
Proof (by contradiction):

T(n,m)= T(n,m/2) + O(n) = O(nlogm)
T(n,n)= (n) + (n) +...+ (n) = (nlog m)
http://stackoverflow.com/questions/10531720/2d-peak-finding-algorithm-java-found-one-example-but-cant-code-it
https://github.com/fekberg/Algorithms/blob/master/Peak%20Finding/Peak%20Finding/Program.cs

    static void Peak(int[,] map, int left, int right)
    {
        // calculate middle column
        int column = (right + left) / 2;


        // get max row in column
        int arow = 0;
        for (int row = 0; row < map.GetLength(0); row++)
            if (map[row, column] > map[arow, column])
                arow = row;

        int a = map[arow, column];

        // get left value
        int b = 0;
        if (column - 1 >= left) b = map[arow, column - 1];
        // get right value
        int c = 0;
        if (column + 1 <= right) c = map[arow, column + 1];

        // if left is higher, recurse left
        if (b > a) Peak(map, left, column - 1);
        // else if right is higher, recurse right
        else if (c > a) Peak(map, column + 1, right);
        // else, peak
        else Console.WriteLine("Peak: " + arow + " " + column + " " + a);
    }

linear-time O(n + m)Reading only O(n + m) elements, reduce an array of n*m candidates to an array of n/2*m/2 candidates
http://stackoverflow.com/questions/23120300/2d-peak-finding-algorithm-in-on-worst-case-time
http://ideone.com/K3ggGm

1. int findPeakLinearTime(int[][] arr){
2. int rows = arr.length;
3. int cols = arr[0].length;
4. return kthLinearColumn(arr, 0, cols-1, 0, rows-1);
5. }
6.  
7. // helper function that splits on the middle Column
8. int kthLinearColumn(int[][] arr, int loCol, int hiCol, int loRow, int hiRow){
9. if(loCol==hiCol){
10. int max = arr[loRow][loCol];
11. int foundRow = loRow;
12. for(int row = loRow; row<=hiRow; row++){
13. if(max < arr[row][loCol]){
14. max = arr[row][loCol];
15. foundRow = row;
16. }
17. }
18. if(!correctPeak(arr, foundRow, loCol)){
19. System.out.println("THIS PEAK IS WRONG");
20. }
21. return max;
22. }
23. int midCol = (loCol+hiCol)/2;
24. int max = arr[loRow][loCol];
25. for(int row=loRow; row<=hiRow; row++){
26. max = Math.max(max, arr[row][midCol]);
27. }
28. boolean centralMax = true;
29. boolean rightMax = false;
30. boolean leftMax = false;
31.  
32. if(midCol-1 >= 0){
33. for(int row = loRow; row<=hiRow; row++){
34. if(arr[row][midCol-1] > max){
35. max = arr[row][midCol-1];
36. centralMax = false;
37. leftMax = true;
38. }
39. }
40. }
41.  
42. if(midCol+1 < M){
43. for(int row=loRow; row<=hiRow; row++){
44. if(arr[row][midCol+1] > max){
45. max = arr[row][midCol+1];
46. centralMax = false;
47. leftMax = false;
48. rightMax = true;
49. }
50. }
51. }
52.  
53. if(centralMax) return max;
54. if(rightMax) return kthLinearRow(arr, midCol+1, hiCol, loRow, hiRow);
55. if(leftMax) return kthLinearRow(arr, loCol, midCol-1, loRow, hiRow);
56. throw new RuntimeException("INCORRECT CODE");
57. }
58.  
59. // helper function that splits on the middle
60. int kthLinearRow(int[][] arr, int loCol, int hiCol, int loRow, int hiRow){
61. if(loRow==hiRow){
62. int ans = arr[loCol][loRow];
63. int foundCol = loCol;
64. for(int col=loCol; col<=hiCol; col++){
65. if(arr[loRow][col] > ans){
66. ans = arr[loRow][col];
67. foundCol = col;
68. }
69. }
70. if(!correctPeak(arr, loRow, foundCol)){
71. System.out.println("THIS PEAK IS WRONG");
72. }
73. return ans;
74. }
75. boolean centralMax = true;
76. boolean upperMax = false;
77. boolean lowerMax = false;
78.  
79. int midRow = (loRow+hiRow)/2;
80. int max = arr[midRow][loCol];
81.  
82. for(int col=loCol; col<=hiCol; col++){
83. max = Math.max(max, arr[midRow][col]);
84. }
85.  
86. if(midRow-1>=0){
87. for(int col=loCol; col<=hiCol; col++){
88. if(arr[midRow-1][col] > max){
89. max = arr[midRow-1][col];
90. upperMax = true;
91. centralMax = false;
92. }
93. }
94. }
95.  
96. if(midRow+1<N){
97. for(int col=loCol; col<=hiCol; col++){
98. if(arr[midRow+1][col] > max){
99. max = arr[midRow+1][col];
100. lowerMax = true;
101. centralMax = false;
102. upperMax = false;
103. }
104. }
105. }
106.  
107. if(centralMax) return max;
108. if(lowerMax) return kthLinearColumn(arr, loCol, hiCol, midRow+1, hiRow);
109. if(upperMax) return kthLinearColumn(arr, loCol, hiCol, loRow, midRow-1);
110. throw new RuntimeException("Incorrect code");
111. }
112.  
113. int[][] randomArray(){
114. int[][] arr = new int[N][M];
115. for(int i=0; i<N; i++)
116. for(int j=0; j<M; j++)
117. arr[i][j] = (int)(Math.random()*1000000000);
118. return arr;
119. }
120.  
121. boolean correctPeak(int[][] arr, int row, int col){//Function that checks if arr[row][col] is a peak or not
122. if(row-1>=0 && arr[row-1][col]>arr[row][col]) return false;
123. if(row+1<N && arr[row+1][col]>arr[row][col]) return false;
124. if(col-1>=0 && arr[row][col-1]>arr[row][col]) return false;
125. if(col+1<M && arr[row][col+1]>arr[row][col]) return false;
126. return true;
127. }
128. }

Code:
https://gist.github.com/tiraeth/1306602
http://www.geeksforgeeks.org/find-a-peak-in-a-given-array/
http://cresspahl.blogspot.com/2012/03/simple-algorithm-for-2d-peakfinding.html
http://stackoverflow.com/questions/9587173/algorithm-to-find-peaks-in-2d-array