Problem overview
The function findDuplicates receives an IntArray called nums and returns a new IntArray holding every value that appears more than once. Each such value must be listed once, however many copies there are, and the result can be in any order.
In the example, [2, 3, 1, 1, 4, 3, 2, 1], the value 1 appears three times, 2 and 3 twice each, and 4 once. So the answer holds 1, 2 and 3, and not 4.
The statement asks for O(n) time and O(n) extra space.
Approach: count as you go, record at the second sighting
The brute-force version counts the copies of each value by scanning the whole array again, which is O(n²). A HashMap avoids the rescanning: it maps each number to how many times it has been seen so far, and a lookup or update costs constant time on average.
The one subtle point is when to record a duplicate. A value is a duplicate from the moment its count reaches 2. If you added it whenever the count was 2 or more, a value with three copies would be added twice. Adding it exactly when the count becomes 2 happens once per value, however many more copies follow. So the result needs no second pass and no de-duplication.
On the example, the counts reach 2 at the second 1, then the second 3, then the second 2. The third 1 raises its count to 3, which is not 2, so nothing is added. The function returns [1, 3, 2], which is a valid answer because the order is free.
Step by step
- Prepare the result.
resultis anArrayListof integers. The size of the answer isn't known in advance, so a growable list is easier than an array. - Prepare the counts.
freqis aHashMap<Int, Int>from a number to the times it has appeared. - Loop over the values.
for (value in nums)processes every number once. - Increase the count. Read the current count with
getOrDefault(value, 0), so a number seen for the first time counts as 0, add 1, and store the result back with the index operator. - Test for exactly 2. This is the moment a value becomes a known duplicate.
- Record it. Add
valuetoresult. - Convert and return. The function returns an
IntArray, sotoIntArray()copies the list into one.
The solution in Kotlin
class Solution {
fun findDuplicates(nums: IntArray): IntArray {
val result = ArrayList<Int>()
val freq = HashMap<Int, Int>()
for (value in nums) {
freq[value] = freq.getOrDefault(value, 0) + 1
if (freq[value] == 2) {
result.add(value)
}
}
return result.toIntArray()
}
}
Kotlin details that matter here:
- Reading a map gives a nullable.
freq[value]has the typeInt?, and it isnullfor a missing key. That is whyfreq[value] + 1wouldn't compile and why the code usesgetOrDefault(value, 0), which returns a plainInt. - Writing uses the same brackets.
freq[value] = ...calls the map'ssetoperator, replacing the old count or creating the entry. - Comparing an
Int?with anIntis allowed.freq[value] == 2compiles, and it is simply false if the value werenull. Here the key was stored one line earlier, so it is nevernull. Kotlin's==compares contents, so there is no reference-equality trap with boxed numbers. - The list-to-array step is explicit. An
ArrayList<Int>is not anIntArray, and Kotlin doesn't convert one to the other on its own.toIntArray()does the copy.
Why a map and not a set
A HashSet can tell you whether a value was seen before, and for this problem that is nearly enough: when add returns false, the value is a repeat. The trouble is the third copy, which also returns false and would be recorded again. The map's counts are what let the code say "the second time, and only the second time". Keeping a count also generalises to questions such as "which values appear exactly three times?".
Complexity
Time is O(n): each element costs a constant number of map operations on average, and the final copy is at most n elements. Space is O(n): the map holds one entry per distinct value, and the result holds at most half of the input's elements.
Edge cases and common mistakes
- Checking
>= 2instead of== 2. A value with three copies would be added on its second and again on its third sighting, giving duplicates in the answer. - Checking after the update, not before. The test
freq[value] == 2must come after the count has been increased. Placed before the update, it would fire one element late. - No duplicates.
[1, 2, 3]returns an empty array. - Empty input. The loop doesn't run, and the function returns an empty array.
- Using
freq[value] + 1directly. It fails to compile, because the left side may benull; the compiler saysoperator call is prohibited on a nullable receiver of type 'Int?'. UsegetOrDefault, or(freq[value] ?: 0) + 1.
Testing
[2, 3, 1, 1, 4, 3, 2, 1]returns1, 3, 2in the order shown above; any order is accepted.[5, 5, 5, 5]returns[5], one entry despite four copies.[]returns[].