Problem overview
The function distinctValues receives an IntArray called nums and returns how many different values it contains. In the example, [1, 5, -3, 1, -4, 2, -4, 7, 7] has nine elements, but 1, -4 and 7 each appear twice. The different values are 1, 5, -3, -4, 2, 7, so the answer is 6.
The statement asks for O(n) time and O(n) extra space.
Approach: remember what you have seen
The brute-force way compares every element with every other one, which takes O(n²) time. Another way sorts the array and counts the places where the value changes. That is O(n log n) time, but it needs no extra set.
This lesson uses a HashSet to get O(n). A hash set answers "is this value in here?" in constant time on average. Walk through the array once. If the current value isn't in the set yet, it is a new distinct value: put it in the set and add one to a counter. If it is already there, skip it. Each element costs one lookup, so the whole pass is linear. The price is the set itself, which can hold up to n values, hence the O(n) extra space.
On the example, the counter goes up for 1, 5, -3, then stays still for the second 1, goes up for -4 and 2, stays for the second -4, goes up for 7 and stays for the second 7. It ends at 6.
Why not a simple array of flags indexed by value? Because the values can be negative or huge, so there is no small range to index into. A hash set handles any Int without you knowing its range in advance, and it only stores the values that actually occur.
Step by step
- Create the set.
valuesis an emptyHashSet<Int>(). It is avalbecause the variable never points to another set; the set's contents are what change. - Create the counter.
answeris avarstarting at 0, because it changes as new values appear. - Loop over the array.
for (value in nums)visits every element once. The order doesn't matter for counting. - Test for a new value.
!values.contains(value)is true only the first time a number shows up. - Record it. Inside the
if, add the value to the set and incrementanswer. From then on, later copies of this number find it in the set and are skipped. - Return the counter.
The solution in Kotlin
class Solution {
fun distinctValues(nums: IntArray): Int {
val values = HashSet<Int>()
var answer = 0
for (value in nums) {
if (!values.contains(value)) {
values.add(value)
answer++
}
}
return answer
}
}
A few Kotlin details:
HashSet<Int>()is a constructor call withoutnew. The element type isInt; on the JVM the set stores boxed integers, which is why it uses more memory than the originalIntArray.for (value in nums)loops over the elements themselves, not the indices. For an empty array the loop body never runs.answer++adds one to avar. It is a statement here; you don't use its value.- The two steps inside the
ifcould be merged, sinceaddreturnstruewhen the value was new. The lesson keeps the check and the insertion separate so each step is easy to see.
A shorter way to say the same thing
Once you see the mechanism, the loop can be collapsed. Building a set from the whole array and asking for its size gives the same count, because the set already keeps only distinct values:
fun distinctValues(nums: IntArray): Int {
return nums.toHashSet().size
}
Both versions do the same work: one hash lookup per element. The longer version is worth writing first because it shows where the counter comes from and why the count only goes up on a first sighting.
Complexity
Time is O(n): one pass, with a contains and at most one add per element, each constant on average. Space is O(n) in the worst case, when every element is different and all of them end up in the set.
Edge cases and common mistakes
- Empty array. The loop doesn't run and the function returns 0, which is right.
- All elements equal.
[7, 7, 7]returns 1. - Counting inside the wrong branch. If you increment
answerfor every element, you get the array's length instead of the number of distinct values. - Adding before checking. If you add the value to the set first and then test
contains, every value looks like a duplicate of itself and nothing is counted. - Duplicates that are far apart. The set remembers every value seen so far, not just the previous one, so
[4, 9, 4]counts4once and returns 2. - Negative numbers. They are ordinary values to a set;
-3and-4in the example count like any other.
Testing
Try these in the editor above and compare with the expected results:
[1, 5, -3, 1, -4, 2, -4, 7, 7]returns6.[]returns0.[7, 7, 7]returns1.