## 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.

### 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.

## Sliding window concept: Never let it slide off your brain

A problem based on sliding window patterns regularly appears in interviews like Facebook, Google, and Amazon. This pattern is simple to understand and apply, however, most of the times candidates do not understand in the first place that the problem is a sliding window problem.

How to identify a sliding window problem?

The first hint is in the problem statement, usually, a sliding window problem asks us to find a subarray or a substring. It means the elements are contiguous, and substring/subarray can be the window we are looking for. So, the idea is to think of a sliding window pattern whenever you hear find a subarray or substring in a given array.
The second hint confirms that the problem is actually to be solved using a sliding window pattern. In the problem, you would be asked to find a substring or subarray with a certain property, for example, find the longest substring with nonrepeating characters.

To summarize, if you are asked to find subarray or substring with a specific property (longest/shortest/whatever), think of sliding window pattern.
Now that we have identified the problem to be a sliding window problem, let’s see how to solve it. There are two kinds of problems, first one has a fixed-length window, for example, find the maximum in a window of K in an array; second are the problems where a window is variable-sized. Problems in the second category are difficult and commonly asked in the interview.

A window has two ends, let’s call them left and right. The window is between these two ends. If the window has a variable size, then the window will expand and shrink.

Always expand the window from the right end and shrink from the left end

When you are solving the problem, initialize left and right as 0, then expand the window by increasing the right. When do we shrink the window or expanding the window? Keep expanding the window until it violates the condition stated in the problem statement. As soon as the violation happens, expansion stops, bookkeeping is done if needed like update the longest variable, etc. We start removing elements from the window from left end until the condition is satisfied again.

Stop when right reaches at the end of the original string. The general pattern of solutions is as follows:

```package AlgorithmsAndMe;

public class SlidingWindowProblems {

public int solve(String s){

/* Step 1. Initialize the window of
zero size, i.e left and right as 0
*/
int left = 0;
int right = 0;

int longest = 0;

//Step 2 : Go on all till right reaches end
while(right < s.length()) {

/* Step 3: Do some bookkeeping to update
the state of the window.
*/

//Step 4: Expand the window
right++;

//Step 5: go on till condition is not valid
while (left < right /* and Condition is invalid */) {

/*Step 6: Do the book keeping to keep
track of optimization requirements */
longest = Math.max(right - left, longest);

/* Step 7: Update the condition. */
/* Step 8: remove the left most element
from the window.
*/
left++;
}
}

return longest;
}
}
```

With this template code, you have to figure out one thing: how would you maintain the state of the window so that we can quickly check if it is valid or not. It varies from problem to problem. Do not sweat too much about it initially, go with the first thing which can work and then later, optimize it.

## Longest substring without repeating character

This problem is available on leetcode as Longest Substring Without Repeating Characters, try it with template provided before going to the solution given below.

Given a string, find the length of the longest substring without repeating characters.

For example, abcabcbb longest string with no repeating characters is abc with length 3.

Hint 1, we are looking for a substring, and hint 2, we are looking for a substring with a specific property (without a repeating character), it means we can use the sliding window approach to solve this problem. In our template, it is important to known when the condition is invalid. To know that a character is repeated, we can use a hashmap, however, a better solution would be a set of character already in the window. Why? Because we do not care about value in the hashmap anyways, all we want to know that a character exists in hashmap, which can be done using set as well without using additional memory for values.

How can we know that condition is invalid? If the new character which comes in the window is already present in the set, then our window violates the no repeating character condition. In that case, we will start removing characters from the left end till a new character can be added to the window. Also, do the bookkeeping to keep track of the longest.

```package AlgorithmsAndMe;

import java.util.HashSet;
import java.util.Set;

public class SlidingWindowProblems {

public int solve(String s){

/* Step 1. Initialize the window of
zero size, i.e left and right as 0
*/
int left = 0;
int right = 0;

int longest = 0;

Set<Character> set = new HashSet<>();
//Step 2 : Go on all till right reaches end
while(right < s.length()) {

/* Window already contains the character
which we want to add, start shrinking
the window.
*/
char c = s.charAt(right);
if(set.contains(c)){
//Step 5: go on till condition is not valid
while (left < right && set.contains(c)) {
/*Step 6: Do the book keeping to keep
track of optimization requirements */
longest = Math.max(right - left, longest);

/* Step 7 and 8: updated condition
remove the left most element
from the window,
*/
set.remove(s.charAt(left));
left++;
}
}

//Step 3 and 4. Add the right character to the set
set.add(c);
right++;
}

return Math.max(right-left, longest);
}
}
```

In this solution, steps 3 and 4 are at the end because how we do the bookkeeping, if we add the right into the set before checking if already exists, it will fail as a set only stores unique elements.

## Longest Substring with At Most 2 Distinct Characters

This problem is asked in Google interview and the problem statement goes like

Given a string, find the longest substring that contains only two unique characters.

For example, given a string abcbbbbcccbdddadacb, the longest substring that contains 2 unique character is bcbbbbcccb.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class SubstringWith2DistinctCharacters {

public int solve(String s){

/* Step 1. Initialize the window of
zero size, i.e left and right as 0
*/
int left = 0;
int right = 0;

int longest = 0;

Map<Character, Integer> map = new HashMap<>();
int distinct = 0;
//Step 2 : Go on all till right reaches end
while(right < s.length()) {

/* Step 3: Do some bookkeeping to update
the state of the window.
*/
char c = s.charAt(right);
if(!map.containsKey(c)){
distinct++;
}
map.put(c, map.getOrDefault(c, 0) + 1);
//Step 4: Expand the window
right++;

//Step 5: go on till condition is not valid
while (left < right && distinct > 2) {

/*Step 6: Do the book keeping to keep
track of optimization requirements */
longest = Math.max(right - left, longest);

/* Step 7: Update the condition. */
map.put(s.charAt(left), map.get(s.charAt(left))-1);

/* We can decrease distinct count only if the character
just removed is not any more in window */
if(map.get(s.charAt(left)) == 0){
distinct--;
}
/* Step 8: remove the left most element
from the window.
*/
left++;
}
}

return Math.max(right - left, longest);
}
}
```

This problem is a straight forward case of a sliding window and perfectly fits in our template. All we had to do is to figure out how to quickly validate the state of the window using a map. Now, can you solve another similar problem called: Longest Substring with At Most K Distinct Characters or a subarray with K different elements or Max Consecutive Ones III

If you are looking for a quick crash course where you can prepare for 80% of your interview in 2 weeks with these pattern-based learning, please reach out to us at [email protected] or book a free demo session.