Longest Subarray With Equal Number Of 0s 1s And 2s

faq

1. What is the meaning of Longest Subarray With Equal Number Of 0s 1s And 2s?
ans -> Longest subarray for the given array which will contain equal number of 0s, 1s, and 2s , we have return its length only in this question.

2. How can we use HashMap in this question?
ans -> We make a hashmap to solve this problem where the key is a string which is represented by "x1-x0 # x2-x1" where the gap between count of 0s and 1s is separated from the gap between count of 1s and 2s by a "#".

3. Why the time complexity is O(n)?
Ans ->The time complexity is linear due to the traversal through the given array.

4. Can we use Hashset instead of HashMap?
ans -> No, for this perticular question we want the hashmap of type String-Integer where in front of every string we will store the index of the array at which we have derived that string, string contains the difference of "(count1- count0 + "#" + count2 - count1)" 

5. 5. What is the length Of longest Subarray With Equal Number Of 0s 1s And 2s for arr = [0, 1, 0, 2, 0, 1, 0]?
Ans -> length Of longest Subarray With Equal Number Of 0s 1s And 2s is equals to 3.
      1st arr = [1, 0, 2]
      2nd arr = [2, 0, 1].

hints

1. Can you think any approach by using HashMap?

2. Make a String V/S Integer HashMap and investigate what types of strings as a key you can store. 

3. intialize 3 variables 
   1. count0 = count of number of zeros
   2. count1 = count of number of ones
   3. count2 = count of number of two
   for the key string -> take delta value of (count1 - count0) and (count2 - count1) and make a key as "(count1- count0 + "#" + count2 - count1)"
   and the value -> frequency of key
   
4. if key is present into HashMap then add the frequency of key into final count.

mcq

A. What is the Subarray?
1. A subarray is a Subsequence of array.
2. A subarray is a contiguous part of array.
3. Both of the above
4. None of the above

Ans -> 2. A subarray is a contiguous part of array.

B. What are the Subarrays of arr = [1,2,3]?
1. [1],[1,2],[1,2,3]
2. [1],[1,2],[1,2,3],[2],[2,3],[3]
3. [1],[1,2],[1,3],[1,2,3],[2],[2,3],[3]
4. None of the above

Ans -> 2. [1],[1,2],[1,2,3],[2],[2,3],[3]

C. What is formula to calculate how many numbers of subarray can be made for n length array?
1. n * (n + 1) / 2
2. n * (n - 1) / 2
3. n + (n / 2)
4. None of the above

Ans -> 1. n * (n + 1) / 2
Explain : for n = 3 number of subarays can be form 3 * (3 + 1) / 2 = 6

D. What is the Time Complexity to solve this question?      
1. O(n)
2. O(n * logn)
3. O(n * n)
4. O(1)

Ans : 1. O(n)
Explaination : The time complexity is O(n) where n is the number of elements in the array as we are traversing the array to generate the strings and storing them in the hashmap.

E. What is the Space Complexity to solve this question?
1. O(n)
2. O(n * n)
3. O(logn)
4. O(1)

ANS : 1. O(n)
Explaination : The space complexity is also O(n) as we are storing the strings into the hashmap.

solution.java

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // Example 1
        int[] arr1 = {0, 1, 2, 0, 1, 2};
        int result1 = solution(arr1, arr1.length);
        System.out.println("Example 1: " + result1);

        // Example 2
        int[] arr2 = {0, 1, 1, 2, 0, 2, 1, 2};
        int result2 = solution(arr2, arr2.length);
        System.out.println("Example 2: " + result2);

        // Example 3
        int[] arr3 = {2, 0, 1, 1, 0};
        int result3 = solution(arr3, arr3.length);
        System.out.println("Example 3: " + result3);

        // Example 4
        int[] arr4 = {1, 1, 2, 0, 1, 2, 0};
        int result4 = solution(arr4, arr4.length);
        System.out.println("Example 4: " + result4);
    }

    public static int solution(int[] arr, int n) {
        int ans = 0;
        HashMap<String, Integer> map = new HashMap<>();
        int count0 = 0;
        int count1 = 0;
        int count2 = 0;
        String key = "0#0";
        map.put(key, -1);
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) count0++;
            else if (arr[i] == 1) count1++;
            else count2++;
            key = (count1 - count0) + "#" + (count2 - count1);
            if (map.containsKey(key)) {
                int len = i - map.get(key);
                if (ans < len) ans = len;
            } else {
                map.put(key, i);
            }
        }
        return ans;
    }
}