Find Trough/Peak Element

Find Peak Element (LC.162)

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞.

Example

Input: [1, 2, 3, 1]
Return: A[2] = 3, return 2
Input: [1, 2, 1, 3, 4, 5, 7, 6]
Return: A[1] = 2 or A[6] = 7, return 1 or 6

Analysis

This is more fun to do. This is no longer a vanilla binary search. This is decrease and conquer. We need to exploit the sorted property and somehow pick half of the original problem to solve. We have 4 cases: 1. mid is peak, then A[mid-1] < A[mid] < A[mid+1] 2. if the seq is increasing, then search right 3. if the seq is decreasing, then search left 4. else mid is a trough, either left or right is fine

Code

public int findPeakElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    return peakHelper(nums, 0, nums.length - 1);
}

private int peakHelper(int[] nums, int start, int end) {
    // base case 2 elements (make sure no array out of bound exception)
    if (start + 1 >= end) {
        if (nums[start] > nums[end]) {
            return start;
        } else {
            return end;
        }
    }
    // decrease
    int mid = start + (end - start) / 2;
    // conquer
    if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
        // nums[mid] is a peak
        return mid;
    } else if (nums[mid - 1] < nums[mid] && nums[mid] < nums[mid + 1]) {
        // in an increasing seq, search right
        return peakHelper(nums, mid + 1, end);
    } else if (nums[mid - 1] > nums[mid] && nums[mid] > nums[mid + 1]) {
        // in a decreasing sq, search left
        return peakHelper(nums, start, mid - 1);
    } else {
        // a trough, either left or right
        return peakHelper(nums, start, mid - 1);
    }
}

The comparisons can be further simplified. But since we have a clear understanding and a working code, objectives accomplished.

Maximum Number in Mountain Sequence

Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.

Example

Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10

Analysis

Same thing as above. Let's try while loop this time.

Code

public int mountainSequence(int[] nums) {
    if (nums == null || nums.length == 0)
        return -1;
    int start = 0, mid, end = nums.length - 1;
    // guarantee more than 2 elements
    while (start + 1 < end) {
        mid = (start + end) / 2;
        if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
            // a peak
            return nums[mid];
        } else if (nums[mid - 1] < nums[mid] && nums[mid] < nums[mid + 1]) {
            // increasing seq, search right
            start = mid + 1;
        } else {
            // decreasing seq, or a trough, search left
            end = mid - 1;
        }
    }
    // base case
    if (nums[start] > nums[end]) {
        return nums[start];
    } else {
        return nums[end];
    }
}

Find Peak Element II

Find peak in a 2D array.

Reference

Find Peak Element by segmentfault