1287. Element Appearing More Than 25% In Sorted Array

📝 Problem Details

• Title: 1287. Element Appearing More Than 25% In Sorted Array
• Link: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
• Difficulty: Easy
• Tags/Categories: Hashmap Math Arrays

💭What Were My Initial Thoughts?

- create a hashmap 
- store the frequency counts in the map
- iterate over the map and return the value with the highest frequency

🤔What Did I Struggle With?

this above solution is acceptable but i wanted to try and come up with a O(1) space solution
- couldnt figure it out

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        unordered_map<int, int> frequencyMap;
 
        // Store frequency counts in the map
        for (int num : arr) {
            frequencyMap[num]++;
        }
 
        // Iterate over the map and find the element with frequency > 25%
        int n = arr.size();
        for (const auto& pair : frequencyMap) {
            if (pair.second > n / 4) {
                return pair.first;
            }
        }
 
        // If no such element is found (though problem guarantees one exists)
        return -1;
    }
};