Longest subarray without repeated numbers

Given an array, find the length of the longest subarray which has no repeating numbers.

Input: 
A = {1,2,3,3,4,5}
Output: 
3
Explanation: 
Longest subarray without any repeating elements are {1,2,3} & {3,4,5}.

Thought Process

1. Brute Force

In this approach, you will consider each subarray and then check whether that particular subarray contains no repeating elements or not. Right? So let’s find out how expensive this task would be? The complexity of generating subarray of an array would be O(n2), and when I will generate a particular subarray then I have to check whether the subarray contains unique elements(will use a map for this) or not, which will take O(n) time.

Time Complexity : O(n^3)
Space Complexity : O(n)

2. Sliding Window Solution

Sliding Window Technique is a method for finding subarrays in an array that satisfy given conditions. If you’re new to Sliding Window technique, visit this Sliding Window, it will be helpful for you. In Short words, I can say that maintaining a subset of items as our window, and resizing and moving that window until we find a solution.

We will use two pointers to construct our window. To expand the window, we have to increment the right pointer and to shrink the window we have to increment the left pointer.

We will increment the right pointer by 1 until the property of the subarray is not violated if the property gets violated, we have to shrink the window(means increment the left pointer by 1) till the subarray contains the repeating letters. We have to repeat this step until the value of the right pointer <= array Size.

  • Here, Property means the subarray should contain only the unique elements.

Initially, left and right pointers both are at 0th index.

  1. Add the value of arr[right] into the map.
    • After adding the value, if map[arr[right]] is 1, that is ok.
      Increment the right pointer by 1.
      Update the maxSize of the window variable.
    • After adding the value into map, if map[arr[right]] is 2, it means that our window contains repeating elements. Now, we have to shrink the window from left so that our window always contains the unique elements.
      Increment the left pointer and parallely decrement the value of the map[arr[left]]by 1.
      Do this thing until the value of the map[arr[right]]becomes 1.
  2. Repeat the 1st step, till the right < arraySize

Time Complexity – O(n), where n is the number of integers in the array.
Space Complexity – O(k), where k is the number of distinct integers in the input array. This also means k<=n, because in worst case, the whole array might not have any repeating integers so the entire array will be added to the map.

longest subarray without repeating numbers

Implementation

#include<bits/stdc++.h>;
using namespace std;
int lengthOfLongestSubarray(vector<int>v)
{
    if(v.size()==0)
    {
        return 0;
    }
    map<int,int> mapy;
    int left=0, right=0;
    int max_window=-1;

    for(right=0;right<v.size();right++)
    {
        int num=v[right];
        mapy[num]=mapy[num]+1;
        
        while(left < right && mapy[num] > 1){
           mapy[v[left]]=mapy[v[left]]-1;
           left=left+1;
        }
        //calculating max_length of window
        max_window=max(max_window,right-left+1);
    }
    return max_window;
}
main()
{
    vector<int>v={1,2,3,3,4,5};
    cout<<lengthOfLongestSubarray(v);
}

This post is contributed by Monika Bhasin.