# Find the frequency of each element in a sorted array

Given a sorted array, **arr[]** consisting of **N** integers, the task is to find the frequencies of each array element.

**Examples:**

Input:arr[] = {1, 1, 1, 2, 3, 3, 5, 5, 8, 8, 8, 9, 9, 10}Output:Frequency of 1 is: 3

Frequency of 2 is: 1

Frequency of 3 is: 2

Frequency of 5 is: 2

Frequency of 8 is: 3

Frequency of 9 is: 2

Frequency of 10 is: 1

Input:arr[] = {2, 2, 6, 6, 7, 7, 7, 11}Output:Frequency of 2 is: 2

Frequency of 6 is: 2

Frequency of 7 is: 3

Frequency of 11 is: 1

**Naive Approach: **The simplest approach is to traverse the array and keep the count of every element encountered in a HashMap and then, in the end, print the frequencies of every element by traversing the HashMap. This approach is already implemented here.

**Time Complexity:** O(N)**Auxiliary Space:** O(N)

**Efficient Approach: **The above approach can be optimized in terms of space used based on the fact that, in a sorted array, the same elements occur consecutively, so the idea is to maintain a variable to keep track of the frequency of elements while traversing the array. Follow the steps below to solve the problem:

- Initialize a variable, say
**freq**as**1**to store the frequency of elements. - Iterate in the range
**[1, N-1]**using the variable**i**and perform the following steps:- If the value of
**arr[i]**is equal to**arr[i-1]**, increment**freq**by**1**. - Else print value the frequency of
**arr[i-1]**obtained in**freq**and then update**freq**to**1**.

- If the value of
- Finally, after the above step, print the frequency of the last distinct element of the array as
**freq**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `// Function to print the frequency` ` ` `// of each element of the sorted array` ` ` `void` `printFreq(vector<` `int` `> &arr, ` `int` `N)` ` ` `{` ` ` ` ` `// Stores the frequency of an element` ` ` `int` `freq = 1;` ` ` ` ` `// Traverse the array arr[]` ` ` `for` `(` `int` `i = 1; i < N; i++)` ` ` `{` ` ` ` ` `// If the current element is equal` ` ` `// to the previous element` ` ` `if` `(arr[i] == arr[i - 1])` ` ` `{` ` ` ` ` `// Increment the freq by 1` ` ` `freq++;` ` ` `}` ` ` ` ` `// Otherwise,` ` ` `else` `{` ` ` `cout<<` `"Frequency of "` `<<arr[i - 1]<< ` `" is: "` `<< freq<<endl;` ` ` `// Update freq` ` ` `freq = 1;` ` ` `}` ` ` `}` ` ` ` ` `// Print the frequency of the last element` ` ` `cout<<` `"Frequency of "` `<<arr[N - 1]<< ` `" is: "` `<< freq<<endl;` ` ` `}` ` ` `// Driver Code` ` ` `int` `main()` ` ` `{` ` ` ` ` `// Given Input` ` ` `vector<` `int` `> arr` ` ` `= { 1, 1, 1, 2, 3, 3, 5, 5,` ` ` `8, 8, 8, 9, 9, 10 };` ` ` `int` `N = arr.size();` ` ` ` ` `// Function Call` ` ` `printFreq(arr, N);` ` ` `return` `0;` ` ` `} ` `// This code is contributed by codersaty` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `import` `java.lang.*;` `import` `java.util.*;` `class` `GFG {` ` ` `// Function to print the frequency` ` ` `// of each element of the sorted array` ` ` `static` `void` `printFreq(` `int` `arr[], ` `int` `N)` ` ` `{` ` ` `// Stores the frequency of an element` ` ` `int` `freq = ` `1` `;` ` ` `// Traverse the array arr[]` ` ` `for` `(` `int` `i = ` `1` `; i < N; i++) {` ` ` `// If the current element is equal` ` ` `// to the previous element` ` ` `if` `(arr[i] == arr[i - ` `1` `]) {` ` ` `// Increment the freq by 1` ` ` `freq++;` ` ` `}` ` ` `// Otherwise,` ` ` `else` `{` ` ` `System.out.println(` `"Frequency of "` ` ` `+ arr[i - ` `1` `]` ` ` `+ ` `" is: "` `+ freq);` ` ` `// Update freq` ` ` `freq = ` `1` `;` ` ` `}` ` ` `}` ` ` `// Print the frequency of the last element` ` ` `System.out.println(` `"Frequency of "` ` ` `+ arr[N - ` `1` `]` ` ` `+ ` `" is: "` `+ freq);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String args[])` ` ` `{` ` ` `// Given Input` ` ` `int` `arr[]` ` ` `= { ` `1` `, ` `1` `, ` `1` `, ` `2` `, ` `3` `, ` `3` `, ` `5` `, ` `5` `,` ` ` `8` `, ` `8` `, ` `8` `, ` `9` `, ` `9` `, ` `10` `};` ` ` `int` `N = arr.length;` ` ` `// Function Call` ` ` `printFreq(arr, N);` ` ` `}` `}` |

## Python3

`# Python3 program for the above approach` `# Function to print the frequency` `# of each element of the sorted array` `def` `printFreq(arr, N):` ` ` ` ` `# Stores the frequency of an element` ` ` `freq ` `=` `1` ` ` `# Traverse the array arr[]` ` ` `for` `i ` `in` `range` `(` `1` `, N, ` `1` `):` ` ` ` ` `# If the current element is equal` ` ` `# to the previous element` ` ` `if` `(arr[i] ` `=` `=` `arr[i ` `-` `1` `]):` ` ` ` ` `# Increment the freq by 1` ` ` `freq ` `+` `=` `1` ` ` `# Otherwise,` ` ` `else` `:` ` ` `print` `(` `"Frequency of"` `,arr[i ` `-` `1` `],` `"is:"` `,freq)` ` ` `# Update freq` ` ` `freq ` `=` `1` ` ` `# Print the frequency of the last element` ` ` `print` `(` `"Frequency of"` `,arr[N ` `-` `1` `],` `"is:"` `,freq)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `# Given Input` ` ` `arr ` `=` `[` `1` `, ` `1` `, ` `1` `, ` `2` `, ` `3` `, ` `3` `, ` `5` `, ` `5` `,` `8` `, ` `8` `, ` `8` `, ` `9` `, ` `9` `, ` `10` `]` ` ` `N ` `=` `len` `(arr)` ` ` `# Function Call` ` ` `printFreq(arr, N)` ` ` ` ` `# This code is contributed by ipg2016107.` |

## C#

`// C# program for the above approach` `using` `System;` `public` `class` `GFG{` ` ` `// Function to print the frequency` `// of each element of the sorted array` `static` `void` `printFreq(` `int` `[] arr, ` `int` `N)` `{` ` ` `// Stores the frequency of an element` ` ` `int` `freq = 1;` ` ` `// Traverse the array arr[]` ` ` `for` `(` `int` `i = 1; i < N; i++)` ` ` `{` ` ` `// If the current element is equal` ` ` `// to the previous element` ` ` `if` `(arr[i] == arr[i - 1])` ` ` `{` ` ` `// Increment the freq by 1` ` ` `freq++;` ` ` `}` ` ` `// Otherwise,` ` ` `else` `{` ` ` `Console.WriteLine(` `"Frequency of "` `+ arr[i - 1] + ` `" is: "` `+ freq);` ` ` `// Update freq` ` ` `freq = 1;` ` ` `}` ` ` `}` ` ` `// Print the frequency of the last element` ` ` `Console.WriteLine(` `"Frequency of "` `+ arr[N - 1] + ` `" is: "` `+ freq);` `}` `// Driver Code` `static` `public` `void` `Main (){` ` ` `// Given Input` ` ` `int` `[] arr = { 1, 1, 1, 2, 3, 3, 5, 5,` ` ` `8, 8, 8, 9, 9, 10 };` ` ` `int` `N = arr.Length;` ` ` ` ` `// Function Call` ` ` `printFreq(arr, N);` `}` `}` `// This code is contributed by Dharanendra L V.` |

## Javascript

`<script>` `// JavaScript program for the above approach` `// Function to print the frequency` `// of each element of the sorted array` `function` `printFreq(arr, N)` `{` ` ` ` ` `// Stores the frequency of an element` ` ` `let freq = 1;` ` ` `// Traverse the array arr[]` ` ` `for` `(let i = 1; i < N; i++)` ` ` `{` ` ` ` ` `// If the current element is equal` ` ` `// to the previous element` ` ` `if` `(arr[i] == arr[i - 1])` ` ` `{` ` ` ` ` `// Increment the freq by 1` ` ` `freq++;` ` ` `}` ` ` `// Otherwise,` ` ` `else` ` ` `{` ` ` `document.write(` `"Frequency of "` `+` ` ` `parseInt(arr[i - 1]) + ` `" is: "` `+` ` ` `parseInt(freq) + ` `"<br>"` `);` ` ` ` ` `// Update freq` ` ` `freq = 1;` ` ` `}` ` ` `}` ` ` `// Print the frequency of the last element` ` ` `document.write(` `"Frequency of "` `+` ` ` `parseInt(arr[N - 1]) + ` `" is: "` `+` ` ` `parseInt(freq) + ` `"<br>"` `);` `}` `// Driver Code` `// Given Input` `let arr = [ 1, 1, 1, 2, 3, 3, 5, 5,` ` ` `8, 8, 8, 9, 9, 10 ];` `let N = arr.length;` `// Function Call` `printFreq(arr, N);` `// This code is contributed by Potta Lokesh` `</script>` |

**Output**

Frequency of 1 is: 3 Frequency of 2 is: 1 Frequency of 3 is: 2 Frequency of 5 is: 2 Frequency of 8 is: 3 Frequency of 9 is: 2 Frequency of 10 is: 1

**Time Complexity:** O(N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.