Problem overview
The method removeDuplicates(_ nums: [Int]) receives an array of integers and returns a new array holding each distinct value once. The statement allows any order for the result.
For [2, 3, 1, 1, 4, 3, -2, 1], the distinct values are 2, 3, 1, 4 and -2, so the method can return [2, 3, 1, 4, -2]. The input array is left as it is.
The budget is O(n^2) time and O(n) extra space. The extra space is the result array, and the quadratic time comes from a search through it for every element.
Approach: keep only values not seen yet
Walk through nums from left to right and keep a second array of the unique values found so far. For each value, ask whether the second array already contains it. If not, this is the first time the value appears, so append it. If it does, skip it.
Asking "is it in the array?" means scanning the array element by element until a match turns up or the end is reached. That scan costs up to the size of the unique array, and it runs once per element of nums. This is where the O(n^2) comes from. The quadratic cost is not required for correctness: a hash set answers the same question in constant time on average, and a later lesson uses one. Here the plain array search keeps the idea simple.
Because values are appended the first time they appear, the result keeps the order of first appearance. The statement doesn't require that order, but it makes the output predictable.
Step by step
- Create the result array.
var uniqueValues = [Int]()starts empty. It is avarbecause the loop appends to it. - Loop over the values. The indices are not needed, so
for value in numswalks the elements directly. - Check and append. The test
!uniqueValues.contains(value)is true only for a value not stored yet. Inside it,uniqueValues.append(value)stores the value, once. - Return the array. After the loop,
uniqueValuesholds every distinct value exactly once.
The solution in Swift
class Solution {
func removeDuplicates(_ nums: [Int]) -> [Int] {
var uniqueValues = [Int]()
for value in nums {
if !uniqueValues.contains(value) {
uniqueValues.append(value)
}
}
return uniqueValues
}
}
The Swift details worth knowing:
[Int]()is an empty array. It is the same as writingvar uniqueValues: [Int] = []. Either form tells Swift the element type, which it needs because there are no elements to infer it from.contains(_:)is a linear search. It works becauseIntisEquatable, and it checks elements one by one. It does not use any index or hash.!before an expression means "not". It is unrelated to the force-unwrap!that follows an optional.- The input is not modified. Arrays are values, and
numsis a constant parameter. The method builds a separate array and returns it. - A
Setdoes not keep order.Set(nums)removes duplicates inO(n)on average, but iterating it gives the values in an unspecified order. That is acceptable here, because the statement allows any order. This lesson uses the array version.
Complexity
Time: O(n^2). The loop runs n times. In the worst case, when all values are different, the k-th check scans k - 1 stored values, which sums to about n^2 / 2 comparisons. When many values repeat, the unique array stays short and the code runs faster, but the worst case defines the bound.
Space: O(n). In the worst case the result holds all n values.
Edge cases and common mistakes
- Empty input. The loop never runs, and the method returns
[]. - One element.
[7]returns[7]. - All equal.
[5, 5, 5]returns[5]. - No duplicates.
[1, 2, 3]returns[1, 2, 3]. - Negative numbers. They are compared like any other value, so the -2 in the example is kept once.
- Checking the input instead of the result. Calling
nums.contains(value)is always true, since the value came fromnums, and nothing would be appended. The check belongs onuniqueValues. - Using
letfor the result. Aletarray cannot be appended to, so the compiler rejects it.
Testing
[2, 3, 1, 1, 4, 3, -2, 1]gives[2, 3, 1, 4, -2].[]gives[].[7]gives[7].[5, 5, 5]gives[5].[1, 2, 3]gives[1, 2, 3].
