Problem in 'Subarrays with distinct elements' question

#1

PLEASE HELP ME WITH THIS CODE. THIS CODE IS PASSING ONLY ONE TEST CASE (THIRD) OUT OF THREE. IT IS SHOWING WRONG ANSWER. CODE IS WORKING FOR ALL TEST CASES THAT I HAVE TRIED MANUALLY.

import java.util.;
public class SubArrays
{
public static void main(String[] args)
{
SubArrays obj=new SubArrays();
Scanner sc=new Scanner(System.in);
int k,n=sc.nextInt();
int arr[]=new int[n];
for(k=0;k<n;k++)
{
arr[k]=sc.nextInt();
}
int length=obj.longestArray(arr);
int ans=0,j=length-1;
for(k=0;k<length;k++)
{
ans=ans+((j-k+1)(j-k+2))/2;
}
System.out.println(ans%(1000000007));

}
public int longestArray(int arr[])
{
    int i=0,j=1,max=0,currLength=1;
    HashMap<Integer,Boolean> map=new HashMap<>();
    map.put(arr[0],true);
    
    while (i < arr.length - 1 && j < arr.length) 
    {
        if (!map.containsKey(arr[j])) 
        {
            currLength++;
            map.put(arr[j++],true);
        }
        else 
        {
            max = Math.max(max, currLength);
            map.remove(arr[i++]);
            currLength--;
        }
    }
    return Math.max(currLength,max);
}

}

#2

Although your implementation is correct for the most part, you should store the last occurrence of each number inside the map. That way, when you encounter the same element again then check if this length is greater than the last distinct last length, if it is, add it to the answer else add the previous longest length to the answer.

#3

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.

#4

I have implemented your suggestion but then also, the same output is displayed.

#5

Please post the link to your code then

#6

import java.util.*;
public class MaxDistinctSubArray
{
public int longestSubArray(int arr[])
{
HashMap<Integer,Boolean> map=new HashMap<>();
map.put(arr[0],true);
int length=1;
int newLength=1;
int i=1;
while(i<arr.length)
{
int num=arr[i];
if(!map.containsKey(num))
{
map.put(num,true);
if(i==arr.length-1)
{
newLength=map.size();
if(newLength>length)
length=newLength;
}
}
else
{
newLength=map.size();
if(newLength>length)
length=newLength;
map=new HashMap<>();
map.put(num,true);
}
i++;
}
return length;
}

public static void main(String[] args) 
{
    MaxDistinctSubArray obj=new MaxDistinctSubArray();
    Scanner sc=new Scanner(System.in);
    int k,n=sc.nextInt();
    int arr[]=new int[n];
    for(k=0;k<n;k++)
    {
        arr[k]=sc.nextInt();
    }
    int length=obj.longestSubArray(arr);
    int ans=0,j=length-1;
    for(k=0;k<length;k++)
    {
        ans=ans+((j-k+1)*(j-k+2))/2;
    }
    System.out.println(ans%(1000000007));
}

}

#7

I think either you have read the question incorrectly or your logic is wrong. You don’t need to find the longest subarray with distinct elements, instead you need to find the sum of lengths of all the subarrays with distinct elements. For that, you could use this logic,

Start iterating from i = 0 and keep a map to store the last occurrence of each number that you’ve encountered so far.Also keep a variable, currMaxLen, that stores the length of the longest subarray that ended on the previous element and contained all distinct elements. Initialize this variable to 0. Now, if the current element hasn’t been encountered before, then it won’t be present in your map, and thus this element is safe to be taken with the longest subarray of distinct elements till the previous element. E.g. if I have an array, 3, 4, 10, 7, 9, 10, 12. Imagine that I have done my iterations till the second last element i.e. 10 and so the currMaxLen = 3. Now, when I come to encounter 12, it is not in the map, so I can easily say that the longest subarray ending in 12 that contains all distinct elements should be of length 1 greater than than currMaxLen, i.e. the array corresponding to 7, 9, 10, 12. Now, if this array has length x, and all of its elements are distinct, then definitely all the subarrays of this subarray will have distinct elements, i.e. {7}, {9}, {10}, {12}, {7, 9}, {9, 10}, {10, 12}, {7, 9, 10},{9, 10, 12}, {7,9, 10, 12} and on the first thought , you should think that we should just increment our answer by x * (x + 1) /2 where x is the value of currMaxLen at that time. But wait, there’s a catch, you shouldn’t include the subarrays like {7}, {9}, {10}, {7, 9}, etc since these arrays are not ending at 12 and so they must have already been accounted for in the answer before. So you just need to add currMaxLen to the answer.

For the other case, if the current element has been encountered before, then you need to take the minimum of the i - lastOccurrence of this element and currMaxLen, (try to reason it through). Similar, reasoning goes into this to increment our final answer.

Also, since the answer is required under a modulo prime, you should take the modulo on every intermediate stage of incrementing your final answer. I hope this clears your doubt.