Start learning free

LESSON 268 OF 415 · HASH TABLE

Longest Subarray Without Repeating in Swift: O(n²) with a Set

Practice O(n2) Read the full explanation

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^2) time and use O(n) extra space.
(There exist faster solutions which we will discuss in future lessons)


STEP 1 OF 8
    Ctrl + Enter to check

    SWIFT · HASH TABLE

    Longest Subarray Without Reapeating in Swift, explained

    Problem overview

    The method longestSubarrayWithoutReapeating receives an array of integers and returns the length of the longest subarray in which no value repeats. A subarray is a run of neighbouring elements, so you can't skip over items.

    For nums = [2, 5, 6, 2, 3, 1, 5, 6] the answer is 5. Both [5, 6, 2, 3, 1] and [6, 2, 3, 1, 5] have five different values, and any run of six would have to repeat something.

    For this lesson the budget is O(n²) time and O(n) extra space. Faster solutions exist, but this lesson builds the simpler one first.

    Approach: try every start, extend until a repeat

    A subarray is fixed by its first index i and its last index j. The plan is to try every start. For each start, grow the subarray one element at a time and stop when the next element is already inside it.

    Stopping early is safe. If nums[i..j] already contains a repeat, every longer subarray from the same start contains it too, so nothing more can be learned from this i. A naive version would check each (i, j) pair by scanning the subarray for repeats, which costs O(n³) overall. A set removes that scan. It holds the values of the current subarray, and asking whether nums[j] is in it takes constant time on average. That leaves two nested loops, O(n²), and the set adds at most O(n) memory.

    Step by step

    1. Keep the best length. result starts at 0 and is declared with var, since it grows as longer subarrays are found. An empty array correctly yields 0.
    2. Choose each start. for i in 0..<nums.count tries every first element.
    3. Create a fresh set per start. uniqueNums is a var empty Set<Int>() inside the outer loop, so each new i begins with no values.
    4. Choose each end. for j in i..<nums.count starts at i, so the one-element subarray is checked first.
    5. Check for a repeat before adding. At this point the set holds the values of nums[i..<j]. If it already contains nums[j], break out of the inner loop.
    6. Record the length. Otherwise nums[i...j] is valid and has j - i + 1 elements, so update result with max.
    7. Add nums[j] to the set, after the check. Adding it first would make every value look like a repeat of itself.
    8. Return result after both loops finish.

    Tracing the example

    For [2, 5, 6, 2, 3, 1, 5, 6], start i = 0 accepts 2, 5 and 6, so result reaches 3. The next element is 2, which is already in the set, so the inner loop breaks. Start i = 1 accepts 5, 6, 2, 3 and 1, which lifts result to 5, then meets 5 again and breaks. Start i = 2 accepts 6, 2, 3, 1 and 5, a length of 5 as well, and breaks on the second 6. Later starts have too little room left to beat 5, so the method returns 5.

    The solution in Swift

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

    Swift details worth a closer look:

    • Half-open ranges. 0..<nums.count and i..<nums.count exclude the upper bound, so both indices stop at the last valid position. If the array is empty, 0..<0 is an empty range and the loop body never runs. (Writing 0...nums.count - 1 instead would crash on an empty array, because the range 0...-1 is invalid.)
    • break leaves only the inner for loop. The outer loop moves on to the next start.
    • max is a global function that returns the larger of two values.
    • The set is a value type. Declaring it inside the outer loop creates a new, independent empty set on every iteration.
    • The method name keeps the lesson's spelling, Reapeating. Use it exactly as written.

    Complexity

    Time: O(n²). For each of the n starts, the inner loop runs at most n times, and each set operation is constant time on average. The inner loop stops at the first repeat, so it is often shorter, but the worst case, an array of all-distinct values, visits every pair.

    Space: O(n). The set holds at most one subarray's worth of distinct values.

    Each start rebuilds its set from nothing, so work is repeated between neighbouring starts. A faster solution keeps one window and moves its left edge forward only when needed, which reaches O(n). This lesson stays with the simpler nested loops.

    Edge cases and common mistakes

    • Empty array. Returns 0.
    • All values equal. [7, 7, 7] returns 1. Each start accepts one element, then meets a repeat.
    • All values distinct. [1, 2, 3] returns 3, the whole array.
    • Creating the set outside the outer loop. Values from earlier starts would stay in it and wrongly block later subarrays.
    • Inserting before the check. Every nums[j] would be found in the set immediately, and the result would always be 0.
    • Confusing subarray and subsequence. Elements must be neighbours. For [1, 2, 1, 3] the answer is 3 ([2, 1, 3]), found by moving the start past the first 1.

    Testing

    • [2, 5, 6, 2, 3, 1, 5, 6] gives 5.
    • [] gives 0.
    • [7, 7, 7] gives 1.
    • [1, 2, 3] gives 3.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free