LESSON 267 OF 414 · HASH TABLE

Longest Subarray Without Reapeating in Scala: O(n²) with a HashSet

Practice O(n²) Read the full explanation

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^2) time and use O(n) extra space.
(There exist faster solutions which we will discuss in future lessons)

STEP 1 OF 8

Guided

Ctrl + Enter to check

SCALA · HASH TABLE

Longest Subarray Without Reapeating in Scala, explained

Problem overview

The method longestSubarrayWithoutReapeating receives an Array[Int] called nums and returns the length of the longest subarray in which no value appears twice. A subarray is a run of consecutive elements.

For Array(2, 5, 6, 2, 3, 1, 5, 6) the answer is 5. Both 5, 6, 2, 3, 1 (indices 1 to 5) and 6, 2, 3, 1, 5 (indices 2 to 6) have five different values. Any six-element window repeats something, so 5 is the maximum.

For this lesson the budget is O(n²) time and O(n) extra space. Faster solutions exist and come later.

Approach: grow a subarray from every start until it repeats

Fix a starting index i. Extend the subarray one element at a time to the right with an end index j. As long as nums(j) is a value not yet in the subarray, the subarray nums(i..j) is valid and its length is j - i + 1. The first time nums(j) is already in the subarray, stop: every longer subarray from the same start would contain the same repeat, so none of them can be valid.

Repeat this for every start and keep the largest length seen. There are n starts and each one scans up to n elements, so the time is O(n²).

The only question is how to know whether nums(j) is already in the subarray. Scanning the subarray each time would add another factor of n. A hash set of the values in the current subarray answers in constant time on average, which keeps the whole thing at O(n²). The set is created fresh for each start, so it always describes only the subarray beginning at i.

On the example, start i = 0 reaches 2, 5, 6 and then hits the second 2, so its best is 3. Start i = 1 reaches 5, 6, 2, 3, 1 and then hits 5, so its best is 5. Later starts do no better, and the result is 5.

Step by step

Declare result with var, starting at 0. It holds the best length so far, and 0 is the correct answer for an empty array.
Loop over the start index with for (i <- nums.indices). nums.indices is the range 0 until nums.length.
Create a new set per start. Inside the loop, val uniqueNums is an empty scala.collection.mutable.HashSet[Int](). Creating it inside the loop gives every start an empty set.
Replace the inner for with a while. Scala has no break, so the end index is a var j = i and a flag var stop = false controls the loop: while (j < nums.length && !stop).
Check for a repeat. If uniqueNums.contains(nums(j)), set stop = true and the loop ends at its next check. Otherwise take the else branch.
Update the best length. In the else, nums(i..j) is valid, so result = math.max(result, j - i + 1).
Add and advance. Still in the else, call uniqueNums.add(nums(j)) and then j += 1. A while loop never moves j by itself. Adding nums(j) before the check would make every value look like a repeat of itself.
Return result. The last expression of a Scala method is its value, so the method ends with just result.

The solution in Scala

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

The Scala details worth a closer look:

No break. The language has no break statement, so the stop flag is the usual way to leave a loop early. In the duplicate case j isn't advanced, and the flag ends the loop at the next condition check.
Why while and not for. A for over a range can't be stopped by a flag. A while re-evaluates its condition every time, so the flag takes effect.
var versus val. result, j and stop change, so they are var. uniqueNums is a val: the name never moves, while the set's contents change.
math.max. This is scala.math.max, available without an import. For two Int arguments it returns an Int.
The value of the method. A method body is a block, and a block's value is its last expression. The final line result is therefore the return value, with no return keyword.

Complexity

Time: O(n²). The outer loop runs n times. For each start, the inner loop advances at most to the end of the array, and each step does a constant-time set operation on average. When all values are distinct, start i scans n - i elements, which sums to about n² / 2 steps.

Space: O(n). At any moment the set holds the values of one subarray, at most n of them. The old set is discarded when a new start begins.

Edge cases and common mistakes

Empty array. The outer loop doesn't run and the result is 0.
All values equal. Array(7, 7, 7) gives 1: each start adds one element and then meets a repeat.
All values distinct. Array(1, 2, 3) gives 3, the whole array.
Sharing one set across starts. If the set is declared outside the outer loop, values from earlier starts stay in it and later subarrays look like they contain repeats.
Forgetting to advance j. Without j += 1 in the else branch, the loop re-reads the same element, finds it in the set on the next pass and stops, so lengths never exceed 1.
Length off by one. The subarray from i to j inclusive has j - i + 1 elements, not j - i.
Subarray versus subsequence. The elements must be consecutive. Skipping elements isn't allowed.

Testing

Array(2, 5, 6, 2, 3, 1, 5, 6) gives 5.
Array(7, 7, 7) gives 1.
Array(1, 2, 3) gives 3.
Array() 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