New update is available. Click here to update.

Last Updated: 21 Jun, 2021

Difficulty: Moderate

```
Let an array ‘arr’ = [2,2,1,1].
In this example, the array can be split like this [2,2], [1,1] in this
case the first and last occurrence of 2 lies in a first subarray and
similarly first and the last occurrence of 1 lies in a second
subarray.
```

```
The first line contains a single integer ‘T’ denoting the number of
test cases to be run. Then the test cases follow.
The first line of each test case contains a single integer N
denoting the size of an array.
The second line of each test contains ‘N’ space-separated i
integers denoting the elements of the array ‘arr’.
```

```
For each test case, print an integer ‘X’ denoting the maximum number of subarrays in which the array ‘arr’ can be split.
Output for each test case will be printed in a separate line.
```

```
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
```

```
1 <= T <= 100
1 <= N <= 10^3
1 <= arr[i] <= 10^5
Time Limit: 1 sec.
```

The key idea in this problem is storing the first and last occurrence index of every element. So, we can store the first and last index and then iterate over the array, and in each iteration, we check if the maximum index of the last occurrence of all the previous elements of the current subarray is less than or equal to the current index.

We use array hash to store the last occurrence of an element.

**Algorithm**

- Initialize array hash of size equal to maximum element in the array to store the occurrences, initialize it with value -1.
- Initialize answer by 0.
- Iterate over the array and update the occurrence index of every element in the hash array.
- Initialize variable maxIndex with -1.
- Update maxIndex with maximum value of ‘MaxIndex’ and ‘HASH[Arr[i]]’ each time.
- If maxIndex becomes equal to the current index, then increment the answer by 1.

- Return ‘ANSWER’ .

SIMILAR PROBLEMS

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022

Difficulty: Hard

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Popular Interview Problems: