Problem overview
The method middleElement receives a list of integers, nums, with an odd number of items, and returns the item in the middle. The middle index is the size of the list divided by 2, rounded down. A list of 5 items has the indexes 0 to 4, and 5 divided by 2, rounded down, is 2: two items come before index 2 and two come after it.
For [1, 2, 3] the answer is 2. For [5, 9, 1, 8, 4] it is 1, because the middle is about the position and not about the size of the number. For [7] it is 7: 1 divided by 2, rounded down, is 0, so the only item is the middle one.
Approach: compute an index, then read it
With an odd number of items, there is exactly one item with the same number of items on each side. Its index is half the size, without the fraction. So the work has two small steps: find the index, then read the item at that index.
Java makes the first step easy. When both operands of / are int values, Java divides and keeps only the whole part, discarding the remainder. So 5 / 2 is 2, 3 / 2 is 1 and 1 / 2 is 0. No rounding function is needed. For an odd size 2k + 1, the result is always k, the index with k items on each side.
The second step is nums.get(index), which reads the item at that position. Indexes start at 0, and the size of a list comes from nums.size(), a method call with parentheses.
Step by step
- Find the middle index.
int middle = nums.size() / 2;divides the size by 2 with integer division and stores the result in anint. - Return the item there.
nums.get(middle)is the middle number.
The solution in Java
class Solution {
public int middleElement(List<Integer> nums) {
int middle = nums.size() / 2;
return nums.get(middle);
}
}
For the three examples, the method returns:
[1, 2, 3] -> 2
[5, 9, 1, 8, 4] -> 1
[7] -> 7
Some Java details are worth a closer look:
- Integer division. The type of
nums.size() / 2isint, because both sides areint. There is no2.5to round, which is why the result for a size of 5 is exactly 2. - The element type. With
List<Integer>,nums.get(middle)returns anInteger, and Java unboxes it into theintthe method returns. getdoesn't remove anything. The list is read, not changed.
Edge cases and common mistakes
- Using the size as the index.
nums.get(nums.size())is one past the end and throws anIndexOutOfBoundsException. Half the size is the way to reach the middle. - Using
size() / 2 - 1. That is the index before the middle. For[1, 2, 3]it returns 1 instead of 2. - Looking for the median. The middle element is chosen by position. The list is not sorted first, so
[5, 9, 1, 8, 4]returns 1, not 5. - Even sizes. The lesson only has odd sizes, but the code runs on any non-empty list. For
[1, 2, 3, 4], 4 / 2 is 2, so it returns 3, the upper of the two middle items. - An empty list. The constraints exclude it. For an empty list,
get(0)throws an exception with the messageIndex 0 out of bounds for length 0. - A single item.
1 / 2is 0, so the code returns the first item, which is also the last. No special case is needed.
Testing
[1, 2, 3]gives 2.[5, 9, 1, 8, 4]gives 1.[7]gives 7.
