162. Find Peak Element

Difficulty: Medium

Frequency: N/A

A peak element is an element that is greater than its neighbors.

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] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if (nums.empty()) return -1;
        if (nums.size() == 1) return 0;
        int n = nums.size();
        int lo = 0, hi = n - 1, med;
        while (lo < hi) {
            med = lo + (hi - lo) / 2;
            if (nums[med] < nums[med + 1]) lo = med + 1;
            else hi = med;
        }
        return lo;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

034. Search for a Range

Difficulty: Medium

Frequency: N/A

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> results(2, -1);
        if (nums.empty()) return results;
        double left_t = target - 0.5, right_t = target + 0.5;
        int lo = 0, hi = nums.size() - 1, med;
        while (lo < hi) {
            med = lo + (hi - lo) / 2;
            if (nums[med] < left_t) lo = med + 1;
            else hi = med;
        }
        if (nums[lo] != target) return results;
        results[0] = lo;
        hi = nums.size() - 1;
        while (lo < hi) {
            med = lo + (hi - lo + 1) / 2;
            if (nums[med] > right_t) hi = med - 1;
            else lo = med;
        }
        results[1] = lo;
        return results;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: