Subarrays with distinct elements Java

justformyntra8 · June 12, 2019, 4:55pm

I am getting timed out for 2 test cases
Lemme know some alternate method, since this has too much time complexity

bhardwaj-aman/java-data-structures-practice-questions/blob/master/(*)Subarrays with distinct elements

package HashingPractice;
import java.util.*;
public class Subarrays_with_distinct_elements  {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int a = s.nextInt();
        int[] b = new int[a];
        for(int i=0;i<a;i++){
            b[i] = s.nextInt();
        }
        HashMap<Integer,ArrayList<Integer>> h = new HashMap<Integer,ArrayList<Integer>>();
       for(int i=0;i<b.length;i++){
           for(int j=i;j<b.length;j++){
               int[] arr = new int[j-i+1];
               for(int k=i;k<=j;k++){
                  arr[k-i]= b[k];
               }
               if(h.get(b[i])==null){
                   h.put(b[i],new ArrayList<Integer>());
               }

This file has been truncated. show original

cutiecoder · June 13, 2019, 5:44pm

Hi,
see you can use here another simpler approach that you can make a arraylist in which you will keep a record that whether a particular number is repeated or not, then you will go on each and every element of the array and use one more loop inside that loop(j) for subsets and check that if j<n and do arraylist contains that jth element if yes then come out of the inside loop else keep on incrementing j and adding that jth number in arraylist.
Then the solution is based on the fact that if we know all elements in a subarray arr[i…j] are distinct, sum of all lengths of distinct element subarrays in this subarray is ((j-i) * (j-i+1))/2 . (This is because the possible lengths of the subarrys will be 1,2,3,…till j-i+1,So sum will be the above formula.)
So when you will come out of the inside loop put ans=ans+(the above formula) and simply increment i.

cutiecoder · June 18, 2019, 3:59pm

Hi @justformyntra8 as you are not responding to the thread, I am marking your doubt as resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “Ask Doubt” section, when your doubt is resolved.

cutiecoder · June 18, 2019, 4:00pm

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.