Given an integer array nums, return a list of [element, frequency] pairs showing how often each distinct value occurs. Include each value exactly once and the pairs may appear in any order.
Example 1
Input: nums = [4, 7, 4, 2, 7, 4]
Output: [[4, 3], [7, 2], [2, 1]]
Explanation: The value 4 appears three times, 7 appears twice, and 2 appears once.
Example 2
Input: nums = [6, 9, 3]
Output: [[6, 1], [9, 1], [3, 1]]
Explanation: Every element appears once, so each frequency is 1.
Approach
Go through the array one number at a time. Use a hash map to store each number and its count. When a number appears for the first time, its count is 1. Each time it appears again, increase that same count by one.
After checking the whole array go through the hash map and collect each number with its final count. Since the map keeps one entry per number, each number appears only once in the result.
Algorithm
Examine the array from left to right.
Maintain a frequency for each distinct value in a hash map.
Increase a value’s frequency whenever it appears.
After processing the array, form one
[element, frequency]pair from each map entry.Return the pairs in any order.
Dry Run
Count frequencies of array elements
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Returns one [element, frequency] pair for each distinct value. vector<vector<int>> countFrequencies(const vector<int>& nums) { // Each distinct value has a single entry in the hash map. unordered_map<int, int> freq; for (int value : nums) { // A missing key starts with a count of zero. // Each occurrence increases its associated count. freq[value]++; } vector<vector<int>> result; // Every map entry produces exactly one output pair. for (const auto& entry : freq) { result.push_back({entry.first, entry.second}); } // The problem allows the pairs to appear in any order. return result; }};// Driver codeint main() { vector<int> nums = {4, 7, 4, 2, 7, 4}; // Create an instance of class Solution. Solution sol; vector<vector<int>> result = sol.countFrequencies(nums); // Print the result as a list of [element, frequency] pairs. cout << "["; for (size_t i = 0; i < result.size(); i++) { if (i > 0) { cout << ", "; } cout << "[" << result[i][0] << ", " << result[i][1] << "]"; } cout << "]\n"; return 0;}Complexity Analysis
Time Complexity: O(N) expected time, where N is the array length. Each frequency update takes expected O(1) time. Collecting the result takes O(K) time for K distinct values, giving O(N + K) = O(N) overall.
Space Complexity: O(K), where K is the number of distinct values. The hash map stores K entries, and the result contains K pairs. In the worst case, every element is distinct, so the space complexity is O(N).
Interview follow-up Questions
Sort the completed pairs by their first value. For K distinct elements, this adds O(K log K) time, making the overall expected time complexity O(N + K log K).
Be the first to add a comment.