Problem overview
You get an IntArray called nums and must return the length of the longest subarray in which no value appears twice. A subarray is a run of neighbouring elements, so you can't skip over elements the way you can in a subsequence.
For [2, 5, 6, 2, 3, 1, 5, 6] the answer is 5. The subarray [5, 6, 2, 3, 1] has five different values, and so does [6, 2, 3, 1, 5]. No run of six elements is free of repeats, because any six neighbours in this array contain some value twice.
The lesson asks for O(n) time and O(n) extra space.
Approach
The brute force tries every start index, walks right until a value repeats and records the length. That costs O(n^2) in the worst case, because each start may walk far to the right again.
The faster idea is a sliding window that never moves backwards:
iis the left edge of the window.jis the index of the next element that might join the window on the right.- A
HashSetholds exactly the values inside the window, so asking "is this value already in the window?" takes constant time on average.
Suppose the window starting at i has grown as far as it can. When the left edge moves to i + 1, the elements from i + 1 up to j - 1 are still free of repeats, since they were already in the window. So j doesn't need to go back to i + 1. It continues from where it stopped. Each index enters the window once and leaves it once, which makes the total work linear.
Step by step
- The set.
uniqueNumsis aHashSet<Int>that holds the current window's values. It is avalbecause the variable always points to the same set; the set's contents still change withaddandremove. - The best length.
resultstarts at 0, which is also the right answer for an empty array. It is avarbecause it gets replaced whenever a longer window turns up. - The right edge.
jis declared before the loop, not inside it. If it were reset for eachi, the scan would repeat work and lose the linear running time. - The left edge. The
forloop overnums.indicesmakes each index the start of a window in turn. - Grow the window. The
whileloop continues as long asjis inside the array andnums[j]is not yet in the set. The order of the two conditions matters: with&&, Kotlin stops at the first false one, sonums[j]is never read whenjequalsnums.size. - Take the element. Inside the loop,
nums[j]is added to the set andjmoves on by one. - Record the length. When the loop stops, the window covers
iup to but not includingj, and its length isj - i, the same asuniqueNums.size.maxOfkeeps the larger of the old best and this length. - Slide the left edge. Before
iadvances,nums[i]is removed from the set, since the next window no longer contains it. Nothing else changes. - Return. After every start has been tried,
resultholds the answer.
The solution in Kotlin
class Solution {
fun longestSubarrayWithoutReapeating(nums: IntArray): Int {
val uniqueNums = HashSet<Int>()
var result = 0
var j = 0
for (i in nums.indices) {
while (j < nums.size && nums[j] !in uniqueNums) {
uniqueNums.add(nums[j])
++j
}
result = maxOf(result, uniqueNums.size)
uniqueNums.remove(nums[i])
}
return result
}
}
A few Kotlin details:
HashSetis available without an import. Kotlin'sHashSetis the JVM'sjava.util.HashSetunder another name.x !in setis the same as!set.contains(x). Theinoperator callscontains.- The element type is
Int, and the set stores boxed integers behind the scenes. For this problem the cost is irrelevant, and equal values compare as equal. nums.indicesis the range0 until nums.size, so an empty array runs the loop zero times and the function returns 0.++jandj++behave the same here because the result of the expression is not used.
Complexity
Time: O(n). The index j only ever increases, so the inner while loop runs at most n times in total over the whole run, not n times per iteration of the for loop. Each element is added to the set once and removed once, and each of those operations takes constant time on average.
Space: O(n). In the worst case, when every value is different, the set holds all n values at once.
Edge cases and common mistakes
- Empty array. The loop never runs and
resultstays 0. - All values equal. For
[7, 7, 7]every window has length 1, so the answer is 1. - All values different. The first window grows to the end of the array and the answer is
nums.size. - Subarray versus subsequence. Values must be neighbours. Picking
2, 5, 6, 3, 1out of the example by skipping the second 2 is not allowed. - Resetting
jinside the loop. This gives correct answers but brings back the quadratic running time. - Forgetting to remove
nums[i]. The set would keep a value that has left the window and block a legitimate extension later. - Swapping the
whileconditions. Writingnums[j] !in uniqueNums && j < nums.sizereads past the end of the array on the last step and throwsArrayIndexOutOfBoundsException.
Testing
[2, 5, 6, 2, 3, 1, 5, 6]returns 5.[]returns 0.[7, 7, 7]returns 1.