← Back to DSA Course | Chapter 7: Hashing | Lesson 5 of 5

Frequency Counting कैसे करें

Frequency counting tally marks रखने जैसा है कि एक jar में हर candy color कितनी बार दिखता है।

In this page:

  1. What is Frequency Counting
  2. Using a Hash Map
  3. Using an Array
  4. Common Uses
  5. Complexity
Syntax
markup 
freq = {}
for item in collection:
    freq[item] = freq.get(item, 0) + 1

counts = [0] * range_size    # for small integer values
for x in collection:
    counts[x] += 1

What is Frequency Counting

Frequency counting का मतलब है यह tally करना कि किसी collection में हर distinct value कितनी बार दिखती है, जो duplicates, anagrams, और mode statistics detect करने के पीछे building block है। यह एक harder algorithm चलने से पहले एक preprocessing step के रूप में लगातार दिखता है।

उदाहरण: What is Frequency Counting

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int arr[] = {1, 2, 2, 3, 1, 1};
	unordered_map<int, int> freq;
	for (int x : arr) freq[x]++;
	for (auto& p : freq) cout << p.first << ": " << p.second << endl;
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 2, 2, 3, 1, 1};
		HashMap<Integer, Integer> freq = new HashMap<>();
		for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
		for (int key : freq.keySet()) System.out.println(key + ": " + freq.get(key));
	}
}
arr = [1, 2, 2, 3, 1, 1]
freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1
for k, v in freq.items():
    print(k, ":", v)
#include <stdio.h>
int main() {
	int arr[] = {1, 2, 2, 3, 1, 1};
	int freq[10] = {0};
	for (int i = 0; i < 6; i++) freq[arr[i]]++;
	for (int i = 0; i < 10; i++) if (freq[i] > 0) printf("%d: %d\n", i, freq[i]);
	return 0;
}

Using a Hash Map

एक hash map इसके लिए general-purpose tool है: हर distinct value एक key बन जाती है, और इसकी count value है, हर occurrence पर increment से update होती है। यह किसी भी तरह के data के लिए काम करता है, strings और बड़े या sparse number ranges सहित।

उदाहरण: Using a Hash Map

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
	string word = "banana";
	unordered_map<char, int> freq;
	for (char c : word) freq[c]++;
	cout << "a appears " << freq['a'] << " times";
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		String word = "banana";
		HashMap<Character, Integer> freq = new HashMap<>();
		for (char c : word.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
		System.out.println("a appears " + freq.get('a') + " times");
	}
}
word = "banana"
freq = {}
for c in word:
    freq[c] = freq.get(c, 0) + 1
print("a appears", freq['a'], "times")
#include <stdio.h>
int main() {
	char word[] = "banana";
	int freq[256] = {0};
	for (int i = 0; word[i]; i++) freq[(int)word[i]]++;
	printf("a appears %d times", freq['a']);
	return 0;
}

Using an Array

जब values छोटी non-negative integers हों (जैसे ASCII character codes या एक known range के अंदर array indices), value से खुद indexed एक plain array तेज़ है और hashing overhead से पूरी तरह बचता है। यह वही idea है जो एक hash map है लेकिन key सीधे array position में baked है।

उदाहरण: Using an Array

#include <iostream>
#include <string>
using namespace std;
int main() {
	string word = "hello";
	int freq[26] = {0};
	for (char c : word) freq[c - 'a']++;
	cout << "l appears " << freq['l' - 'a'] << " times";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		String word = "hello";
		int[] freq = new int[26];
		for (char c : word.toCharArray()) freq[c - 'a']++;
		System.out.println("l appears " + freq['l' - 'a'] + " times");
	}
}
word = "hello"
freq = [0] * 26
for c in word:
    freq[ord(c) - ord('a')] += 1
print("l appears", freq[ord('l') - ord('a')], "times")
#include <stdio.h>
int main() {
	char word[] = "hello";
	int freq[26] = {0};
	for (int i = 0; word[i]; i++) freq[word[i] - 'a']++;
	printf("l appears %d times", freq['l' - 'a']);
	return 0;
}

Common Uses

यह pattern यह जांचने के पीछे है कि क्या दो strings anagrams हैं (उनके frequency tables compare करें), सबसे frequent element ढूंढना, और बिना sort किए duplicates detect करना। 'मुझे जानना है चीज़ें कितनी बार होती हैं' पहचानना अक्सर किसी problem में इस pattern को देखने की ओर पहला step है।

उदाहरण: Common Uses

#include <iostream>
#include <string>
using namespace std;
bool isAnagram(string a, string b) {
	int freq[26] = {0};
	for (char c : a) freq[c - 'a']++;
	for (char c : b) freq[c - 'a']--;
	for (int f : freq) if (f != 0) return false;
	return true;
}
int main() {
	cout << (isAnagram("listen", "silent") ? "Anagram" : "Not anagram");
	return 0;
}
public class Main {
	static boolean isAnagram(String a, String b) {
		int[] freq = new int[26];
		for (char c : a.toCharArray()) freq[c - 'a']++;
		for (char c : b.toCharArray()) freq[c - 'a']--;
		for (int f : freq) if (f != 0) return false;
		return true;
	}
	public static void main(String[] args) {
		System.out.println(isAnagram("listen", "silent") ? "Anagram" : "Not anagram");
	}
}
def is_anagram(a, b):
    freq = [0] * 26
    for c in a:
        freq[ord(c) - ord('a')] += 1
    for c in b:
        freq[ord(c) - ord('a')] -= 1
    return all(f == 0 for f in freq)

print("Anagram" if is_anagram("listen", "silent") else "Not anagram")
#include <stdio.h>
int isAnagram(char *a, char *b) {
	int freq[26] = {0};
	for (int i = 0; a[i]; i++) freq[a[i] - 'a']++;
	for (int i = 0; b[i]; i++) freq[b[i] - 'a']--;
	for (int i = 0; i < 26; i++) if (freq[i] != 0) return 0;
	return 1;
}
int main() {
	printf(isAnagram("listen", "silent") ? "Anagram" : "Not anagram");
	return 0;
}

Complexity

Frequency table बनाने में input को एक बार scan करने के लिए O(n) time लगता है। Extra space O(k) है, जहां k आप track कर रहे distinct values की संख्या है, जो n से कहीं छोटा हो सकता है अगर values बहुत repeat हों।

उदाहरण: Complexity

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int arr[] = {4, 4, 4, 2, 2, 9};
	int n = 6;
	unordered_map<int, int> freq;
	for (int i = 0; i < n; i++) freq[arr[i]]++;
	cout << "Scanned " << n << " items, " << freq.size() << " distinct keys";
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 4, 4, 2, 2, 9};
		HashMap<Integer, Integer> freq = new HashMap<>();
		for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
		System.out.println("Scanned " + arr.length + " items, " + freq.size() + " distinct keys");
	}
}
arr = [4, 4, 4, 2, 2, 9]
freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1
print("Scanned", len(arr), "items,", len(freq), "distinct keys")
#include <stdio.h>
int main() {
	int arr[] = {4, 4, 4, 2, 2, 9};
	int n = 6;
	int freq[10] = {0};
	int distinct = 0;
	for (int i = 0; i < n; i++) {
		if (freq[arr[i]] == 0) distinct++;
		freq[arr[i]]++;
	}
	printf("Scanned %d items, %d distinct keys", n, distinct);
	return 0;
}
Related Topics

Counting Sort क्या है · Anagram और Frequency Count · Two Sum समस्या · Collision को Handle करना

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. एक unordered_map से freq[x] पढ़ना और यह मान लेना कि यह insert किए बिना 0 है, जब [] असल में एक zero-valued entry insert करता है।
  2. एक fixed-size array उपयोग करना जब values negative या बड़ी हो सकती हैं, इसलिए index range से बाहर जाता है।
  3. Test cases के बीच counts reset करना भूल जाना।
चैप्टर सारांश
  • Hashing fast lookup के लिए keys को values पर map करता है, hash maps और hash sets उपयोग करते हुए।
  • Collision handling उन अलग keys से deal करता है जो उसी जगह map होती हैं।
  • Hashing Two Sum और frequency counting जैसी problems solve करता है।
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Two Sum Problem Next Lesson → Recursion Deep Dive

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.