LESSON 314 OF 414 · SLIDING WINDOW

Longest Subarray Without Repeating in Scala: O(n) Sliding Window

Given an input array of integers, find the length of the longest subarray without repeating 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) time and use O(n) extra space

STEP 1 OF 9

Guided

Ctrl + Enter to check

SCALA · SLIDING WINDOW

Longest Subarray Without Reapeating in Scala, explained

Problem overview

The method longestSubarrayWithoutReapeating receives an Array[Int] and returns the length of the longest contiguous subarray in which no value appears twice. In [2, 5, 6, 2, 3, 1, 5, 6] the subarray [5, 6, 2, 3, 1] has five different values, and so does [6, 2, 3, 1, 5]. Nothing longer exists, because any six consecutive elements contain a repeat, so the answer is 5.

Approach: a window that never moves backward

The simple solution tries every start index and extends to the right until it meets a repeat. That costs O(n²) in the worst case, because the extension restarts from scratch for each start.

The faster idea reuses the work. Suppose the window [i, j) (from i up to but not including j) has no repeats and j can't grow any further. When the start moves to i + 1, the elements from i + 1 to j - 1 are still distinct, so the end j doesn't need to go back. It only moves forward. Both pointers travel across the array once, and a set holds the values currently in the window so that "is this a repeat?" takes constant time.

On the example, the windows found for each start index are:

i	j when growth stops	window	size
0	3	`[2, 5, 6]`	3
1	6	`[5, 6, 2, 3, 1]`	5
2	7	`[6, 2, 3, 1, 5]`	5
3	8	`[2, 3, 1, 5, 6]`	5
4	8	`[3, 1, 5, 6]`	4

At i = 0, growth stops at j = 3 because nums(3) is a 2, which is already in the window. Notice that j never decreases from row to row.

The invariant behind the code

Two facts hold at the start of every iteration of the outer loop, and the code is correct because it keeps them true:

the set contains exactly the values nums(i) to nums(j - 1);
those values are all different.

The inner loop preserves both: it only adds a value after checking that the set doesn't contain it. When it stops, either j is at the end of the array or nums(j) is a repeat of something in the window, so the window can't be extended with the next element. That makes the window the longest repeat-free subarray that starts at i, and taking the maximum over all i gives the answer.

Step by step

Create the set. Declare uniqueNums as a val holding an empty scala.collection.mutable.HashSet[Int](). Scala's default Set is immutable, so the mutable one is named in full. It stores the values of the current window.
Declare result as a var starting at 0. It holds the best length found so far.
Declare j as a var starting at 0, before the loop. It is the index of the next element to try. Declaring it outside the loop is what keeps it from moving back.
Loop over each start index with for (i <- nums.indices).
Grow the window. A while loop continues as long as j < nums.length and !uniqueNums.contains(nums(j)). The bounds check comes first, so nums(j) is never read past the end.
Take the element. Inside that loop, call uniqueNums.add(nums(j)) and then j += 1. Scala has no ++.
Record the size. When growth stops, the set holds exactly nums[i..j-1], so its size is j - i. Update result with math.max(result, uniqueNums.size).
Drop the start. Before moving to i + 1, call uniqueNums.remove(nums(i)). The next window starts one position later, and j stays where it is.
Return result as the last expression of the method.

The solution in Scala

class Solution {
    def longestSubarrayWithoutReapeating(nums: Array[Int]): Int = {
        val uniqueNums = scala.collection.mutable.HashSet[Int]()
        var result = 0
        var j = 0
        for (i <- nums.indices) {
            while (j < nums.length && !uniqueNums.contains(nums(j))) {
                uniqueNums.add(nums(j))
                j += 1
            }
            result = math.max(result, uniqueNums.size)
            uniqueNums.remove(nums(i))
        }
        result
    }
}

The Scala details worth a closer look:

Mutable versus immutable sets. Set(1, 2) + 3 builds a new set and leaves the original alone. The code needs a set it can change in place, and that is scala.collection.mutable.HashSet. Its add returns true when the value was new, and its remove returns true when the value was present. The code ignores both results.
Why remove(nums(i)) always finds its value. At the start of iteration i the set holds nums[i..j-1]. If that range is empty (j == i), the inner loop adds nums(i) first, since the set doesn't contain it. So the value being removed is always present.
Short-circuit &&. If j < nums.length is false, the second operand isn't evaluated, which protects the array access.
No return keyword. The final line result is the method's value.

Complexity

Time: O(n). The outer loop runs n times. The inner loop advances j by one each time it runs, and j never decreases and never passes n, so the inner loop's total work across the whole call is at most n iterations. Set operations take constant time on average.

Space: O(n). The set can hold every element when all values are distinct.

Edge cases and common mistakes

Empty array. The loop doesn't run and the result stays 0.
One element. [7] returns 1.
All equal. [1, 1, 1, 1] returns 1: each window grows by one element and stops.
All distinct. [1, 2, 3, 4] returns 4: the first window reaches the end of the array.
A repeat that isn't adjacent. [1, 2, 1, 3, 2] returns 3.
Forgetting to remove nums(i). The set would still contain values that are no longer in the window, and later windows would stop too early.
Resetting j to i on every iteration. The answer stays correct, but the time becomes O(n²).
Reading nums(j) before checking j < nums.length. Swapping the two conditions throws ArrayIndexOutOfBoundsException when the window reaches the end.

Testing

nums = [2, 5, 6, 2, 3, 1, 5, 6] gives 5.
nums = [1, 2, 1, 3, 2] gives 3.
nums = [1, 1, 1, 1] gives 1.
nums = [1, 2, 3, 4] gives 4.
nums = [] gives 0.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free