Start learning free

LESSON 244 OF 348 · HASH TABLE

Longest Subarray Without Repeating Integers in Kotlin: O(n²) with a HashSet

Practice O(n2) Read the full explanation

Given an input array of integers, find the length of the longest subarray without reapeating 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
    Ctrl + Enter to check

    KOTLIN · HASH TABLE

    Longest Subarray Without Reapeating in Kotlin, explained

    Problem overview

    The function longestSubarrayWithoutReapeating receives an IntArray called nums and returns the length of the longest subarray in which no integer appears twice. A subarray is a run of neighbouring elements, so you can't skip over elements.

    In the example, nums = [2, 5, 6, 2, 3, 1, 5, 6]. The run [5, 6, 2, 3, 1] has five different values, and so does [6, 2, 3, 1, 5]. Nothing longer avoids a repeat, so the answer is 5.

    For this lesson the statement allows O(n²) time and asks for O(n) extra space. Faster solutions exist, but this lesson builds the straightforward one first.

    Approach: try every start, grow until a repeat

    Every subarray is fixed by where it starts and where it ends. The idea is to try each start i and, for that start, grow the end j one element at a time, keeping the values seen so far in a HashSet. As long as the next element isn't in the set, the subarray from i to j has no repeats, and its length, j - i + 1, is a candidate for the answer.

    The moment the next element is already in the set, the loop for this start can stop. Any longer subarray from the same start would still contain that repeated pair, so none of them can be valid. This early exit is what makes the set useful: without it you would have to rescan the subarray for every new element, which costs an extra factor of n.

    For the example, start at index 0: the values 2, 5, 6 are new, then the second 2 is found in the set, so the best length from this start is 3. Start at index 1: 5, 6, 2, 3, 1 are all new, then the second 5 stops the loop. That gives length 5. No later start beats it.

    The cost is a pair of nested loops, each running up to n times, so O(n²) time. A single sliding window can do this in linear time, but that is the idea of a later lesson.

    Step by step

    1. Start the answer at 0. result is a var, because it changes whenever a longer subarray appears. It also gives the right answer, 0, for an empty array.
    2. Choose the start. The outer loop, for (i in nums.indices), tries every index. nums.indices is the range 0 until nums.size.
    3. Make a fresh set per start. uniqueNums is created inside the outer loop, so every new start begins with no values from the previous one. It is a val: the variable stays put, and the set's contents change.
    4. Choose the end. The inner loop, for (j in i until nums.size), extends the subarray one element at a time. until excludes the upper bound, so j never leaves the array.
    5. Stop at a repeat. If uniqueNums already contains nums[j], break leaves the inner loop.
    6. Record the length. Otherwise nums[i..j] has no repeats, and maxOf(result, j - i + 1) keeps the larger of the old best and the new length.
    7. Remember the element. Add nums[j] to the set so the next j can see it. This must come after the check; adding first would make every element a repeat of itself.
    8. Return result once every start has been tried.

    The solution in Kotlin

    class Solution {
    fun longestSubarrayWithoutReapeating(nums: IntArray): Int {
        var result = 0
        for (i in nums.indices) {
            val uniqueNums = HashSet<Int>()
            for (j in i until nums.size) {
                if (uniqueNums.contains(nums[j])) {
                    break
                }
                result = maxOf(result, j - i + 1)
                uniqueNums.add(nums[j])
            }
        }
        return result
    }
}

    Kotlin details:

    • i until nums.size is a half-open range: it includes i and excludes nums.size. When i is the last index, the range holds just that index.
    • break leaves only the innermost loop, which is what is wanted here: the outer loop moves on to the next start.
    • maxOf(a, b) is a standard function that returns the larger of two values. No if or else is needed, since the break already skips this line when there is a repeat.
    • Both indices are Int. For arrays small enough to fit in memory, j - i + 1 can't overflow.

    Complexity

    Time is O(n²): for each of the n starts, the inner loop runs at most n times, and each set operation is constant on average. Space is O(n): the set holds at most one entry per element of the subarray, and a new set replaces the old one for each start.

    Edge cases and common mistakes

    • Empty array. The loops don't run, and the result is 0.
    • All elements equal. For [7, 7, 7], every start breaks on its second element, so the answer is 1.
    • All elements different. The inner loop never breaks, and the answer is nums.size.
    • Reusing one set across starts. Declaring uniqueNums outside the outer loop would carry old values into new subarrays and give wrong answers.
    • Confusing subarray with subsequence. Elements must be adjacent. In the example, picking 2, 5, 6, 3, 1 by skipping the second 2 isn't allowed.

    Testing

    • [2, 5, 6, 2, 3, 1, 5, 6] returns 5.
    • [] returns 0.
    • [7, 7, 7] returns 1.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free