Start learning free

LESSON 240 OF 338 · HASH TABLE

Longest Subarray Without Repeating in Go: 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 reapeating 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

    GO · HASH TABLE

    Longest Subarray Without Reapeating in Go, explained

    Problem overview

    The function longestSubarrayWithoutRepeating receives a slice of integers, nums, and returns the length of the longest contiguous subarray in which no value appears twice. 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] qualify, and no window of length 6 is free of repeats.

    This lesson asks for O(n²) time and O(n) extra space. Faster solutions exist and belong to other lessons on this problem.

    Approach: try every start, extend until a repeat

    A subarray is fixed by its first index i and its last index j. Checking every pair (i, j) and testing each subarray for duplicates from scratch would cost O(n³). Two observations bring that down to O(n²).

    • Extend one element at a time. For a fixed i, the subarray ending at j is the previous one plus nums[j]. If it has no repeats, the only thing to check is whether nums[j] already occurs in the previous one.
    • Stop at the first repeat. If nums[j] duplicates a value inside nums[i..j-1], then every longer subarray starting at i contains that same repeat. The inner loop can end right there.

    To check "does this value already occur?" in O(1), keep a set of the values of the current subarray. A fresh, empty set is created for every start index.

    For i = 1 in the example, the window grows as 5, 6, 2, 3, 1 (length 5), and then nums[6] is 5, which is in the set, so the inner loop stops. Starting from i = 0, the window reaches 2, 5, 6 and then stops at the second 2 with length 3.

    The cost of this approach is easy to see: after a repeat is found, the work of building the window is thrown away and the next start index begins from an empty set, even though most of that window is still valid for the next start. Reusing that information is what the faster solutions do. Here the point is to see that a set turns the repeat check from a scan of the window into a single lookup, which is what takes the brute force from cubic to quadratic time.

    Step by step

    1. Start the best length result at 0, which is the right answer for an empty slice.
    2. Loop over start indices i with a three-part for.
    3. Create the set uniqueNums with make(map[int]struct{}) inside that loop, so every start begins with no values.
    4. Loop over end indices j from i, so the one-element subarray is considered first.
    5. Check for a repeat using comma-ok in the if header. On a repeat, break out of the inner loop.
    6. Update the answer with the built-in max and the length j - i + 1. This line runs only when the new element was not a repeat.
    7. Add nums[j] to the set, after the check, so the element is not mistaken for a duplicate of itself.
    8. Return result after both loops.

    The solution in Go

    func longestSubarrayWithoutRepeating(nums []int) int {
    result := 0
    for i := 0; i < len(nums); i++ {
        uniqueNums := make(map[int]struct{})
        for j := i; j < len(nums); j++ {
            if _, exists := uniqueNums[nums[j]]; exists {
                break
            }
            result = max(result, j-i+1)
            uniqueNums[nums[j]] = struct{}{}
        }
    }
    return result
}

    The Go details:

    • The only loop is for. The three-part form init; condition; post is the classic counting loop, and break leaves the innermost loop only.
    • Built-in max. Since Go 1.21, max and min are built in and work on ordered types such as int. In older versions you would write an if.
    • A set as map[int]struct{}. The empty struct carries no data. struct{}{} is a value of that type.
    • Comma-ok. The statement before the semicolon runs first, and exists exists only inside the if.
    • Map per start index. Each outer iteration allocates a new map. The old one is garbage collected, so memory stays at O(n).

    Complexity

    Time: O(n²). The outer loop runs n times and the inner loop at most n - i times, each iteration doing O(1) map work on average. For an input with all different values the total is about n² / 2 steps.

    Space: O(n). The set holds at most the values of one window, never more than n.

    Edge cases and common mistakes

    • Empty slice. No loop runs and the result is 0.
    • One element. [4] gives 1.
    • All equal. [3, 3, 3] gives 1: each window stops at its second element.
    • All different. [1, 2, 3] gives 3.
    • Adding before checking. If nums[j] went into the set first, every element would look like a repeat of itself and the answer would be 0.
    • Sharing one set across start indices. Values from the previous window would stay in the set and cut later windows short.
    • Subarray versus subsequence. The elements must be contiguous. For [1, 2, 1, 3, 4, 2] the answer is 4 ([2, 1, 3, 4]).

    Testing

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