Reduce Array Size to The Half

Approach 1

We will be using HashMap for storing the count. HashMap is a Map interface that stores the key and value pair where keys should be unique. 

For more details regarding HashMap, do refer to these amazing, engaging articles→ Introduction to HashMap and Implementation of HashMap.

Input :

Output:

   3

As we see in the example, we have to keep the count of occurrences for every element; we will be using HashMap.  It will be stored like this:

To get the element having a maximum frequency, we will sort the array in descending order, due to which we will get to know which element is occurring most of the time.

After sorting table looks like this:

• First, we will pick elements having a maximum frequency of ‘3’.
• Taking ans as a variable to store the number of elements to be deleted.
• Ans will be updated to 1 after selecting an element with frequency ‘3’.
• Now the size of the array will become ‘9,’ i.e., 12-3=9. We want the size to be ‘6’ or less than ‘6’.
• After frequency ‘3’, we will select the subsequent frequency from the table, i.e., ‘2’.
• Ans will be updated to 2 after selecting the element with frequency ‘2’.
• The size of the array will now become 9-2=7. It is still more than ‘6’.
• The subsequent frequency we will select is ‘2’.
• Ans will be updated to 3 after selecting the element with frequency ‘2’.
• The size of the array will become 7-2=5. Which is less than 6. 
• The output will be 3.

Code

public class reduce {

 public static int minSize(int[] arr,int n) {
      
  //creating HashMap using its basic syntax
HashMap<Integer, Integer> count = new HashMap<>();
 //storing the frequency along with the values using inbuilt functions of HashMap
 for (int x : arr) 
  count.put(x, count.getOrDefault(x, 0) + 1);
        
            //Creating array for storing the frequencies using counting sort
 int[] counting = new int[count.values().size()];
 int i=0;
 for (int freq : count.values()) 
  counting[i++]=freq;
Arrays.sort(counting);

 int ans = 0, removed = 0, half = n / 2;
i=counting.length-1;
 while (removed < half) {
ans ++;
removed+=counting[i--];
}
 return ans;
}

//Main function
public static void main(String[] args) {
int arr[]= {3,3,3,3,5,5,5,2,2,7};
int n=10;
System.out.println(minSize(arr,n));

}

}

You can also try this code with Online Java Compiler

Run Code

Output:

2

You can also try this code with Online Java Compiler

Run Code

Analysis of Complexity

Time Complexity: The time complexity of finding the frequency and sorting the elements will be O(nlogn).

Space Complexity: The space complexity is O(n) as we require extra space for storing the sorted elements.

You can also read about the Longest Consecutive Sequence.

Approach 2

• In the worst case, the maximum value in the frequency array is n, which happens when all arr numbers are the same.
• We can sort frequencies by using Counting Sort, which is O(n) in Time Complexity.
• To solve this problem efficiently, we will be using some modifications to the previous approach.

Code

public class reduce {

 public static int minSize(int[] arr,int n) {
      
  //creating HashMap using its basic syntax
HashMap<Integer, Integer> count = new HashMap<>();
 //storing the frequency along with the values using inbuilt functions of HashMap
 for (int x : arr) 
  count.put(x, count.getOrDefault(x, 0) + 1);
        
            //Creating array for storing the frequencies using counting sort
 int[] counting = new int[n + 1];
 for (int freq : count.values()) 
  ++counting[freq];

 int ans = 0, removed = 0, half = n / 2, freq = n;
 while (removed < half) {
ans += 1;
 while (counting[freq] == 0) --freq;
removed += freq;
--counting[freq];
}
 return ans;
}

//Main function
public static void main(String[] args) {
int arr[]= {3,3,3,3,5,5,5,2,2,7};
int n=10;
System.out.println(minSize(arr,n));

}

}

You can also try this code with Online Java Compiler

Run Code

Output

2

Analysis of Complexity

Time Complexity: The time complexity will be O(n) as the counting sort is used.

Space Complexity: The space complexity is O(n).

Frequently Asked Questions

What do you mean by Counting Sort?

It is a sorting technique that counts the number of objects having distinct key values, i.e., hashing.

What is the time complexity for finding the storing the frequency of elements?

O(n) time will be taken to find the frequency count using counting sort.

What do you mean by HashMap?

HashMap allows us to store key and value pairs, where keys should be unique. It is like a Hashtable class but not synchronized. It may have one null key and multiple null values.

Conclusion

This blog discusses finding the frequency of elements and eliminating their occurrences to reduce the array size to half. In our approaches, we have used Counting Sort and HashMap for solving the problem efficiently.

You can refer to this suggested article which will give you insights into questions about different Data Structures.

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

After solving this problem, you didn't feel excited to solve more problems based on Data Structures and Algorithms? But you might be unaware/dilemma about where to start from or what will be the roadmap to solve the problems on a variety of topics; Don't worry, Coding Ninjas has your back and will provide you with Problems, Sorting Based Problems, HashMap, and our paid courses, etc. You may also check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

Also, if you are in the learning phase already, check out our new interview preparation and interview bundle for your placement preparations asked in big product-based companies like Amazon, Facebook, etc.