Start learning free

LESSON 196 OF 347 · NESTED LOOPS & BRUTE FORCE

Longest Subarray Without Repeating in C#: O(n^3) Brute Force

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


STEP 1 OF 6
    Ctrl + Enter to check

    C# · NESTED LOOPS & BRUTE FORCE

    Longest Subarray Without Reapeating in C#, explained

    Problem overview

    The method LongestSubarrayWithoutReapeating(int[] nums) returns the length of the longest subarray in which no integer appears twice. A subarray is a run of consecutive elements, so {5, 6, 2} is a subarray of {2, 5, 6, 2, 3} but {2, 6, 3} is not. (The method name keeps the lesson's spelling, "Reapeating", so use it exactly as written.)

    For nums = {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 distinct values, and no run of six elements is free of repeats.

    Approach: try every start, extend until a repeat

    The lesson asks for O(n^3) time and O(1) extra space. This is the slowest reasonable approach, and later lessons on the same problem make it faster.

    Pick every possible start i. For each start, grow the subarray one element at a time by moving the end j to the right. When a new element nums[j] is added, the subarray nums[i..j-1] before it had no repeats, so the only possible new repeat is nums[j] itself. Check whether that value already occurs in the earlier part. If it does, stop extending: every longer subarray from the same start would contain that repeat too. If it doesn't, the subarray nums[i..j] is valid, and its length is j - i + 1.

    The cost explains the cubic bound. There are about n^2 pairs (i, j), and each does a check that can walk through up to n earlier elements: n^2 × n = n^3.

    Two later ideas shrink this cost. Remembering the values of the current subarray in a hash set makes each check constant time, and sliding the start forward only as far as needed avoids restarting from scratch for every i. Neither is needed here; the lesson focuses on the exhaustive search and on getting its loops and boundaries right.

    Step by step

    1. Start with result = 0. It's the best length found so far. An empty array leaves it at 0, which is the right answer.
    2. Loop over the start i. It runs from 0 while i < nums.Length. Using < keeps i on valid indices.
    3. Loop over the end j. It starts at i, so the one-element subarray nums[i..i] is the first one examined.
    4. Check for a repeat. Copy nums[j] into int searchValue. The earlier part of the subarray is nums.Skip(i).Take(j - i): Skip(i) drops the first i elements and Take(j - i) keeps the next j - i, which stops just before nums[j]. Then Any(value => value == searchValue) asks whether any element equals the new value. On a repeat, break out of the inner loop.
    5. Record the length. If there was no repeat, set result to Math.Max(result, j - i + 1). No else is needed: after a break this line is skipped.
    6. Return result once every start has been tried.

    The solution in C#

    class Solution {

    public int LongestSubarrayWithoutReapeating(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.Length; ++i) {
            for (int j = i; j < nums.Length; ++j) {
                int searchValue = nums[j];
                if (nums.Skip(i).Take(j - i).Any(value => value == searchValue)) {
                    break;
                }
                result = Math.Max(result, j - i + 1);
            }
        }
        return result;
    }
}

    The C# details:

    • LINQ. Skip, Take and Any are extension methods from the System.Linq namespace. They work on any sequence, including arrays, and produce lazily evaluated results rather than copying the array.
    • The lambda. value => value == searchValue is a small anonymous function. Any calls it for each element until one returns true. The lambda uses searchValue, a variable from the surrounding method, which C# lets you capture.
    • Take(0) is fine. When j == i, the earlier part is empty, so Any returns false and the single element counts as valid.
    • break only leaves the inner loop. The outer loop then moves on to the next start.
    • No copies of the array. A subarray is described by the two indices i and j, so the code never builds new arrays to hold subarrays.

    Complexity

    Time: O(n^3). The two loops visit up to about n^2 / 2 pairs, and the repeat check for a pair walks the subarray before nums[j], which has up to n elements. The worst case is an array with all distinct values, where no break ever fires.

    Space: O(1) extra. The code stores a few integers. The LINQ calls create small helper objects, but their size doesn't grow with the input.

    Edge cases and common mistakes

    • Empty array. The loops never run, and the result stays 0.
    • All values equal. {7, 7, 7} gives 1. Each start admits only itself before the next element repeats it.
    • No repeats at all. {1, 2, 3} gives 3, the whole array.
    • Forgetting the break. Without it, the loop would skip the length update for the repeated element but keep extending, then count longer subarrays that contain the repeat. The answer could be too big.
    • Off-by-one in Take. Take(j - i + 1) would include nums[j] itself, so every check would find a match and every answer would be 0.
    • Length of the subarray. The length of nums[i..j] is j - i + 1, not j - i.
    • Confusing subarray with subsequence. The elements must be consecutive.

    Testing

    • {2, 5, 6, 2, 3, 1, 5, 6} gives 5.
    • {7, 7, 7} gives 1.
    • {1, 2, 3} gives 3.
    • An empty array 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