[LintCode] Find Peak Element II - Eason Liu - 博客园

[LintCode] Find Peak Element II - Eason Liu - 博客园
There is an integer matrix which has the following features:

1. The numbers in adjacent positions are different.
2. The matrix has n rows and m columns.
3. For all i < m, A[0][i] < A[1][i] && A[n - 2][i] > A[n - 1][i].
4. For all j < n, A[j][0] < A[j][1] && A[j][m - 2] > A[j][m - 1].

We define a position P is a peek if A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1].

Solve it in O(n+m) time.

If you come up with an algorithm that you thought it is O(n log m) or O(m log n), can you prove it is actually O(n+m) or propose a similar but O(n+m) algorithm?

[ [1 ,2 ,3 ,6 ,5], 
  [16,41,23,22,6], 
  [15,17,24,21,7], 
  [14,18,19,20,10], 
  [13,14,11,10,9] ]

return index of 41 (which is [1,1]) or index of 24 (which is [2,2])

http://www.tangjikai.com/algorithms/lintcode-390-find-peak-element-ii

Solution 1: Binary search for row
Steps:
1. Get the maximum point in the center row, A[mid][col].
2. 

• If A[mid][col] < A[mid + 1][col], cut off the top half(l = mid + 1)

                     A[mid][col] < A[mid + 1][col]: the bottom half mush contains a peak element

• If A[mid][col] < A[mid - 1][col], cut off the top half(r = mid - 1)

                     A[mid][col] < A[mid - 1][col]: the top half mush contains a peak element

• Else, return A[mid][col]

                     A[mid][col] > A[mid-1][col] and > A[mid+1][col] and it is the largest in row => peak element

1. def findPeakII(self, A):
2. # write your code here
3. if not A:
4. return []
6. l, r = 1, len(A) - 2
7. ans = []
9. while l <= r:
10. mid = l + (r - l) / 2
11. col = self.find(A[mid])
13. if A[mid][col] < A[mid - 1][col]:
14. r = mid - 1
15. elif A[mid][col] < A[mid + 1][col]:
16. l = mid + 1
17. else:
18. ans.append(mid)
19. ans.append(col)
20. return ans
22. return []
24. def find(self, a):
25. ans = 0
26. for i in range(len(a)):
27. if a[i] > a[ans]:
28. ans = i

7     vector<int> findPeakII(vector<vector<int> > A) {
 8         // write your code here
 9         vector<int> res;
10         int left = 0, right = A.size() - 1;
11         while (left <= right) {
12             int mid = left + ((right - left) >> 1);
13             int col = findPeak(A[mid]);
14             if (A[mid][col] < A[mid+1][col]) {
15                 left = mid + 1;
16             } else if (A[mid][col] < A[mid-1][col]) {
17                 right = mid - 1;
18             } else {
19                 return {mid, col};
20             }
21         }
22         return res;
23     }
24     int findPeak(vector<int> &v) {
25         int res = 0;
26         for (int i = 1; i < v.size(); ++i) {
27             if (v[i] > v[res]) res = i;
28         }
29         return res;
30     }

Solution 2: Binary search for window
Steps:
1. Get the largest value in center row and center column(window) excluding boundary (6 largest below)
2. Find larger neighbor (8 > 6), recurse in quadrant(NW part below)
Read more

http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

1. def findPeakII(self, A):
2. # write your code here
3. if not A:
4. return []
6. l, r = 1, len(A) - 2
7. ans = []
9. while l <= r:
10. mid = l + (r - l) / 2
11. col = self.find(A[mid])
13. if A[mid][col] < A[mid - 1][col]:
14. r = mid - 1
15. elif A[mid][col] < A[mid + 1][col]:
16. l = mid + 1
17. else:
18. ans.append(mid)
19. ans.append(col)
20. return ans
22. return []
24. def find(self, a):
25. ans = 0
26. for i in range(len(a)):
27. if a[i] > a[ans]:
28. ans = i
30. return ans

Let T(m,n) as time complexity of finding peak element in an m*n array.
T(m,n) = T(m/2,n/2)+c(m+n)
              = T(m/4,n/4)+c(m+n)+c(m/2+n/2)
              = ...
              = T(1,1) + c(m+n)(1+1/2+1/4+...+1/(m+n))
              = c(2(m+n)) 
              = O(m+n)

https://codesolutiony.wordpress.com/2015/05/21/lintcode-find-peak-element-ii/
O(m+n)

    public List<Integer> findPeakII(int[][] A) {

        List<Integer> res = new ArrayList<Integer>();

        if (A == null || A.length == 0 || A[0].length == 0) {

            return res;

        }

        int i = 1, j = 1;

        while (true) {

            if (isValid(A, i, j)) {

                res.add(i);

                res.add(j);

                return res;

            }

            if (A[i+1][j] > A[i][j+1]) {

                i++;

            } else {

                j++;

            }

        }

    }

    private boolean isValid(int[][] a, int i, int j) {

        if (i > 0 && i < a.length - 1 && j > 0 && j < a[0].length - 1

            && a[i-1][j] < a[i][j] && a[i+1][j] < a[i][j] && a[i][j+1] < a[i][j] && a[i][j+1] < a[i][j]) {

            return true;

        }

        return false;

    }

https://docs.google.com/viewer?url=http%3A%2F%2Fcourses.csail.mit.edu%2F6.006%2Fspring11%2Flectures%2Flec02.pdf

Read full article from [LintCode] Find Peak Element II - Eason Liu - 博客园