Subarray with distinct integers

Easy
0/40
Average time to solve is 10m
profile
Contributed by
47 upvotes
Asked in companies
OlaCapegemini Consulting India Private LimitedVMware Software India Pvt Ltd

Problem statement

You are given an array/list 'ARR' consisting of 'N' integers and an integer 'B'. A non-empty subarray of 'ARR' is good if it contains exactly 'B' distinct integers.

Your task is to return the number of good subarrays in the given array/list.

Example:

For 'ARR' = [1, 2, 1, 3, 2, 4] and 'B' = 3, one of the good subarrays which contains three distinct integers is [1, 2, 1, 3].

Note:

An array 'C' is a subarray of array 'D' if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end from array 'D'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two single space-separated integers ‘N’ and ‘B’ denoting the number of integers in the array/list and the given integer.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array.
Output Format : 
For each test case, print an integer denoting the number of good subarrays in the given array/list.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 5000
1 <= B <= N
1 <= ARR[i] <= 10^9

Time Limit: 1sec
Sample Input 1 :
2
5 2 
1 2 1 2 3
5 3
1 2 1 3 4
Sample Output 1:
7
3

Explanation for Sample 1:

All good subarrays in test case 1 are [1, 2], [2, 1], [1, 2], [2, 3], [1, 2, 1], [2, 1, 2], [1, 2, 1, 2].

All good subarrays in test case 2 are [1, 2, 1, 3], [2, 1, 3], [1, 3, 4]. So the total good subarray are 3.
Sample Input 2 :
1
5 5
1 2 1 3 4
Sample Output 2 :
0
Hint

Iterate over all possible subarrays and find the answer.

Approaches (2)
Brute Force

We will iterate through all possible subarrays of the array with the help of two nested loops. We will maintain a Set data structure for the count of distinct integers in a subarray. 

 

The algorithm will be-

  • We will run a loop for the starting index of the subarray.
  • From every starting index, we will run a loop for the ending index of the subarray.
    • We will maintain a set ‘DISTINCT_COUNT’ for the number of distinct integers in the current subarray.
    • Let the current ending index be ‘CURR_INDEX’. Then for each iteration, we will-
      1. Insert ‘ARR[CURR_INDEX]’ to ‘DISTINCT_COUNT’.
      2. If the size of ‘DISTINCT_COUNT’ is exactly ‘B’, we will increment our ‘COUNT’ by 1.
  • We finally return ‘COUNT’.
Time Complexity

O(N^2), where ‘N’ denotes the number of elements in an array.

 

We are visiting all the subarrays and as there are N*(N+1)/2 subarrays in total, the time complexity due to this will be O(N^2).

  

For each subarray, we are inserting its element in a set. As insertion in a set takes constant time, the time complexity will be O(N^2).   

Space Complexity

O(1), constant space is used.

Code Solution
(100% EXP penalty)
Subarray with distinct integers
Full screen
Console