Problem overview
The method distinctValues receives an array of integers and returns how many different values it contains. In the example [1, 5, -3, 1, -4, 2, -4, 7, 7], the distinct values are 1, 5, -3, -4, 2 and 7, so the answer is 6. The duplicates (the second 1, the second -4 and the second 7) are not counted again.
The statement asks for O(n) time and O(n) extra space.
Approach: a set of values seen so far
One way is to sort the array and count the places where a value differs from its neighbour. Sorting costs O(n log n), so it misses the budget. Comparing every pair is worse still, O(n²).
A hash set removes the need for order. It answers "is this value already here?" in constant time on average and silently ignores repeated insertions. The loop looks at each number once. If the set doesn't contain it, the number is new: add it to the set and count it. If the set contains it, an earlier copy was already counted, so skip it. The price is memory: in the worst case the set holds every element, which is the allowed O(n) extra space.
Step by step
- Create the set.
valuesis an emptySet<Int>()declared withvar, since a SwiftSetis a value type and inserting into it changes the variable. - Create the counter.
answerstarts at 0 and counts the distinct values found so far. - Loop over the numbers with
for value in nums. The order doesn't matter for counting. - Test for a new value.
if !values.contains(value)is true only the first time a number appears. - Record it. Inside the
if, insert the value and add one toanswerwith+= 1. Swift has no++operator. - Return
answer.
Tracing the example
Take [1, 5, -3, 1, -4, 2, -4, 7, 7]. The first three values, 1, 5 and -3, are new, so answer climbs to 3 and the set holds all three. The next 1 is already in the set and is skipped. Then -4 and 2 are new, which makes answer 5. The second -4 is skipped, 7 is new and brings answer to 6, and the last 7 is skipped. The loop ends with answer equal to 6, and the set holds exactly the six distinct values.
The solution in Swift
class Solution {
func distinctValues(_ nums: inout [Int]) -> Int {
var values = Set<Int>()
var answer = 0
for value in nums {
if !values.contains(value) {
values.insert(value)
answer += 1
}
}
return answer
}
}
Swift details worth a closer look:
inout. The parameter is declaredinout [Int], so the caller passes the array with an ampersand, as indistinctValues(&nums), and the caller's variable must be avar. This method only reads the array.- The result of
insert.insertreturns a tuple saying whether the value was new, and Swift allows ignoring it. That tuple is an alternative to thecontainscheck:if values.insert(value).inserted { answer += 1 }does the same in one lookup. !in a condition means "not". It is unrelated to the force-unwrap!that follows an optional.- Shortcut. Because
answeralways equals the number of elements in the set,Set(nums).countgives the same result. The loop spells out what that constructor does.
A sorting alternative
The set isn't the only way. Sort a copy of the array, then count the positions whose value differs from the one before. This version needs no hashing:
func distinctBySorting(_ nums: [Int]) -> Int {
let sortedNums = nums.sorted()
var count = 0
for i in 0..<sortedNums.count {
if i == 0 || sortedNums[i] != sortedNums[i - 1] {
count += 1
}
}
return count
}
It returns 6 for the example and 0 for an empty array. Sorting costs O(n log n), so it is slower than the set for large inputs, but it is useful when memory is tight, since it needs only the sorted copy. The set version trades that memory for speed.
Complexity
Time: O(n). The loop runs n times, and contains and insert take constant time on average.
Space: O(n). The set holds each distinct value once, up to n of them when nothing repeats.
Edge cases and common mistakes
- Empty array. The loop doesn't run, and the method returns 0. The empty set and the zero counter are already the right answer, so no special case is needed.
- All values equal.
[7, 7, 7]gives 1. - Counting every element. Incrementing
answeroutside theifreturns the array's length instead of the number of distinct values. - Forgetting the insert. Without
values.insert(value)the set stays empty, nothing is ever recognised as a repeat, and the result is again the array's length. - Calling with a constant. Because of
inout, passing an array declared withletis a compile error, and so is leaving out the ampersand. Declare the argument withvarand write&numsat the call. - Negative numbers and large values. They need no special handling:
-4or9_000_000_000is just another hashableInt, and the code does no arithmetic that could overflow.
Testing
[1, 5, -3, 1, -4, 2, -4, 7, 7]gives 6.[]gives 0.[7, 7, 7]gives 1.[1, 2, 3]gives 3.
