Start learning free

LESSON 221 OF 415 · BRUTE FORCE

Longest Subarray Without Repeating in Swift: O(n^3) Brute Force

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


STEP 1 OF 6
    Ctrl + Enter to check

    SWIFT · BRUTE FORCE

    Longest Subarray Without Reapeating in Swift, explained

    Problem overview

    The method longestSubarrayWithoutReapeating(_ nums: [Int]) receives an array of integers and returns the length of the longest subarray in which no value appears twice. A subarray is a run of neighbouring elements, with no gaps and no reordering.

    For [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 no run of six has that property. The method returns only the length, not the subarray.

    The statement asks for O(n^3) time and O(1) extra space. That is a hint to use three nested levels of work: choose a start, choose an end, and check the run for repeats.

    Approach: grow each subarray until a repeat appears

    Every subarray is determined by its first index i and its last index j. A brute-force solution tries all those pairs and checks each run for repeats.

    A shortcut saves work without changing the idea. For a fixed i, extend j one step at a time. The run from i to j adds only one new element, nums[j], to the previous run. If that value already occurs in the run before it, the new run has a repeat, and so does every longer run that starts at i. The inner loop can stop right there with break. Otherwise the run is valid, and its length j - i + 1 is a candidate for the answer.

    Checking whether the new element occurs earlier in the run is itself a scan, with cost up to the run's length. So there are about n^2 pairs (i, j), each with a scan of up to n elements, hence O(n^3) in total. Faster solutions use a set or dictionary to avoid the scan, and the lesson leaves them for later.

    Step by step

    1. Start the answer at 0. var result = 0 holds the best length found so far. An empty array keeps it at 0.
    2. Choose the first index. for i in 0..<nums.count tries every starting position.
    3. Choose the last index. for j in i..<nums.count starts at i, so the one-element run is considered first.
    4. Look for a repeat. Save nums[j] in searchValue and take the slice nums[i..<j], the run before j. If it contains searchValue, break out of the inner loop.
    5. Record the length. If there was no break, the run nums[i...j] is valid and has j - i + 1 elements. Update result with max(result, j - i + 1). No else is needed, because the break skips this line.
    6. Return the answer after both loops.

    The solution in Swift

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

    The Swift details worth knowing:

    • Slices are views. nums[i..<j] has the type ArraySlice<Int>. It shares the original array's storage rather than copying it, which is why the space stays O(1). A slice keeps the original indices: nums[1..<4] has startIndex 1 and endIndex 4.
    • The slice can be empty. When j == i the range i..<i is empty, and contains on it gives false, so the first element of each run is always accepted. An empty range is legal. Only a range whose start is above its end is an error, and j never goes below i.
    • Half-open versus closed. i..<j leaves out j, which is exactly the "previous run". The run including j would be i...j.
    • max is a global function. max(result, j - i + 1) returns the larger of two values, which replaces an if that updates the answer.
    • break leaves only the inner loop. The outer loop moves on to the next start index.

    Complexity

    Time: O(n^3). There are up to n^2 / 2 pairs (i, j), and the contains call scans up to j - i elements. In the worst case, an array of all-different values, no break ever fires, and the total work is on the order of n^3. With many repeats the break cuts the inner loop short, but the bound stays the same.

    Space: O(1). The method keeps a few integers, and the slice does not copy the array.

    Edge cases and common mistakes

    • Empty array. The loops never run and the answer is 0.
    • One element. [1] gives 1.
    • All values equal. [4, 4, 4] gives 1, because every run of two has a repeat.
    • All values different. [1, 2, 3, 4] gives 4, the whole array.
    • Repeat at the end. [1, 2, 3, 1] gives 3, and [1, 2, 1, 2] gives 2.
    • Subarray versus subsequence. The values must be neighbours. In [1, 2, 1, 3], picking 1, 2 and 3 skips an element, which is not allowed.
    • Including j in the slice. With nums[i...j] the check would always find nums[j] itself, so every run would be rejected and the answer would be 0.
    • Using continue instead of break. After a repeat, longer runs from the same i still contain it. With continue they can be accepted wrongly, because the check compares the new element only with the run before it, and the old repeat is no longer compared with anything. For [1, 2, 1, 3, 2] that version returns 4 instead of 3.

    Testing

    • [2, 5, 6, 2, 3, 1, 5, 6] gives 5.
    • [] gives 0.
    • [1] gives 1.
    • [4, 4, 4] gives 1.
    • [1, 2, 3, 4] gives 4.
    • [1, 2, 3, 1] 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