DSCPPAS269 - Editorial

editorial
, ,
1

Problem Statement:

You are given a list of integers heights representing the heights of N mountain peaks. For each peak, you need to find the height of the next higher peak that comes after it in the list. If there is no higher peak after a given peak, return -1 for that peak.

Approach:

This problem can be efficiently solved using a stack-based approach, which allows us to traverse the list of peaks once and determine the next higher peak for each element in linear time.

The main idea is to iterate through the list of peaks while maintaining a stack to keep track of the indices of peaks for which we are yet to find a higher peak. As we move through the list, we compare the current peak’s height with the heights of the peaks stored in the stack. If the current peak is higher than the peak at the index stored at the top of the stack, we have found the next higher peak for that index, so we update the result and pop the index from the stack. We continue this process until we’ve processed all peaks. Peaks that never find a higher peak after them will retain the default value of -1 in the result.

Step-by-Step Explanation:

  1. Initialize the Result Vector:

    • We initialize a result vector of the same size as heights with all elements set to -1, since any peak that doesn’t have a higher peak after it will return -1.

  2. Stack for Indices:

    • We use a stack to store indices of the peaks. This stack helps in tracking the indices of the peaks for which we are looking for the next higher peak.

  3. Iterating Through the Heights:

    • As we iterate over the heights, for each peak:
      • We check if the current peak height is greater than the height of the peak at the index stored on the top of the stack.
      • If it is, it means we’ve found the next higher peak for the peak at the top of the stack. We update the result for that index and pop the stack.
      • We continue this until either the stack is empty or the current peak is not higher than the peak at the top of the stack.
    • After processing, we push the current index onto the stack.

  4. Final Result:

    • Once the loop finishes, the result vector will contain the height of the next higher peak for each peak, or -1 if no higher peak exists after it.

Example:

Consider the following list of peaks: [5, 3, 8, 7, 6, 4].

  • Processing Peak 5: No higher peak encountered yet, so push index 0 onto the stack.
  • Processing Peak 3: No higher peak for peak 5 yet, push index 1.
  • Processing Peak 8: Peak 8 is higher than peaks 3 and 5, so update their results and push index 2.
  • Processing Peak 7: No higher peak for peak 8 yet, push index 3.
  • Processing Peak 6: No higher peak for peak 7 yet, push index 4.
  • Processing Peak 4: No higher peak for peak 6 yet, push index 5.

Final result: [8, 8, -1, -1, -1, -1].

Complexity:

  • Time Complexity: The solution runs in O(N) time, where N is the number of peaks, since each element is pushed and popped from the stack at most once.
  • Space Complexity: The space complexity is O(N) for the stack and the result vector.