Leetcode 2190: Most Frequent Number Following Key In an Array
You are given an integer array ’nums’ and an integer ‘key’, which is present in ’nums’. Your task is to find the integer that most frequently appears immediately after an occurrence of ‘key’ in the array. In other words, count how many times each integer follows ‘key’ and return the integer that appears the most.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array 'nums' and an integer 'key'.
Example: Input: nums = [3,1,2,3,4,3,5], key = 3
Constraints:
• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
Output: Return the integer that follows 'key' the most times in the array. The answer will be unique.
Example: Output: 3
Constraints:
• The test cases will be generated such that the answer is unique.
Goal: The goal is to find the integer that follows 'key' the most times in the array.
Steps:
• Iterate through the array and count how many times each integer appears immediately after an occurrence of 'key'.
• Keep track of the integer that has the highest count.
Goal: Conditions that the solution must satisfy.
Steps:
• The length of the nums array is between 2 and 1000.
• Each element in nums is between 1 and 1000.
Assumptions:
• The array contains at least one occurrence of 'key'.
• The solution must find the target with the maximum frequency efficiently.
• Input: Input: nums = [3,1,2,3,4,3,5], key = 3
• Explanation: In the array, '3' is followed by '1' at index 1, by '4' at index 3, and by '5' at index 5. '3' appears 3 times, while no other integer follows 'key' as frequently. Thus, the output is 3.
• Input: Input: nums = [2,5,2,3,5,2], key = 2
• Explanation: In the array, '2' is followed by '5' at index 1, '3' at index 3, and another '5' at index 4. '5' follows '2' twice, while no other integer follows 'key' as frequently. Hence, the output is 5.
Approach: To solve this problem, we will iterate through the array and count how often each integer follows an occurrence of 'key', then return the integer with the maximum count.
Observations:
• This problem can be solved by iterating through the array and maintaining a count of the occurrences of each integer that follows 'key'.
• We can use a hash map or array to store the frequency of each integer following 'key' and then find the integer with the highest frequency.
Steps:
• Initialize a counter for each integer that follows 'key'.
• Loop through the array, and whenever 'key' is found, increment the counter for the next integer.
• Return the integer with the highest count.
Empty Inputs:
• There will always be at least one element after 'key', so empty inputs are not a concern.
Large Inputs:
• Ensure the solution works for arrays of size 1000.
Special Values:
• All elements in the array could be the same, or 'key' might be the last element, in which case no other element can follow it.
Constraints:
• The solution should be efficient and work within the given constraints.
int mostFrequent(vector<int>& nums, int key) {
int cnt[1001] = {}, res = 0;
for (int i = 1; i < nums.size(); ++i)
if (nums[i - 1] == key && ++cnt[nums[i]] > cnt[res])
res = nums[i];
return res;
}
1 : Function Definition
int mostFrequent(vector<int>& nums, int key) {
Defines the function 'mostFrequent' which takes a vector of integers 'nums' and an integer 'key' as inputs, and returns the most frequent number after occurrences of 'key'.
2 : Variable Initialization
int cnt[1001] = {}, res = 0;
Initializes an array 'cnt' to store frequencies of numbers, and a variable 'res' to track the most frequent number.
3 : Loop
for (int i = 1; i < nums.size(); ++i)
Starts a loop from the second element of the vector 'nums' to check each number and count its occurrences after the key.
4 : Condition Check
if (nums[i - 1] == key && ++cnt[nums[i]] > cnt[res])
Checks if the previous element in the array is equal to 'key' and if the frequency of the current element is greater than the current 'res'. If true, update 'res'.
5 : Update Result
res = nums[i];
Updates the result 'res' to the current number 'nums[i]' if it appears more frequently after 'key'.
6 : Return Statement
return res;
Returns the most frequent number after occurrences of 'key' from the vector 'nums'.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the input array, because we only need to iterate through the array once.
Best Case: O(m)
Worst Case: O(m)
Description: The space complexity is O(m), where m is the number of distinct integers that follow 'key'. This is the space used for counting occurrences.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus