LESSON 268 OF 414 · HASH TABLE

Longest Subarray With At Most K Distinct Integers in Scala: O(n²)

Practice O(n²) Read the full explanation

Given an array of integers, find the longest subarray that contains at most K distinct integers and return its length.

Example

Input: nums = [1, 2, 1, 2, 3], k = 2
Output: 4
Explanation: the subarray nums[0...3] contains 2 distinct values: [1, 2] and is the longest subarray

Note:

Your algorithm should run in at most O(n²) time and use O(n) extra space.

STEP 1 OF 8

Guided

Ctrl + Enter to check

SCALA · HASH TABLE

Longest Subarray With At Most K Distinct Integers in Scala, explained

Problem overview

The method longestSubarray receives an Array[Int] called nums and an Int called K. It returns the length of the longest subarray, a run of consecutive elements, that contains at most K different values. Repeats of a value inside the subarray don't count extra.

For Array(1, 2, 1, 2, 3) and K = 2 the answer is 4. The first four elements, 1, 2, 1, 2, contain only the two distinct values 1 and 2. Adding the fifth element brings in 3, a third distinct value, so no longer valid subarray exists.

The lesson asks for O(n²) time and O(n) extra space. A faster sliding-window solution is the subject of a later lesson.

Approach: extend from every start until there are too many values

Try every index i as the start of a subarray and extend the end index j one step at a time. A hash set holds the distinct values of nums(i..j), and its size is the number of distinct values. After adding nums(j):

if the set has more than K values, stop: extending further can only keep or increase the number of distinct values, so no longer subarray from this start is valid;
otherwise nums(i..j) is valid, so compare its length j - i + 1 with the best so far and move on to j + 1.

There are n starts, and each scans at most n elements with constant-time set operations on average, which gives O(n²). The set is created inside the outer loop, so every start begins with no values.

On the example with K = 2, start 0 collects 1, then 2, then 1 and 2 again, and the set still holds two values, so the length reaches 4. The fifth element adds 3, the set grows to three, and the scan stops. Start 1 reaches 2, 1, 2 for length 3 before 3 breaks it. The overall maximum is 4.

Step by step

Declare answer with var, set to 0. It is the best length found so far and changes later.
Loop over the start index with for (i <- nums.indices). nums.indices runs from 0 to nums.length - 1.
Create the set for this start. Inside the loop, val distinctValues is an empty mutable.HashSet[Int](). It is a val because the name never changes, even though the set grows.
Set up a while loop with a flag. Scala has no break, so declare var j = i and var stop = false, and loop while j < nums.length && !stop.
Add the next element. distinctValues.add(nums(j)). A set ignores a value it already holds, so the size counts distinct values only.
Check the limit. If distinctValues.size > K, set stop = true.
Otherwise count it. In the else, answer = math.max(answer, j - i + 1) and then j += 1 to try a longer subarray. j advances only here, because once stop is set the loop ends before j is used again.
Return answer on its own line after the outer loop. The last expression of a method is its value.

The solution in Scala

class Solution {
    def longestSubarray(nums: Array[Int], K: Int): Int = {
        var answer = 0
        for (i <- nums.indices) {
            val distinctValues = mutable.HashSet[Int]()
            var j = i
            var stop = false
            while (j < nums.length && !stop) {
                distinctValues.add(nums(j))
                if (distinctValues.size > K) {
                    stop = true
                } else {
                    answer = math.max(answer, j - i + 1)
                    j += 1
                }
            }
        }
        answer
    }
}

The Scala details worth a closer look:

The mutable. prefix. mutable.HashSet names the class in scala.collection.mutable. In your own file, that short form needs import scala.collection.mutable first; otherwise the compiler reports "Not found: mutable". The default Set is immutable and has no in-place add.
Parameter name K. It is a capital letter, which Scala allows for a parameter. The name must match exactly, because the lesson's tests call the method with it.
The flag instead of break. A while loop re-evaluates its condition each time, so setting stop ends it at the next check. Because j isn't advanced in that case, the loop leaves with j pointing at the element that broke the limit.
size on a set. The size is the number of elements currently stored, which is the count of distinct values. It is a constant-time call.
math.max. It comes from scala.math and needs no import.

Complexity

Time: O(n²). Each of the n starts scans forward at most to the end of the array, doing constant average-time work per step. With a large K, such as when K is at least the number of distinct values, every start scans to the end, which is about n² / 2 steps in total.

Space: O(n). The set holds at most K + 1 values before the scan stops, which is never more than n. The set from the previous start is discarded.

Edge cases and common mistakes

Empty array. The loop doesn't run and the answer is 0.
K = 0. The first element makes the set size 1, which is above 0, so the scan stops at once from every start. Array(1, 2, 3) with K = 0 gives 0.
Large K. When K is at least the number of distinct values, the whole array is valid. Array(1, 2, 3) with K = 5 gives 3.
Reusing the set. A set declared outside the outer loop keeps values from earlier starts, so the size check would stop too early.
Counting before checking. The answer must be updated only in the else branch. Updating it after adding an element that breaks the limit would report a subarray with K + 1 distinct values.
Counting elements instead of distinct values. A subarray like 1, 2, 1, 2 has four elements but two distinct values. Only the distinct count is limited by K.

Testing

Array(1, 2, 1, 2, 3) with K = 2 gives 4.
Array(1, 2, 3) with K = 0 gives 0.
Array(1, 2, 3) with K = 5 gives 3.
Array() with K = 2 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