C# | Memory beats 100% [EXPLAINED]
Intuition\nThis problem is about finding an element in a subarray that appears frequently enough to be considered a "majority" element. To solve this efficientl
# Intuition\nThis problem is about finding an element in a subarray that appears frequently enough to be considered a "majority" element. To solve this efficiently, I need a way to quickly determine how many times each element appears within a specified range of the array.\n\n# Approach\nPreprocess the Array: First, I create a dictionary that maps each element to a list of its positions in the array. This allows me to quickly look up where each element appears.\n\nQuery the Subarray: For each query, I use binary search on the lists of positions to count how many times each element appears within the specified range. This helps in determining if any element meets the threshold requirement.\n\n# Complexity\n- Time complexity:\n\nPreprocessing: O(n log n) for building the position lists.\n\nQuerying: O(m log n), where m is the number of distinct elements. This is efficient because binary search on sorted lists is quick.\n\n- Space complexity:\nO(n) for storing the positions of each element.\n\n# Code\n```csharp []\npublic class MajorityChecker {\n    private readonly Dictionary<int, List<int>> _positions;\n    \n    public MajorityChecker(int[] arr) {\n        _positions = new Dictionary<int, List<int>>();\n        \n        for (int i = 0; i < arr.Length; i++) {\n            if (!_positions.ContainsKey(arr[i])) {\n                _positions[arr[i]] = new List<int>();\n            }\n            _positions[arr[i]].Add(i);\n        }\n    }\n    \n    public int Query(int left, int right, int threshold) {\n        foreach (var kvp in _positions) {\n            int num = kvp.Key;\n            var indices = kvp.Value;\n            \n            int leftIndex = BinarySearch(indices, left);\n            int rightIndex = BinarySearch(indices, right + 1) - 1;\n            \n            if (leftIndex < indices.Count && indices[leftIndex] <= right && rightIndex >= 0) {\n                int count = rightIndex - leftIndex + 1;\n                if (count >= threshold) {\n                    return num;\n                }\n            }\n        }\n        return -1;\n    }\n\n    private int BinarySearch(List<int> list, int target) {\n        int low = 0, high = list.Count;\n        while (low < high) {\n            int mid = (low + high) / 2;\n            if (list[mid] < target) {\n                low = mid + 1;\n            } else {\n                high = mid;\n            }\n        }\n        return low;\n    }\n}\n\n```
['C#']