Problem overview
The method removeRepeats gets an ArrayBuffer[Int] called nums and returns a new ArrayBuffer[Int] in which each value appears once. The first copy of each value stays, later copies are dropped, and the values keep the order in which they first appear.
For [3, 1, 3, 2, 1] the answer is [3, 1, 2]: the second 3 and the second 1 are repeats. For [6, 6, 6, 6] it is [6], and for [4, 9, 2], which has no repeats, the answer is the same three numbers.
Approach
Read the numbers from left to right and remember the ones already met. A number that has not been met is the first copy: keep it. A number that has been met is a repeat: skip it. A set answers "have I seen this?" quickly, and reading in order keeps the first copies in their original order.
Step by step
- Create an empty mutable set
seenofInt. - Create an empty
ArrayBuffer[Int]calledresult. - Loop over
numswithfor (num <- nums). - Inside, check
!seen.contains(num). The!turns the answer around, so the check is true for a number not yet in the set. - In that branch, append the number to
resultand add it toseen, both with+=. - After the loop, return
result.
The solution in Scala
class Solution {
def removeRepeats(nums: ArrayBuffer[Int]): ArrayBuffer[Int] = {
val seen = scala.collection.mutable.Set[Int]()
val result = ArrayBuffer[Int]()
for (num <- nums) {
if (!seen.contains(num)) {
result += num
seen += num
}
}
return result
}
}
Both seen and result are vals, yet both grow: val only fixes which object the name refers to, not what is inside it. The return must come after the loop, otherwise only the first number would come back.
Why check before adding
You could add every number to the set and only look at its size at the end, but then you would lose the order. The set tells you whether this is the first copy; the buffer remembers the order. For [3, 1, 3, 2, 1] the set ends up with three values, and the buffer receives exactly those three, at the moment each is first met.
Testing
With the lesson's examples the method returns 3 1 2, 6 and 4 9 2 (the tests print lists as values separated by spaces).
Another way
Scala's buffers already have a method for this:
val unique = ArrayBuffer(3, 1, 3, 2, 1).distinct
It gives ArrayBuffer(3, 1, 2), the same result. Writing the loop yourself shows how it works, and the same set-and-result pattern comes back in problems where distinct is not enough.
Edge cases and common mistakes
- Using only a set. Converting with a set alone gives no promise about order, so the result may not follow the first appearances. The buffer keeps the order.
- Adding to
seenbut not toresult, or the other way round. A number must go into both when it is a first copy. - Appending before the check. That keeps every number, repeats included.
- Negative numbers and large values need no special care: a set of
Intholds any of them, and the limits of a billion in size fit in anInt.
