Median Value
Medium · rating 1300 · Sorting, Arrays
The first line contains n. The second line contains n integers. Print the median. For an odd count it is the middle value once sorted; for an even count it is the average of the two middle values, rounded down to an integer.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Sort the values. With an odd count the median is the single middle element at index n//2. With an even count, average the two middle elements at n//2 - 1 and n//2, using integer division for the floor.
a = sorted(map(int, ...))
if n % 2:
print(a[n//2])
else:
print((a[n//2 - 1] + a[n//2]) // 2)Complexity
Time: O(n log n) to sort. Space: O(n). (A quickselect can find the median in O(n) average time.)
Related problems
- Kth Largest Element — Medium
- Sort the Array — Easy
- Merge Two Sorted Arrays — Easy
- Leaderboard Ranking — Medium
- Maximum Window Sum — Medium
- Rotate Array Right — Medium