Split Array Into Maximum Subarrays

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
AmazonAdobeJosh Technology Group

Problem statement

You have given an integer array/list ‘arr’ of size ‘N’. You have to split the array into the maximum number of subarrays such that the first and last occurrence of every distinct element lies in a single subarray.

You are required to return the number of maximum subarrays in which the array can be split.

An array ‘C’ is a subarray of array ‘D’ if ‘C’ can be obtained from ‘D’ by deletion of several elements from the beginning and several elements from the end.

For Example: 
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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
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’.
Output Format: 
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.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints: 
1 <= T <= 100
1 <= N <= 10^3
1 <= arr[i] <= 10^5

Time Limit: 1 sec.
Sample Input 1:
2
4
2 2 3 3
5
1 2 1 2 4
Sample Output 1:
2
2
Explanation For Sample Output 1:
In test case 1:
Given 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. 

In test case 2:
Given array can be split like this [1,2,1,2], [4] in this the first and 
last occurrence of 2 and 1 lie in a first subarray and similarly first 
and the last occurrence of 4 lies in a second subarray.
Sample Input 2:
2
5
1 2 3 4 5
2
3 3
Sample Output 2:
5
1
Explanation For Sample Output 2:
 In test case 1:
 The given array can be split like this [1],[2],[3],[4],[5] in this first 
 and last occurrence of every element in the array lying in the 
 separate subarray. 

 In test case 2:
 The given array can be split like this [3,3] in this first and last 
 occurrence of 3 will lie in one subarray.
Hint

Try storing indices of the last occurrence of every element.

Approaches (1)
Iterative

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

 

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

O(N), where N is the size of an array. 

 

We are iterating over an array having ‘N’ elements once, so there will be N operations inside it, which will give runtime complexity of O(N).

Space Complexity

O(N), where N is the number of elements in the array.

 

The space complexity due to the hashmap will be O(N). 

Code Solution
(100% EXP penalty)
Split Array Into Maximum Subarrays
Full screen
Console