LESSON 243 OF 347 · HASH TABLE

Longest Subarray Without Repeating in C#: O(n^2) with a HashSet

Practice O(n²) 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

Guided

Ctrl + Enter to check

C# · HASH TABLE

Longest Subarray Without Reapeating in C#, explained

Problem overview

The method LongestSubarrayWithoutReapeating receives an int[] nums and returns the length of the longest subarray in which no integer appears twice. (The lesson spells the name with "Reapeating"; use exactly that spelling in code.) A subarray is a block of consecutive elements.

For [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 different values, and no six consecutive elements are all different.

For this lesson the algorithm may take O(n²) time and O(n) extra space. The statement notes that faster solutions exist.

Approach: try every start, grow until a repeat

Every subarray has a first element. For each possible start i, extend the subarray one element at a time to the right, with end index j. As long as the new element has not appeared in the subarray, the subarray is valid and its length j - i + 1 is a candidate for the answer. The moment the new element is already inside, stop extending: every longer subarray from the same start contains that repeat too.

The only question inside the inner loop is "have I seen nums[j] in this subarray?". Scanning the subarray each time would add another factor of n. A HashSet<int> answers it in constant time on average, so the work stays at one set operation per pair (i, j). There are about n²/2 pairs, so the total is O(n²).

The faster approach slides a window and never restarts from scratch, which brings the time down to O(n). This lesson stays with the simpler double loop.

Breaking early also has a payoff in practice. When repeats are frequent, each inner loop stops after a few steps, so the program is much faster than the worst case. The O(n²) bound only describes inputs with long runs of distinct values.

Step by step

Create result, an int starting at 0. It is the best length so far. An empty array correctly returns 0.
Loop i from 0 while i < nums.Length. Each i is a possible first element. Using < stops at the last valid index.
Create a fresh HashSet<int> called uniqueNums inside this loop. It holds the values of the current subarray. Creating it per start makes every new i begin with an empty set.
Loop j from i while j < nums.Length. Starting j at i tests the one-element subarray first.
If uniqueNums.Contains(nums[j]), break. The set holds exactly nums[i] up to nums[j - 1], so a hit means nums[j] repeats inside the subarray.
Otherwise update result. The subarray nums[i..j] is valid, so Math.Max(result, j - i + 1) keeps the larger length. No else is needed, because the break skips this line.
Add nums[j] to the set. The order matters: if you add it before the check, every value looks like a repeat of itself.
Return result after both loops finish.

The solution in C#

class Solution {

    public int LongestSubarrayWithoutReapeating(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.Length; ++i) {
            HashSet<int> uniqueNums = new HashSet<int>();
            for (int j = i; j < nums.Length; ++j) {
                if (uniqueNums.Contains(nums[j])) {
                    break;
                }
                result = Math.Max(result, j - i + 1);
                uniqueNums.Add(nums[j]);
            }
        }
        return result;
    }
}

Trace the start i = 1 on the example. The set starts empty. 5, 6, 2, 3 and 1 are each new, so the length grows to 5. The next element, 5, is in the set, so the loop breaks. The start i = 0 stops earlier, at the second 2, with length 3.

C# details:

break leaves only the inner loop. The outer loop then moves on to the next i, which is the intended behaviour.
++j versus j++. In a for header they behave the same, because the value of the expression is not used.
Math.Max is in the System namespace and returns the larger of two int values. HashSet<T> needs System.Collections.Generic.
nums.Length is a property. Arrays use Length, with no parentheses, while a List<T> uses Count.

Complexity

Time: O(n²). For each of the n starts, the inner loop runs at most n - i times, with constant-time set operations. The sum is at most n(n+1)/2 steps. With all-distinct input the inner loop never breaks early, which is the worst case.

Space: O(n). The set holds at most one subarray's values. Only one set exists at a time, because each outer iteration creates a new one and the old one is discarded.

Edge cases and common mistakes

Empty array. The outer loop never runs, so the answer is 0.
All values equal. [7, 7, 7] gives 1: each start accepts one element and breaks at the next.
All values different. The answer is the whole array length.
Declaring the set outside the outer loop. Values from earlier starts stay in the set, and later subarrays are wrongly cut short.
Confusing subarray and subsequence. A subarray is contiguous. In [1, 2, 1, 3] the answer is 3 ([2, 1, 3]). Skipping the second 1 to get [1, 2, 3] would also have three distinct values, but it is not contiguous, so it is a subsequence and not a valid choice.
Off-by-one in the length. The length of nums[i..j], both ends included, is j - i + 1.

Testing

[2, 5, 6, 2, 3, 1, 5, 6] gives 5.
[7, 7, 7] gives 1.
[] gives 0.

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

Start learning free