HackerRank Find the Median Java Solution Explained
Problem Overview
Original Problem: Find the Median | HackerRank
Difficulty: Easy
Category: Arrays, Sorting
Description: Given an unsorted array of integers with an odd number of elements, find the median—the middle element after sorting the array, where an equal number of elements are less than and greater than it. Return the median as an integer.
This problem, part of HackerRank’s One Week Preparation Kit (Day 1 Mock Test), is ideal for beginners to practice sorting and array manipulation in Java, key skills for coding interviews.
Understanding the Problem
The Find the Median problem requires you to determine the median of an unsorted array of integers. The median is the middle value in a sorted array when the number of elements is odd, ensuring an equal number of elements are on either side. For example, in the array [3, 1, 4, 1, 5], sorting gives [1, 1, 3, 4, 5], and the median is 3 (the third element). The input array always has an odd number of elements, simplifying the median calculation, and the task is to return this value as an integer.
Input and Output
Input:
First line: An integer n, the size of the array.
Second line: n space-separated integers arr[i].
Output:
An integer representing the median of the sorted array.
Constraints:
1 ≤ n ≤ 1,000,001
n is odd.
-10,000 ≤ arr[i] ≤ 10,000
The array may contain duplicates.
Initial Reasoning
To solve this, we need to:
Sort the array to arrange elements in ascending order.
Since n is odd, the median is the element at index n/2 in the sorted array.
Handle large arrays efficiently, as n can be up to 1,000,001.
Use Java’s built-in sorting to simplify the process, as the constraints allow for O(n log n) time complexity.
This approach is straightforward and leverages Java’s sorting capabilities, making it accessible for beginners.
Thought Process
Here’s the step-by-step logic:
Read the Input: Use the provided code to read the array size n and the array elements.
Sort the Array: Sort the array in ascending order to position the median at the middle index.
Find the Median: Since n is odd, the median is the element at index n/2 (using zero-based indexing). For example, if n = 5, the median is at index 2.
Handle Constraints:
The array can be large (up to 1,000,001 elements), so use efficient sorting (e.g., Java’s Collections.sort).
Elements are within [-10,000, 10,000], so int is sufficient (no need for long).
Duplicates are allowed and don’t affect the median (e.g., [1, 1, 3, 4, 5] still has median 3).
Edge Cases:
If n = 1, the array has one element, which is the median.
For large n, sorting must be efficient to avoid performance issues.
The constraints ensure n is odd, so no need to handle even-sized arrays.
Pseudocode
// findMedian method:
Sort the array
Retrieve and return the median
Solution Code
// Note: This is one of many possible solutions
// Note: Due to HackerRank's test constraints, variable names are not updated in the code below to follow Java naming conventions.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
public static int findMedian(List<Integer> arr) {
// Sort the array efficiently in ascending order
Collections.sort(arr);
// Return the middle element (n is odd, so n/2 gives the median index)
return arr.get(arr.size() / 2);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int n = Integer.parseInt(bufferedReader.readLine().trim());
List arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
int result = Result.findMedian(arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
} Step-by-Step Explanation
Let’s break down the Java solution for beginners:
Input Handling:
The main method reads:
n, the array size, using Integer.parseInt(bufferedReader.readLine().trim()).
A line of n space-separated integers, processed into a List<Integer> using Stream.of and map(Integer::parseInt).
Sorting the Array:
In findMedian, sort the List<Integer> using Collections.sort(arr), which implements an efficient dual-pivot quicksort algorithm with O(n log n) time complexity.
This arranges the elements in ascending order (e.g., [3, 1, 4, 1, 5] → [1, 1, 3, 4, 5]).
Finding the Median:
Since n is odd, the median is at index n/2. For example, if n = 5, n/2 = 2, so the median is the element at index 2.
Use arr.size() / 2 to get the index and arr.get() to retrieve the median value.
Return this value as an int, as the constraints (-10,000 ≤ arr[i] ≤ 10,000) ensure it fits within an integer.
Output Handling:
In the main method, write the result to the output file using bufferedWriter.write(String.valueOf(result)).
Add a newline with bufferedWriter.newLine().
Close bufferedReader and bufferedWriter to prevent resource leaks.
Common Mistakes to Avoid
Here are common pitfalls for beginners:
Not Sorting the Array: Attempting to find the median without sorting (e.g., looking for the “middle” value in the unsorted array) will give incorrect results, as the median requires sorted order.
Using Incorrect Index for Median: Forgetting that Java uses zero-based indexing may lead to off-by-one errors. The median is at arr.size() / 2, not (arr.size() + 1) / 2.
Ignoring Large Array Sizes: For n up to 1,000,001, inefficient sorting or excessive memory use (e.g., creating multiple copies of the array) can cause performance issues. Stick to Collections.sort for efficiency.
Real-World Application
Finding the median is a common operation in data analysis and statistics. For example, in financial applications, the median income of a dataset can provide a better measure of central tendency than the mean when outliers are present. In machine learning, medians are used in data preprocessing to handle skewed distributions. This problem teaches sorting and array access, skills critical for data processing and algorithm design in software development.
FAQs
Q: Why use Collections.sort instead of a custom sorting algorithm?
A: Collections.sort is optimized (O(n log n) using dual-pivot quicksort) and part of Java’s standard library, making it reliable and beginner-friendly for this problem.
Q: Can I find the median without sorting?
A: For large arrays, algorithms like QuickSelect can find the median in O(n) time, but for this problem’s constraints and simplicity, sorting (O(n log n)) is sufficient and easier to implement.
Q: What if the array has duplicates?
A: Duplicates don’t affect the median. After sorting, the middle element is still the median, regardless of repeated values (e.g., [1, 1, 3, 4, 5] has median 3).