Overview

Given the elevations of N mountains, determine whether there exists a unique mountain that is higher than all other mountains (an independent peak). If such a mountain exists, output its elevation; otherwise, output 0.

Analysis

For a mountain to be an independent peak, it must satisfy the following two conditions: 1. The mountain has the maximum elevation among all mountains 2. There is exactly one mountain with the maximum elevation

If the maximum value appears multiple times, no mountain satisfies the condition of being “higher than all other mountains,” so no independent peak exists. Also, if there is only one mountain, that mountain itself is the independent peak.

A naive approach would be to compare each mountain against all other mountains, but this would result in a time complexity of \(O(N^2)\), which is too slow given the constraint \(N \leq 10^6\).

Algorithm

An efficient solution follows these steps: 1. Find the maximum value \(M\) of the entire array 2. Count how many times the maximum value \(M\) appears in the array 3. If the maximum value appears exactly once, output \(M\); if it appears two or more times, output 0

The case where there is only one mountain is handled as a special case.

Complexity

• Time complexity: \(O(N)\)
  • \(O(N)\) for finding the maximum value
  • \(O(N)\) for counting the maximum value
• Space complexity: \(O(N)\)
  • For storing the input array

Implementation Notes

• Use sys.stdin.read() for efficient input processing

• Check the case where there is only one mountain first

• Use the max() function to find the maximum value and the count() method to count its occurrences

• Don’t forget to output 0 when the maximum value appears multiple times

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    if n == 1:
        print(A[0])
        return
        
    max_val = max(A)
    count_max = A.count(max_val)
    
    if count_max == 1:
        print(max_val)
    else:
        print(0)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.