Get this book -> Problems on Array: For Interviews and Competitive Programming

Given an array of N elements, our task is to find the **least frequent element** present in it. There are many ways to do this. In this article, we are going to talk about 3 of those methods along with their implementation.

Table of Contents

- Different ways to find the least frequent element in an array
- Naive Algorithm
- Optimized algorithm with array sorting
- Optimized algorithm with mapping

# Different ways to find the least frequent element

We are going to be exploring three methods through which we will be able to find the least frequent element in an array and then print it. If there are multiple elements that appear the least number of times in the array, then we can print any one of them.

The three methods are:

- Naive algorithm
- Optimized algorithm with array sorting
- Optimized algorithm with mapping

# (1) Naive Algorithm

This is a very simple and straight-forward solution to this problem that doesn't really take the efficiency and complexity of the algorithm into account. It is a brute force algorithm.

The steps of Naive algorithm to find the least frequent element are as follows:

NOTE: Here arr is our main input array

- Initialize the values of leastCtr and leastElement as the length of the input array and -99 respectively.
- for i from 0 to length of arr do

2.1 Initialize the value of currentCtr as 0

2.2 for j from 0 to length of arr do

2.2.1 if (arr[i] == arr[j]) do

2.2.1.1 Increment the value of currentCtr by 1

2.3 if currentCtr < leastCtr do

2.3.1 Replace the values of leastCtr and leastElement with currentCtr and arr[i] respectively - By the time we reach this point, we will already have the least frequent element of the array stored in the leastElement variable and its count will be stored in the leastCtr variable.

## Question

#### The time complexity of this algorithm should be:

### (a) Explanation

Let us consider the following array as our input.

- For each element of the
**outer loop i**, the**inner loop j**checks if the element present at the ith index is equal to the element present at the jth index. If they are equal, then the**currentCtr**variable is incremented by 1. - When the control comes out of the inner loop, the algorithm then checks if the value of
**currentCtr**is lesser than the value of**leastCtr**. If it is, then the value of**leastCtr**is replaced with the value of**currentCtr**. - The size of the given array is
**5**. - When
**i = 0**and the**inner loop j**has finished completely, the values of**currentCtr**,**leastCtr**,**leastElement**are updated to**2**,**2**and**5**respectively because the value of**currentCtr (2)**was lesser than the value of**leastCtr (5)**. - When
**i = 1**and the**inner loop j**has finished completely, the value of**currentCtr**is updated to 2. However, the value of**leastCtr (2)**and**leastElement (5)**remain the same as the value of**currentCtr (2)**is not less than**leastCtr (2)**. - When
**i = 2**and the**inner loop j**has finished completely, the values of**currentCtr**,**leastCtr**,**leastElement**are updated to**1**,**1**and**16**respectively because the value of**currentCtr (1)**was lesser than the value of**leastCtr (2)**. - When
**i = 3**and the**inner loop j**has finished completely, the value of**currentCtr**is updated to 2. However, the value of**leastCtr (1)**and**leastElement (16)**remain the same as the value of**currentCtr (2)**is not less than**leastCtr (1)**. - When
**i = 4**and the**inner loop j**has finished completely, the value of**currentCtr**is updated to 2. However, the value of**leastCtr (1)**and**leastElement (16)**remain the same as the value of**currentCtr (2)**is not less than**leastCtr (1)**. - Finally, after the completion of the loops, the least frequent element in the array (
**leastElement**) is found to be**16**and its count was found to be**1**.

### (b) Implementation in Python

Following is the implementation of our Naive approach in Python:

```
def findLeastFreqElementNaive(arr):
leastCtr, leastElement = len(arr), -99
for i in range(len(arr)):
currentCtr = 0
for j in range(len(arr)):
if (arr[i] == arr[j]):
currentCtr += 1
if (currentCtr < leastCtr):
leastCtr, leastElement = currentCtr, arr[i]
return leastElement, leastCtr
if __name__ == "__main__":
arr = [5, 6, 16, 6, 5]
leastFreqElementNaive, ctr1 = findLeastFreqElementNaive(arr)
print("====NAIVE ALGORITHM====")
print("Given array:", arr)
print("The least frequent element in the array is:", leastFreqElementNaive)
print("Count of", leastFreqElementNaive,":", ctr1)
```

(c) Output

```
====NAIVE ALGORITHM====
Given array: [5, 6, 16, 6, 5]
The least frequent element in the array is: 16
Count of 16 : 1
```

(d) Complexity

Time complexity: **O(NÂ²)**

Space complexity: **O(1)**

# (2) Optimized algorithm with array sorting

This is an optimized algorithm which is much more efficient than the naive algorithm in terms of computational complexity. Firstly, we sort the array and then traverse through each element linearly while keeping a track of the frequency of the elements.

The steps of our optimized algorithm using sorting to find the least frequent element are as follows:

NOTE: Here arr is our main input array

- Copy the contents of the input array to a new variable temp_arr. The motivation behind this step is so that the original order of the input array is maintained and we can perform the required operations on the temporary array.
- Initialize the values of leastCtr, leastElement and currentCtr as the length of the input array, -99 and 1 respectively.
- Perform the sorting operation on temp_arr. For example, it will be temp_arr.sort() on Python.
- for i from 0 to (length of temp_arr) - 1 do

4.1 if temp_arr[i] == temp_arr[i + 1] do

4.1.1 Increment the value of currentCtr by 1

4.2 else do

4.2.1 if currentCtr < leastCtr do

4.2.1.1 Replace the values of leastCtr and leastElement with currentCtr and temp_arr[i] respectively

4.2.2 Reset the value of currentCtr to 1 - if currentCtr < leastCtr do

5.1 Replace the values of leastCtr and leastElement with currentCtr and temp_arr[len(temp_arr) - 1] respectively. We are performing this extra check because this check would not be performed for the last element in the array in our main loop. This is why we have to explicitly check if the last element in the input array is the least frequent element in the array or not. - By the time we reach this point, we will already have the least frequent element of the array stored in the leastElement variable and its count will be stored in the leastCtr variable.

## Question

#### The time complexity of this algorithm should be:

### (a) Explanation

Let us consider the following array as our input.

- Firstly, the array is sorted.

- After sorting, for each i from 0 to the size of the array minus 1, i.e., 4, we check if the value of
**temp_arr[i]**is equal to the value of**temp_arr[i + 1]**. If it is, then we increment the value of**currentCtr**and go back to the loop. - However, if the value of
**temp_arr[i]**is not equal to the value of**temp_arr[i + 1]**, then we check if the value of**currentCtr**is lesser than the value of**leastCtr**. If it is, then we update the values of**leastCtr**and**leastElement**to**currentCtr**and**temp_arr[i]**respectively. - When
**i = 0**, the values of**leastCtr**and**leastElement**remain**5**and**-99**respectively. Since the value of**temp_arr[i] (3)**is equal to the value of**temp_arr[i + 1] (3)**, the value of**currentCtr**is incremented by 1 (becomes**2**) and then the control goes back to the start of the loop. - When
**i = 1**, the value of**temp_arr[i] (3)**is not equal to the value of**temp_arr[i + 1] (15)**, and the value of**currentCtr**is lesser than the value of**leastCtr**, therefore the values of**leastCtr**is set to the value of**currentCtr (2)**and the value of**leastElement**becomes**temp_arr[i] (3)**. After that, the value of**currentCtr**is reset to**1**and the control goes back to the start of the loop. - When
**i = 2**, since the value of**temp_arr[i] (15)**is not equal to the value of**temp_arr[i + 1] (21)**, the values of**leastCtr (2)**and**leastElement (3)**are set to**1**and**15**respectively. The control then goes back to the main loop. - When
**i = 3**, the value of**temp_arr[i] (21)**is equal to the value of**temp_arr[i + 1]**. The value of**currentCtr (1)**is incremented and becomes**2**and then the loop finally stops. - One final check is performed to check if the last element is the least frequent element in the array. However, that is not the case in our input array, so we simply return the values of
**leastElement (15)**and**leastCtr (1)**.

### (b) Implementation in Python

Following is the implementation of our Optimized algorithm with array sorting in Python:

```
def findLeastFreqElementSorting(arr):
temp_arr, leastCtr, leastElement, currentCtr = arr.copy(), len(arr), -99, 1
temp_arr.sort()
for i in range(len(temp_arr) - 1):
if (temp_arr[i] == temp_arr[i + 1]):
currentCtr += 1
else:
if (currentCtr < leastCtr):
leastCtr, leastElement = currentCtr, temp_arr[i]
currentCtr = 1
if (currentCtr < leastCtr):
leastCtr, leastElement = currentCtr, temp_arr[len(temp_arr) - 1]
return leastElement, leastCtr
if __name__ == "__main__":
arr = [3, 21, 21, 15, 3]
leastFreqElementSorting, ctr2 = findLeastFreqElementSorting(arr)
print("====OPTIMIZED ALGORITHM WITH SORTING====")
print("Given array:", arr)
print("The least frequent element in the array is:", leastFreqElementSorting)
print("Count of", leastFreqElementSorting,":", ctr2)
```

### (c) Output

```
====OPTIMIZED ALGORITHM WITH SORTING====
Given array: [3, 21, 21, 15, 3]
The least frequent element in the array is: 15
Count of 15 : 1
```

### (d) Complexity

Time complexity: **O(N logN)**

Space complexity: **O(N)** (because of the usage of the sort() method)

# (3) Optimized algorithm with hash mapping

This is another optimized algorithm which is much more efficient than the naive algorithm in terms of computational complexity. Since we are using the python language, we will make use of the **dictionary** data structure to implement this algorithm with mapping.

The algorithm is illustrated below:-

NOTE: Here arr is our main input array

1. Declare dictMap as an empty dictionary. We will map the elements and their frequencies here.

2. for i from 0 to length of arr do

2.1 if arr[i] is present in dictMap as a key do

2.1.1 Increment the value corresponding to the key arr[i] by 1 in dictMap

2.2 else do

2.2.1 In dictMap, initialize the key arr[i] with its value as 1

3. Put the least value present in dictMap in the leastElementCtr variable. For example, in python, it can be simply done by calling the min method as min(dictMap.values())

4. for every key i in dictMap do

4.1 if dictMap[i] == leastElementCtr do

4.1.1 Initialize the value of the variable leastElement as i

4.1.2 break the loop

5. By the time we reach this point, we will already have the least frequent element of the array stored in the leastElement variable and its count will be stored in the leastCtr variable.

## Question

#### The time complexity of this algorithm should be:

### (a) Explanation

Let us consider the following array as our input.

- For each index
**i (0 to 4)**in the array, if**arr[i]**is not present in our dictionary**dictMap**, we make an addition to**dictMap**with the key being**arr[i]**and the value being**1**. If the the value**arr[i]**is present in our**dictMap**, then we simply increment the value by 1 that corresponds to the key**dictMap[arr[i]]**. - After all the values (frequencies) have been mapped to their respective keys (elements), we then run a final loop to find the key (element) with the minimum value (frequency). After this loop, we can simply return the least frequent element and its frequency as well.
- In the first loop, when
**i = 0**, we insert the key-value pair of**17: 1**to**dictMap**.**dictMap = {17: 1}** - When
**i = 1**, we insert the key-value pair of**10: 1**to**dictMap**.**dictMap = {17: 1, 10: 1}** - When
**i = 2**, we insert the key-value pair of**11: 1**to**dictMap**.**dictMap = {17: 1, 10: 1, 11: 1}** - When
**i = 3**, since**arr[i] (11)**is present in**dictMap**, we increment the value by 1 in**dictMap**where the key is**arr[i]**.**dictMap = {17: 1, 10: 1, 11: 2}** - When
**i = 4**, since**arr[i] (10)**is present in**dictMap**, we increment the value by 1 in**dictMap**where the key is**arr[i]**.**dictMap = {17: 1, 10: 2, 11: 2}** - The key (element) with the minimum frequency is found to be
**17**with a frequency of**1**. We can return these values now as the final result has been computed.

### (b) Implementation

Implementation of our Optimized algorithm with hash mapping in Python:

```
def findLeastFreqElementMapping(arr):
dictMap = {}
for i in range(len(arr)):
if (arr[i] in dictMap.keys()):
dictMap[arr[i]] += 1
else:
dictMap[arr[i]] = 1
leastElementCtr = min(dictMap.values())
for i in dictMap:
if dictMap[i] == leastElementCtr:
leastElement = i
break
return leastElement, leastElementCtr
if __name__ == "__main__":
arr = [17, 10, 11, 11, 10]
leastFreqElementMapping, ctr3 = findLeastFreqElementMapping(arr)
print("====OPTIMIZED ALGORITHM WITH MAPPING====")
print("Given array:", arr)
print("The least frequent element in the array is:", leastFreqElementMapping)
print("Count of", leastFreqElementMapping,":", ctr3)
```

### (c) Output

```
====OPTIMIZED ALGORITHM WITH MAPPING====
Given array: [17, 10, 11, 11, 10]
The least frequent element in the array is: 17
Count of 17 : 1
```

### (d) Complexity

Time complexity: O(N)

Space complexity: O(1)

## Summary

As a summary of our three methods for finding the least frequent element are:

- Naive algorithm O(N^2) time, O(1) space.
- Optimized algorithm with array sorting O(N logN) time, O(1) space.
- Optimized algorithm with mapping O(N) time, O(N) space.

With this article at OpenGenus, you must have the complete idea of different efficient approaches to find the Least frequent element in an array.