Problem overview
The function longestSubarrayWithoutRepeating receives a slice nums of integers and returns the length of the longest contiguous subarray in which no value appears twice.
In the example, nums = []int{2, 5, 6, 2, 3, 1, 5, 6}. The subarray [5, 6, 2, 3, 1] has five distinct values, and so does [6, 2, 3, 1, 5]. Nothing longer exists, because any window of six elements would have to contain a repeated value. The answer is 5.
The statement asks for O(n) time and O(n) extra space.
Approach: a window that only grows to the right
The brute-force solution picks every start, extends the subarray until a value repeats, and records the length. Each start can scan the whole rest of the slice, so it costs O(n²).
The waste is in the repetition. Suppose the best window starting at i ends just before index j. The elements from i + 1 to j - 1 are still distinct when the start moves to i + 1, because a subarray of a repeat-free subarray is repeat-free. So the next window doesn't need to be rebuilt: it already covers i + 1 to j - 1, and only needs to grow further from j.
That gives the shape of the solution:
- keep a set of the values currently in the window;
- for each start
i, pushjforward whilenums[j]isn't in the set, adding each value; - when it stops, the window holds the longest repeat-free subarray starting at
i, and its size is the length of the set; - remove
nums[i]from the set and move toi + 1, leavingjwhere it is.
Since j never moves backwards, each index is added to the set once and removed once. The total work is O(n).
The trace for the example:
i = 0: the window grows over indices 0 to 2 (values 2, 5, 6) and stops at index 3, because 2 is already in the set. Size 3.i = 1: 2 was removed withnums[0], so the window grows over indices 1 to 5 (5, 6, 2, 3, 1) and stops at index 6, where 5 repeats. Size 5.i = 2: after removing the 5, index 6 is allowed, so the window is indices 2 to 6, size 5. It stops at index 7, where 6 repeats.- The later starts give sizes 5, 4, 3, 2 and 1, so the best is 5.
Step by step
- Create the set
uniqueNums. Go has no set type, so amap[int]struct{}stands in: only the keys matter, and the empty structstruct{}as value takes no memory. - Declare
resultas 0, the best length found so far. An empty slice gives 0. - Declare
jas 0, the index of the next element to add. It is declared before the loop overiso that it keeps its value wheniadvances. - Loop over
i, every possible start of the window. - Grow the window with
for j < len(nums). Inside it, look upnums[j]in the set. The two-value lookup_, exists := uniqueNums[nums[j]]reports presence, and writing it in theifstatement's short form keepsexistslocal to thatif. If it exists,break. - Add the new value otherwise: store
struct{}{}undernums[j]and incrementj. - Record the length. The window holds the values at indices
itoj - 1, so its length isj - i, which equalslen(uniqueNums). Take the larger of that andresultwith the built-inmax. - Remove
nums[i]withdeletebefore the next start. It is always in the set at this point: if the window was empty, the inner loop added at leastnums[i]. - Return
resultafter all starts.
The solution in Go
func longestSubarrayWithoutRepeating(nums []int) int {
uniqueNums := make(map[int]struct{})
result := 0
j := 0
for i := 0; i < len(nums); i++ {
for j < len(nums) {
if _, exists := uniqueNums[nums[j]]; exists {
break
}
uniqueNums[nums[j]] = struct{}{}
j++
}
result = max(result, len(uniqueNums))
delete(uniqueNums, nums[i])
}
return result
}
The Go details worth knowing:
- The set is a map.
struct{}is the type with no fields, andstruct{}{}is its only value. Amap[int]boolwould also work, but then reading a missing key givesfalse, which hides the difference between "absent" and "stored as false". Withstruct{}you always test presence with the two-value lookup. - The comma-ok lookup.
v, ok := m[key]returns the stored value and whether the key exists. Here the value is useless, so it is discarded with the blank identifier_. The lookup can't be written inside aforcondition, which is why it sits in anif. - No
while.for j < len(nums)is Go's while loop. Thebreakleaves only that inner loop, not the outer one. deleteis built in. It works on a map and a key, and does nothing when the key is absent.lenon a map gives the number of keys, which is whylen(uniqueNums)equals the window length.
Complexity
Time: O(n). The outer loop runs n times. j goes from 0 to at most n and never decreases, so across the whole run the inner loop performs at most n successful steps plus one failed check per start. Map operations take constant time on average.
Space: O(n). In the worst case, when all values are distinct, the set holds every element.
Edge cases and common mistakes
- Empty slice. The loops never run and the result is 0.
- All values equal.
nums = []int{7, 7, 7}returns 1. For each start, the window can hold only the start value. - All values distinct.
nums = []int{1, 2, 3}returns 3, taken ati = 0whenjreaches the end. - A repeat that is not adjacent.
nums = []int{1, 2, 1, 3}returns 3, from the window[2, 1, 3]. Comparing only neighbours would miss that 1 repeats. - Forgetting to delete
nums[i]. The set would keep values that left the window, and later windows would stop too early. - Rebuilding the window for every start. Resetting
jtoiand clearing the set gives correct answers, but the solution becomesO(n²). - Measuring the length as
j - i + 1. When the inner loop stops,jpoints at the first element not in the window, so the length isj - i. - Confusing a subarray with a subsequence. A subarray is contiguous, so skipping elements isn't allowed.
Testing
nums = []int{2, 5, 6, 2, 3, 1, 5, 6}gives 5.nums = []int{}gives 0.nums = []int{7, 7, 7}gives 1.nums = []int{1, 2, 3}gives 3.nums = []int{1, 2, 1, 3}gives 3.