Category: geeksforgeeks

Peak element

https://www.geeksforgeeks.org/problems/peak-element
https://leetcode.com/problems/find-peak-element
Difficulty: Basic
Accuracy: 38.86%
Submissions: 510K+Points: 1

Given an array arr[] where no two adjacent elements are same, find the index of a peak element. An element is considered to be a peak if it is greater than its adjacent elements (if they exist). If there are multiple peak elements, return index of any one of them. The output will be “true” if the index returned by your function is correct; otherwise, it will be “false”.

Note: Consider the element before the first element and the element after the last element to be negative infinity.

Examples :

Input: arr = [1, 2, 4, 5, 7, 8, 3]
Output: true
Explanation: arr[5] = 8 is a peak element because arr[4] < arr[5] > arr[6].

Input: arr = [10, 20, 15, 2, 23, 90, 80]
Output: true
Explanation: arr[1] = 20 and arr[5] = 90 are peak elements because arr[0] < arr[1] > arr[2] and arr[4] < arr[5] > arr[6]. 

Input: arr = [1, 2, 3]
Output: true
Explanation: arr[2] is a peak element because arr[1] < arr[2] and arr[2] is the last element, so it has negative infinity to its right.

Constraints:
1 ≤ arr.size() ≤ 10⁶
-2³¹ ≤ arr[i] ≤ 2³¹ – 1

Solution in C++

Algorithm: Uses a binary search approach to find a peak element in O(log n) time complexity.

//
// Created by robert on 12/15/24.
//
#include <iostream>
#include <vector>
using namespace std;

int findPeakElement(const vector<int>& arr) {
    int n = arr.size();
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if the mid element is a peak
        if ((mid == 0 || arr[mid] > arr[mid - 1]) &&
            (mid == n - 1 || arr[mid] > arr[mid + 1])) {
            return mid; // Peak found
        }

        // If the left neighbor is greater, search on the left side
        if (mid > 0 && arr[mid - 1] > arr[mid]) {
            high = mid - 1;
        }
        // Otherwise, search on the right side
        else {
            low = mid + 1;
        }
    }

    return -1; // This should never be reached
}

int main() {
    vector<int> arr = {1, 2, 4, 5, 7, 8, 3};
    int peakIndex = findPeakElement(arr);
    cout << "Peak element index: " << peakIndex << endl;
    return 0;
}

Given an array of non-overlapping intervals intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>] represent the start and the end of the i<sup>th</sup> event and intervals is sorted in ascending order by start<sub>i</sub>. He wants to add a new interval newInterval= [newStart, newEnd] where newStart and newEnd represent the start and end of this interval.

Need to insert newInterval into intervals such that intervals is still sorted in ascending order by start<sub>i</sub> and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Examples:

Input: intervals = [[1,3], [4,5], [6,7], [8,10]], newInterval = [5,6]
Output: [[1,3], [4,7], [8,10]]
Explanation: The newInterval [5,6] overlaps with [4,5] and [6,7].

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,9]
Output: [[1,2], [3,10], [12,16]]
Explanation: The new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Constraints:
1 ≤ intervals.size() ≤  10⁵
0 ≤ start[i], end[i] ≤ 10⁹Try more examples

This problem involves inserting a new interval into a sorted, non-overlapping set of intervals and ensuring the resulting intervals remain sorted and non-overlapping. It also requires merging overlapping intervals as necessary.

Key Steps to Solve the Problem:

1. Determine Where to Insert the New Interval:
   • Traverse the original list of intervals and insert the new interval in its appropriate position based on its start value.
2. Merge Overlapping Intervals:
   • After inserting the new interval, traverse the list of intervals and merge any overlapping intervals to ensure the intervals are non-overlapping.
3. Preserve Sorting:
   • Since the given list is already sorted and we insert the new interval at the correct position, the list remains sorted.

Algorithm:

If there is an overlap (i.e., starti <= newEnd and endi >= newStart), merge the overlapping intervals by updating newInterval to:

Iterate over Intervals:

For each interval in the intervals array, if it does not overlap with newInterval, simply add it to the result.
If there is an overlap (i.e., starti <= newEnd and endi >= newStart), merge the overlapping intervals by updating newInterval to:

newInterval[0] = min(newInterval[0], starti);
newInterval[1] = max(newInterval[1], endi);

Once the merging is complete, the resulting array will be sorted and non-overlapping.

Add Remaining Intervals:

If there are intervals after the position of the merged interval, append them to the result array.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result; // Resultant array of intervals
    int i = 0, n = intervals.size();

    // Step 1: Add all intervals that come before the new interval
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        i++;
    }

    // Step 2: Merge overlapping intervals with newInterval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.push_back(newInterval); // Add the merged interval

    // Step 3: Add all intervals that come after the new interval
    while (i < n) {
        result.push_back(intervals[i]);
        i++;
    }

    return result;
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {6, 9}};
    vector<int> newInterval = {2, 5};

    vector<vector<int>> result = insertInterval(intervals, newInterval);
    cout << "Resulting Intervals: ";
    for (const auto& interval : result) {
        cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    cout << endl;

    return 0;
}

Complexity Analysis:

1. Time Complexity:
   • Traversal through all intervals happens once: O(n), where n is the number of intervals.
   • Merging overlapping intervals is constant time per iteration as only the current interval and newInterval are involved.
   Total: O(n).
2. Space Complexity:
   • Result is stored in a new vector: O(n).
   • Space used for storing merged intervals (in the result).

Edge Cases:

1. Empty Intervals:
   • intervals = [] and newInterval = [5, 7] → Result: [[5, 7]].
2. No Overlap:
   • intervals = [[1, 2], [3, 4]] and newInterval = [5, 6] → Result: [[1, 2], [3, 4], [5, 6]].
3. Complete Overlap:
   • intervals = [[1, 5]] and newInterval = [2, 3] → Result: [[1, 5]].