Day 5 – Hashing (Arrays, Maps) and Basic Sorting

Today I covered the fundamentals of hashing and revisited basic sorting algorithms including selection, bubble, and insertion sort.

---

Hashing – Pre-storing and Fetching

Hashing is used to store and retrieve data in constant or near-constant time. It works on the principle of converting a key into an index using a hash function.

Pre-storing + Fetching

• Integer array hashing can be done using a fixed-size array.

• String hashing requires mapping characters to integer indices (based on ASCII).

• Space constraints are important when choosing the data structure.

---

Array Size Limits (C++)

---

Hashing for Integers (Fixed Array)

int hashArr[1000001] = {0}; // 10^6

// Storing frequency
for (int i = 0; i < n; i++) {
    hashArr[arr[i]]++;
}

// Fetching frequency
cout << hashArr[x]; 
// Time: O(1), Space: O(n)

---

Hashing for Characters (Strings)

int hashStr[26] = {0}; // For lowercase 'a' to 'z'

for (char c : str) {
    hashStr[c - 'a']++;
}

cout << hashStr['c' - 'a'];
// Time: O(n), Space: O(26)

---

ASCII Notes

• 'a' = 97, 'A' = 65, '0' = 48

• Can use c - 'a' to get position from 0–25

---

Hashing Large Keys – Using Maps

For values beyond array limits or when keys are strings, pairs, or large numbers:

Map (Ordered)

map<int, int> m;
m[5]++;
cout << m[5];
// Time: O(log n) per insert/access

Unordered Map (Hash Table Based)

unordered_map<int, int> um;
um[5]++;
cout << um[5];
// Avg Time: O(1), Worst Time: O(n)

---

Hashing With Custom Keys

unordered_map<string, int> freq;
freq["abc"]++;
freq["xyz"]++;

map<pair<int, int>, int> pMap;
pMap[{2, 3}] = 5;

---

Hash Function – Division Method

int hashIndex = key % tableSize;

---

Collisions

• In unordered_map, collisions cause performance to degrade.

• Worst-case time for insert/find can become O(n).

---

Frequency Counting Example (Integers)

unordered_map<int, int> freq;
for (int i = 0; i < n; i++) freq[arr[i]]++;

for (auto [k, v] : freq)
    cout << k << ": " << v << endl;

---

LeetCode Problem Solved – 1838. Frequency of the Most Frequent Element

• Approach: Sorting + Sliding Window + Prefix Sum

• Observation: Increase elements in a window until all are equal

• Complexity: Time O(n log n), Space O(1)

• Found it interesting because of the required mathematical insight and careful window control

---

Sorting Algorithms

1. Selection Sort

• Repeatedly selects the minimum element and places it at the beginning

void selectionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        swap(a[i], a[minIdx]);
    }
}
// Time: O(n²), Space: O(1)

---

2. Bubble Sort

• Repeatedly swaps adjacent elements if they are in the wrong order

void bubbleSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);
        }
    }
}
// Time: O(n²), Space: O(1)

Optimized Bubble Sort (Stops if no swap)

void bubbleSortOpt(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n-1; i++) {
        bool didSwap = false;
        for (int j = 0; j < n-i-1; j++) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
                didSwap = true;
            }
        }
        if (!didSwap) break;
    }
}
// Best Case Time: O(n), Worst: O(n²), Space: O(1)

---

3. Insertion Sort

• Picks one element at a time and inserts it into its correct position in the sorted part

void insertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i-1;
        while (j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}
// Time: O(n²), Best Case: O(n), Space: O(1)

---

Summary:

• Learned and implemented integer and string hashing with arrays and maps

• Understood array size limits and when to use map/unordered_map

• Studied hash function, collisions, and frequency counting

• Solved a medium LeetCode problem using sliding window + hashing

• Revised and implemented basic sorting algorithms with optimizations

Will continue with more sorting and searching techniques tomorrow. Theory still pending, to be added separately.

---