Problem overview
The method longestSubarrayWithoutReapeating receives an Array[Int] named nums and returns the length of the longest subarray in which no value appears twice. A subarray is a run of consecutive elements. Unlike a subsequence, it can't skip elements. (The method name keeps the spelling "Reapeating" from the lesson; use it exactly as written.)
For Array(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 distinct values, and no run of six elements has all different values. The statement allows O(n^3) time, a signal that the brute force is expected.
Approach: try every start and every end
A subarray is fixed by its first index i and its last index j. The brute force tries every i, extends j to the right one element at a time, and checks whether the new element already occurs in the part of the subarray before it.
Two observations keep this simple and fast enough:
- Only the new element
nums(j)can create a repeat, because the shorter subarraynums[i..j)was already valid when it was accepted. So each step has to check one value against the earlier part, not the whole subarray against itself. - Once
nums(j)repeats a value inside the subarray, every longer subarray starting aticontains the same repeat. The search for thisican stop right there.
The cost: there are about n^2 / 2 pairs (i, j), and checking each one scans up to n elements, hence O(n^3). A later lesson replaces the scan with a set and then removes the restart for each i.
Step by step
- The answer so far. Declare
var result = 0. It holds the longest valid length found. An empty array correctly gives 0, and any real subarray replaces it. - Every first element. Loop with
for (i <- nums.indices). - Extend the end. Scala has no
breakin the language, so the inner loop is awhilecontrolled by a flag. Declarevar j = iandvar stop = false, and loop whilej < nums.length && !stop. Settingstoptotrueends the loop at the next check, which is what abreakwould do. - Check the new element. Read
nums(j)intoval searchValueand testnums.slice(i, j).contains(searchValue).slice(i, j)is the previous subarray, fromiup to but not includingj, so it doesn't containnums(j)itself. If the value is there, setstoptotrue. - Otherwise accept it. In the
elsebranch the subarraynums[i..j]has no repeats, and its length isj - i + 1. Updateresultwithmath.max(result, j - i + 1), then add 1 toj. Awhileloop doesn't movejfor you, so the increment has to be written. In the duplicate case no increment is needed because the loop is about to end. - Return. After the loops,
resultis the last expression and the method's value.
The solution in Scala
class Solution {
def longestSubarrayWithoutReapeating(nums: Array[Int]): Int = {
var result = 0
for (i <- nums.indices) {
var j = i
var stop = false
while (j < nums.length && !stop) {
val searchValue = nums(j)
if (nums.slice(i, j).contains(searchValue)) {
stop = true
} else {
result = math.max(result, j - i + 1)
j += 1
}
}
}
result
}
}
Scala details:
slice(from, until). It returns a new array with the elements from indexfromup to but not includinguntil.nums.slice(3, 3)is empty, which is why the first element of each start, wherej == i, is always accepted.- Slices are copies. Each
slicecall builds a new array of up tonelements, thencontainsscans it. That is acceptable at this size and matches theO(n^3)budget; the temporary arrays are discarded right away. varinside the loop.jandstopare declared inside theforbody, so everyistarts with fresh values.resultlives outside so it survives all iterations.math.max. It takes two numbers and returns the larger one. It is available without an import.- No
return. The bareresultis the value of the method body.
Complexity
Time: O(n^3). There are up to n starting indices, up to n end positions for each, and each end position does a slice and a contains of up to n elements. In practice the stop flag cuts each start short as soon as a repeat appears, but an input with all different values never triggers it, so the worst case is the full n^3.
Space. Besides the integers, each slice creates a temporary array of up to n elements, which is thrown away on the next step. Strictly, that makes the memory in use at one moment O(n), not O(1); the lesson accepts it for simplicity.
Edge cases and common mistakes
- Empty array. The outer loop doesn't run, and the result stays 0.
- All the same.
Array(7, 7, 7)returns 1. - All different.
Array(1, 2, 3)returns 3. - Forgetting
j += 1. With awhileloop, the loop never ends, becausejstays the same and the flag never changes. - Slicing up to
j + 1. That includesnums(j)in the part being searched, so every element appears to repeat itself. - Not stopping at a repeat. Without
stop, the loop would continue past the duplicate, and later positions could count a subarray that contains the repeat. - Subarray versus subsequence. Elements must be next to each other.
2, 5, 6, 3, 1skips the second 2, so it is not a subarray of the example.
Testing
Array(2, 5, 6, 2, 3, 1, 5, 6)gives5.Array(7, 7, 7)gives1.Array(1, 2, 3)gives3.Array()gives0.
