LESSON 315 OF 415 · SLIDING WINDOW

Longest Subarray Without Repeating Integers in Swift: O(n) Two Pointers

Given an input array of integers, find the length of the longest subarray without repeating integers.

Example

Input: nums = [2, 5, 6, 2, 3, 1, 5, 6]
Output: 5
Explanation: [5, 6, 2, 3, 1] or [6, 2, 3, 1, 5] are both valid and of maximum length 5

Note:

For this lesson, your algorithm should run in O(n) time and use O(n) extra space

STEP 1 OF 9

Guided

Ctrl + Enter to check

Longest Subarray Without Reapeating in Swift, explained

Problem overview

The method longestSubarrayWithoutReapeating (the lesson spells it that way, so the code does too) receives an array of integers and returns the length of the longest contiguous subarray in which no value appears twice.

In the example, nums = [2, 5, 6, 2, 3, 1, 5, 6]. The subarray [5, 6, 2, 3, 1] has five different values, and so does [6, 2, 3, 1, 5]. No longer subarray avoids a repeat, so the answer is 5. The statement asks for O(n) time and O(n) extra space.

Approach: a window and a set

Checking every subarray for repeats would take far more than linear time. The faster idea keeps a window of distinct values in a Set and moves it forward without ever starting over.

Use two indices. The index i is the left edge of the window. The index j is the first position that is not in the window yet. For each i, push j to the right for as long as nums[j] is not already in the set. When that stops, the window nums[i..<j] is the longest repeat-free subarray that starts at i, and its length equals the size of the set. Then drop nums[i] from the set and move on to i + 1.

The key point is that j never moves back. The values from i + 1 up to j are still distinct after nums[i] leaves, so the next window can keep them and only needs to grow from where j stopped.

Here is the idea on [1, 2, 1, 3]. At i = 0, j takes the 1 and the 2 and stops at the second 1, so the window has two values. Removing nums[0] leaves {2}. At i = 1, j continues from position 2: it takes the 1 and the 3 and reaches the end, so the set is {2, 1, 3} and the length 3 becomes the result. The remaining iterations can only find shorter windows.

Step by step

Create the set. uniqueNums is an empty Set<Int>(), declared with var because inserting into a set changes the variable. It holds the values of the current window, so testing for a repeat is a constant-time lookup.
Create the result. result starts at 0, which is also the right answer for an empty array.
Create the right edge. j starts at 0. It is declared before the loop over i because it never moves back.
Loop over the left edge. for i in 0..<nums.count tries every index as the start of a window.
Grow the window. A while loop runs as long as j < nums.count && !uniqueNums.contains(nums[j]). The && stops at the first false operand, so nums[j] is never read once j reaches the end.
Take the new value. Inside that loop, insert nums[j] into the set and do j += 1.
Record the length. After the loop, the window is i up to but not including j, which is exactly what the set holds. Set result to max(result, uniqueNums.count).
Slide the left edge. Remove nums[i] from the set, so the next window starts one position later. It is always present at this point: when the window is empty, the growing loop adds at least nums[i].
Return result.

The solution in Swift

class Solution {
    func longestSubarrayWithoutReapeating(_ nums: [Int]) -> Int {
        var uniqueNums = Set<Int>()
        var result = 0
        var j = 0
        for i in 0..<nums.count {
            while j < nums.count && !uniqueNums.contains(nums[j]) {
                uniqueNums.insert(nums[j])
                j += 1
            }
            result = max(result, uniqueNums.count)
            uniqueNums.remove(nums[i])
        }
        return result
    }
}

The Swift details worth a closer look:

Set is a value type. Inserting or removing changes the set, so it must be declared with var. A let set can't be modified.
Return values you don't use. insert returns a tuple saying whether the value was new, and remove returns the removed value, or nil if it wasn't there. Both are marked so that ignoring the result produces no warning.
The half-open range. 0..<nums.count excludes the upper bound, so i stops at the last valid index. Writing 0...nums.count would index one past the end and crash. For an empty array 0..<0 is an empty range, so the loop body never runs.
No ++. Swift has no increment operator; use j += 1.
max is a global function. max(result, uniqueNums.count) needs no import and takes two Int values.

Complexity

Time: O(n). Each index enters the set once, when j passes it, and leaves once, when i passes it. The two loops together do at most about 2n steps, each with constant average cost for the set operations.

Space: O(n). The set can hold every element when all values are different.

Edge cases and common mistakes

Empty array. The loop doesn't run and the method returns 0.
All values equal. [7, 7, 7] returns 1. The window holds one 7, then it is removed and the next 7 starts a new one.
No repeats at all. [1, 2, 3] returns 3: the first window already reaches the end, and the later windows only get shorter.
Repeat in the middle. [1, 2, 1, 3, 4, 2] returns 4, from the subarray [2, 1, 3, 4].
Resetting j inside the loop. It works but brings the running time back to quadratic.
Using the length j - i after removing nums[i]. Measure the window before the removal, as the solution does.
Checking only the neighbour. A repeat can be far from the current element, which is why the set holds the whole window.

Testing

[2, 5, 6, 2, 3, 1, 5, 6] gives 5.
[] gives 0.
[7, 7, 7] gives 1.
[1, 2, 3] gives 3.
[1, 2, 1, 3, 4, 2] gives 4.

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

Start learning free