Problem overview
The method removeDuplicates receives an Array[Int] called nums and returns a new Array[Int] that holds each distinct value once. The result can be in any order.
For Array(2, 3, 1, 1, 4, 3, -2, 1) the distinct values are 2, 3, 1, 4 and -2, so the result has five elements. The statement shows them as 2, 3, 1, 4, -2, but since any order is accepted, 4, 3, 2, 1, -2 or any other arrangement is just as valid.
The lesson asks for O(n) time and O(n) extra space.
Approach: let a hash set drop the repeats
A set stores each value at most once. Inserting a value that is already present does nothing, so duplicates disappear without any extra work. A hash set also does an insertion in constant time on average, so adding all n numbers costs O(n). Once every number has been inserted, the set contains exactly the distinct values, and converting it to an array gives the answer.
The price of this approach is order. A hash set arranges its elements by hash code, not by insertion order, so the result usually doesn't follow the order of the input. The statement allows that. If you needed the first occurrence of each value kept in input order, you would use a LinkedHashSet instead.
Step by step
- Create an empty mutable hash set of
IntnameduniqueValues:scala.collection.mutable.HashSet[Int](). The defaultSetin Scala is immutable, so the mutable class is named with its full package. - Loop over
numswithfor (value <- nums)and calluniqueValues.add(value)for each element.addreturnsfalsewhen the value is already in the set, so there is no need to check first. - Convert and return.
uniqueValues.toArraycopies the set's elements into a newArray[Int], which is the return type the method needs.
The solution in Scala
class Solution {
def removeDuplicates(nums: Array[Int]): Array[Int] = {
val uniqueValues = scala.collection.mutable.HashSet[Int]()
for (value <- nums) {
uniqueValues.add(value)
}
return uniqueValues.toArray
}
}
The Scala details worth a closer look:
- The ignored result of
add. The call returns aBoolean, and the loop throws it away. That is fine here, because the side effect on the set is what matters. toArraybuilds a new array. The returned array is independent of the set and ofnums, which is left unchanged. For aHashSet[Int]the element type is known, so the result is anArray[Int], as the method signature requires.- Order is not specified. The elements of the result come out in whatever order the hash set holds them, so don't rely on it. If you want a predictable order, sort the result with
.sorted, which returns a new sorted array: for the example it gives 1, 2, 3, 4 and -2 in the order-2, 1, 2, 3, 4. - Shorter forms exist.
nums.distinctreturns the distinct values in first-seen order, andnums.toSet.toArraydoes the same job as the loop. The lesson writes the loop to practise the set.
Complexity
Time: O(n). There are n insertions, each constant time on average, and one final pass that copies at most n elements into the array.
Space: O(n). The set holds up to n values when all of them are different, and the result array needs room for the same number.
Edge cases and common mistakes
- Empty array. The set stays empty and the result is an empty array.
- All values equal.
Array(5, 5, 5)gives an array with the single element 5. - No duplicates. The result has the same elements as the input, possibly in a different order.
- Comparing with an expected array by position. Since the order isn't fixed, compare after sorting if you test it yourself. Also,
==on two arrays compares references, not contents, soArray(1, 2) == Array(1, 2)isfalse. Convert both withtoListbefore comparing. - Using the immutable
Set. It has noaddmethod that changes it in place, so the loop wouldn't do what you want.
Testing
Array(2, 3, 1, 1, 4, 3, -2, 1)gives the values -2, 1, 2, 3, 4 once each, in some order.Array(5, 5, 5)givesArray(5).Array(1, 2, 3)gives the same three values.Array()gives an empty array.
