Start learning free

LESSON 373 OF 415 · BIT MANIPULATION

Single Number in Swift: O(n log n) with Sorting

Practice O(n log n) Read the full explanation

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element in the array appears twice except for one element which appears only once.

Note:

Your algorithm should run in O(n log n) time and use O(1) extra space (when the array is sorted in place).
(There are faster solutions which we will discuss in future lessons)

Hints:

Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another.
Let's take an example:

nums = [2,1,3,1,3]
sortedNums = [1,1,2,3,3]

The single element is 2. What property does it satisfy that the other elements don't?

After sorting the array, the single element is the only one that is different than both its neighbors.
More exactly, in sorted nums, the element at index i is the single element if both these conditions hold true:

i is the first index, or the previous element is different from the element at index i
i is the last index, or the next element is different from the element at index i

We sort the array, thus the Time Complexity is O(n log n).
If we sort nums in place, we don't use any extra arrays, so the Extra Space used is O(1). (Sorting a copy, as Swift's sorted() does, would take O(n) extra space.)

STEP 1 OF 13

Guided

Ctrl + Enter to check

SWIFT · BIT MANIPULATION

Single Number in Swift, explained

Problem overview

The method singleNumber receives a non-empty array nums in which every value appears exactly twice, except one value that appears once. It returns that single value. The statement asks for O(n log n) time and O(1) extra space.

For [4,1,2,1,2] the answer is 4, because 1 and 2 each appear twice. For [2,2,1] the answer is 1, and for [1] it is 1.

Approach: sort, then find the value with no equal neighbor

Counting each value with a dictionary would work in linear time but uses extra memory proportional to the input. Comparing every pair of elements needs no memory but takes O(n²) time. Sorting sits between them.

After sorting in ascending order, equal values sit next to each other, so the duplicates form pairs: [4,1,2,1,2] becomes [1,1,2,2,4]. Every value that has a pair has an equal neighbor on one side. The single value is the only one whose neighbors on both sides are different, or missing because it sits at an end of the array. Scanning the sorted array for that value finds the answer.

The lesson's tests expect this approach, with sorting costing O(n log n). Later lessons on the same problem show faster solutions.

Step by step

Write a helper isSingleNumber(_ nums: [Int], _ index: Int) -> Bool above singleNumber. It says whether the element at index has no equal neighbor.
Check the left neighbor. If index > 0 and nums[index - 1] equals nums[index], the element has a pair, so return false. The index > 0 test comes first so the code never reads before the start.
Check the right neighbor. If index < nums.count - 1 and nums[index] equals nums[index + 1], return false in the same way.
Return true at the end of the helper: neither neighbor matched.
Handle the one-element array in singleNumber: if nums.count == 1, return nums[0]. The helper would handle it, but this skips the sort and the loop.
Sort a copy. Declare a constant sorted holding nums.sorted(). Function parameters are constants in Swift, so nums can't be sorted in place.
Scan the indices of sorted with a loop variable i over 0..<sorted.count.
Test each one. If isSingleNumber(sorted, i) is true, return sorted[i].
Return -1 after the loop. The input always contains a single number, so this line is only a fallback that the compiler requires, because a function with a result must return on every path.

A walk through the scan

Take [4,1,2,1,2]. Sorting gives [1,1,2,2,4], and the loop asks the helper about each index in turn:

Index 0 holds 1. There is no left neighbor, but the right neighbor is also 1, so the helper returns false.
Index 1 holds 1. The left neighbor is 1, so it returns false at the first check.
Indexes 2 and 3 hold 2. Each has an equal neighbor, on the right and on the left respectively, so both return false.
Index 4 holds 4. Its left neighbor is 2, and it has no right neighbor, because 4 < nums.count - 1 is false. Neither check returns, so the helper returns true, and the method returns sorted[4], which is 4.

The scan always finds the answer, because every other value occupies two adjacent slots and gets a false from one side or the other.

The solution in Swift

class Solution {
    private func isSingleNumber(_ nums: [Int], _ index: Int) -> Bool {
        if index > 0 && nums[index - 1] == nums[index] {
            return false
        }
        if index < nums.count - 1 && nums[index] == nums[index + 1] {
            return false
        }
        return true
    }
    func singleNumber(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return nums[0]
        }
        let sorted = nums.sorted()
        for i in 0..<sorted.count {
            if isSingleNumber(sorted, i) {
                return sorted[i]
            }
        }
        return -1
    }
}

The Swift details worth knowing:

sorted() versus sort(). sorted() returns a new array and leaves the original alone. sort() sorts a var array in place and returns nothing. With var arr = [3,1,2], the call arr.sorted() gives [1, 2, 3] while arr stays [3, 1, 2]; after arr.sort(), arr is [1, 2, 3].
Short-circuit &&. In index > 0 && nums[index - 1] == nums[index], the right side runs only when the left side is true. That is what makes the guard work: at index 0 the expression nums[-1] is never evaluated. Reading it would crash the program, because Swift checks array bounds at run time.
private. The helper is visible only inside the class. Calling it from singleNumber works without any prefix.
The sorted copy and extra space. nums.sorted() allocates a new array, so strictly speaking this uses O(n) memory, not the O(1) the statement mentions.
Argument labels. The underscores in _ nums and _ index remove the argument labels, so the call is isSingleNumber(sorted, i).

Complexity

Time: O(n log n). Sorting costs O(n log n). The scan then checks each index in constant time, which adds O(n).

Space: O(n) as written. The sorted copy holds n integers. The statement's O(1) assumes sorting the input itself in place; the algorithm is otherwise the same.

Edge cases and common mistakes

One element. [1] returns 1 right away.
Single value at either end. [1,2,2] sorts to [1,2,2] and returns 1, using only the right neighbor. [1,1,2] returns 2, using only the left neighbor.
Negative numbers. [-3,5,-3] sorts to [-3,-3,5] and returns 5. Sorting handles negatives like any other value.
Checking only one side. If the helper looked only to the right, the second element of every pair would look single. Both neighbors must be checked.
Removing the bounds guards. At index 0, nums[index - 1] reads index -1, and at the last index, nums[index + 1] reads past the end. Either crashes.
Looking at the unsorted array. In [4,1,2,1,2] the equal values are not adjacent, so the neighbor test says nothing until the array is sorted.

Testing

[2,2,1] gives 1.
[4,1,2,1,2] gives 4.
[1] gives 1.
[-3,5,-3] gives 5.
[1,1,2] gives 2.

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free