Problem overview
The function longestSubarrayWithoutReapeating(nums: IntArray): 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 consecutive elements, not an arbitrary selection.
For nums = [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 consecutive elements avoids a repeat. The answer is only the length, so the function doesn't need to say which subarray it found.
The lesson's budget is O(n^3) time and, in the statement, O(1) extra space. It is a deliberately slow first solution that checks everything. Faster approaches come in later lessons.
Approach: try every start and grow the subarray
A subarray is determined by its first index i and its last index j. Trying every pair with i <= j covers all candidates. For each pair, the question is whether nums[i..j] has a repeated value, and if not, whether its length j - i + 1 beats the best so far.
Checking each pair from scratch is wasteful, and there is a useful shortcut. Fix i and let j grow one step at a time. Each step adds just one new element, nums[j], to the previous subarray nums[i..j-1]. The earlier subarray had no repeats, otherwise the loop would have stopped earlier, so the new one has a repeat only if nums[j] already occurs in the earlier part. When it does, every longer subarray starting at i contains that same repeat, so the inner loop can stop with break and move to the next i.
With i = 1 in the example, the subarrays grow as [5], [5, 6], [5, 6, 2], [5, 6, 2, 3], [5, 6, 2, 3, 1] with length 5, and then the next element, 5, repeats the first one, so the loop stops. The best length from each start is 3, 5, 5, 5, 4, 3, 2 and 1 for i = 0 to 7, and the maximum is 5.
Step by step
- Create the result. Declare
var result = 0. It holds the longest valid length found so far, and it must be avarbecause it is updated. An empty array leaves it at 0, which is the right answer. - Choose the start. Write
for (i in nums.indices), so every index is tried as the first element. - Choose the end. Inside it, write
for (j in i until nums.size). The range starts ati, because a subarray with one element is valid, and ends at the last index. - Look for a repeat. Save the new value in
val searchValue = nums[j]. The previous subarray isnums[i..j), fromiup to but not includingj, whichnums.copyOfRange(i, j)copies. Its end index is exclusive, so the copy doesn't containnums[j]itself. The callany { it == searchValue }asks whether any element of that copy equals the new value. If so,break. - Record the length. When no repeat was found,
nums[i..j]is valid and hasj - i + 1elements. Update withresult = maxOf(result, j - i + 1). Noelseis needed, becausebreakskips this line. - Return the result after both loops.
The solution in Kotlin
class Solution {
fun longestSubarrayWithoutReapeating(nums: IntArray): Int {
var result = 0
for (i in nums.indices) {
for (j in i until nums.size) {
val searchValue = nums[j]
if (nums.copyOfRange(i, j).any { it == searchValue }) {
break
}
result = maxOf(result, j - i + 1)
}
}
return result
}
}
The Kotlin details worth knowing:
copyOfRange(from, to). It returns a newIntArraywith the elements from indexfromup to, but not including, indexto. Whenj == ithe range is empty, and the copy is an empty array, so the first element of every start passes the check. Iffromwere greater thantoit would throw anIllegalArgumentException, which can't happen here becausej >= i.any { ... }. It takes a lambda.itis the lambda's single parameter, one element of the array.anyreturnstrueas soon as one element satisfies the condition, andfalsefor an empty array.break. It leaves the innermost loop, here thejloop. The outer loop moves to the nexti. It sits in theifbody, outside the lambda.maxOf(a, b). It is a standard function that returns the larger of two values.- The name. The lesson's function and the problem title spell "repeating" as "reapeating". Use the spelling as written, or the code won't match the tests.
Complexity
Time: O(n^3). There are about n^2 / 2 pairs (i, j). For each pair, copyOfRange copies up to n elements and any scans them, so each pair costs O(n). That multiplies to O(n^3). The early break makes typical inputs faster, but an array of all different values never triggers it.
Space. This code allocates a copy in every check, so its extra space is not O(1). Each copy can hold up to n elements and becomes garbage right after the check, so at any moment the extra memory is O(n). The copy is a convenience of the lesson. Scanning the range i until j with a loop would need no copy.
Edge cases and common mistakes
- Empty array. The loops don't run and the result stays 0.
- One element.
[7]gives 1. - All equal.
[1, 1, 1]gives 1: every start can use only its own element. - All different.
[1, 2, 3, 4]gives 4, the whole array. - A repeat that isn't adjacent.
[1, 2, 1, 2, 3]gives 3, from[1, 2, 3]at the end, not 4. - Subarray versus subsequence.
[2, 5, 6, 2, 3, 1, 5, 6]has the distinct values 2, 5, 6, 3 and 1, but the elements must be consecutive, so the answer is 5. - Copying through
j. UsingcopyOfRange(i, j + 1)would includenums[j]and always find a match with itself, giving 0 for every input. - Forgetting the
break. The loop would keep extending a subarray that already has a repeat, and later steps could count one wrongly as valid. - Counting the length wrongly. The length of
nums[i..j]isj - i + 1.
Testing
[2, 5, 6, 2, 3, 1, 5, 6]gives5.[1, 2, 1, 2, 3]gives3.[3, 3, 4, 5]gives3.[-1, 0, -1]gives2.[1, 1, 1]gives1, and[]gives0.