Problem overview
The method findDuplicates receives an Array[Int] called nums and returns a new Array[Int] with the values that appear more than once. Each duplicated value is listed one time, however many copies the input holds, and the result can be in any order.
For Array(2, 3, 1, 1, 4, 3, 2, 1) the values 1, 2 and 3 repeat, while 4 appears once. The answer holds 1, 2 and 3. The value 1 appears three times, but it must be reported only once.
The lesson asks for O(n) time and O(n) extra space.
Approach: count as you go and report at the second copy
The brute-force solution compares every element with every other, which costs O(n²). A hash map avoids that. It maps each number to how many times the loop has seen it so far, and each lookup and update takes constant time on average.
The key observation is about when to report a value. A value is a duplicate the moment its count reaches 2, because that is the first time you meet a second copy. If you add the value to the result at that exact moment, then a value with three or four copies is not added again, because its count moves on to 3 and 4 and never equals 2 again. So there is no need for a second pass or a second set to avoid repeats.
On the example the counts change as follows. The values 2, 3 and 1 are seen once each. The next 1 brings its count to 2, so 1 is added to the result. The value 4 is seen once, then 3 reaches 2 and is added, then 2 reaches 2 and is added. The final 1 raises its count to 3, which is not 2, so nothing happens. The result is 1, 3, 2, in the order the second copies appeared.
Step by step
- Create the result buffer.
resultis a mutableArrayBuffer[Int], a growable array to collect duplicates in as they are discovered. - Create the count map.
freqis a mutableHashMap[Int, Int]from a number to the times it has appeared. - Loop over the numbers with
for (value <- nums)so every element is counted. - Increase the count.
freq.getOrElse(value, 0)gives the current count, or 0 when the value is not in the map yet. Add 1 and store it back withfreq(value) = ..., which inserts a new key or replaces the old count. - Test for exactly 2. The check is
freq(value) == 2, not "at least 2", which would report a value again for each further copy. - Record the duplicate. Inside the
if,result += valueappends it to the buffer. - Convert and return. The method must return an
Array, soresult.toArraycopies the buffer into one.
The solution in Scala
class Solution {
def findDuplicates(nums: Array[Int]): Array[Int] = {
val result = mutable.ArrayBuffer[Int]()
val freq = mutable.HashMap[Int, Int]()
for (value <- nums) {
freq(value) = freq.getOrElse(value, 0) + 1
if (freq(value) == 2) {
result += value
}
}
return result.toArray
}
}
The Scala details worth a closer look:
- The
mutable.prefix. Names such asmutable.ArrayBufferrefer to the packagescala.collection.mutable. In your own file that prefix only compiles afterimport scala.collection.mutable; without it the compiler reports "Not found: mutable". - Missing keys throw. Reading
freq(value)for a key that isn't in the map throws aNoSuchElementException. That is why the count is read withgetOrElse(value, 0)before the first write. After the assignment on the line above, the key is present, sofreq(value)in theifis safe. - Assignment through parentheses.
freq(value) = nis a call to the map'supdatemethod. It inserts the key if it is new and replaces the value if it exists. +=on a buffer.result += valueappends in place, becauseresultis a mutable buffer. AnArrayhas a fixed size, which is why the code gathers results in anArrayBufferfirst.
Complexity
Time: O(n). The loop visits each element once and does a constant number of map and buffer operations per element, each constant on average. The final toArray is O(d), where d is the number of duplicates, and d is at most n / 2.
Space: O(n). The map holds one entry per distinct value, up to n of them. The result buffer adds at most n / 2 more.
Edge cases and common mistakes
- No duplicates.
Array(1, 2, 3)gives an empty array. - Many copies.
Array(5, 5, 5, 5)givesArray(5), because only the second copy triggers the report. - Empty array. The loop doesn't run and the result is empty.
- Using "at least 2". Checking
freq(value) >= 2would add 5 three times for the input above. - Checking before counting. If the
ifran before the count was updated, a value would be reported one copy late, and a value with exactly two copies would be missed. - Reading a missing key.
freq(value) + 1on a value seen for the first time throws instead of starting at 0. - Result order. The values come out in the order of their second copies, not the order of the first ones. Because the statement allows any order, that is fine.
Testing
Array(2, 3, 1, 1, 4, 3, 2, 1)gives the values 1, 3 and 2, in that order.Array(5, 5, 5, 5)givesArray(5).Array(1, 2, 3)gives an empty array.Array()gives an empty array.
