News Leaflets
0 63

Given an array nums[], and integer K and X, the task is to find the most frequent element K positions away from X in the given array.

Examples:

Input: nums = [1, 100, 200, 1, 100], K = 1, X = 1
Output: 100
Explanation: Elements 1 position apart from 1 is only 100.

Input: nums = [2, 2, 2, 2, 3], K = 2, X = 2
Output: X = 2 occurs in indices {0, 1, 2, 3}.
Explanation: Elements 2 position apart are at {2}, {3}, {0, 4}, {1} i.e. 2, 2, {2, 3} and 2.
So 2 occurs 4 times and 3 one time, Therefore 2 is the most frequent element.

Approach: The problem can be solved using the idea of array traversal and storing the elements K distance away from X.

Follow the steps mentioned below to solve the problem:

• Search all occurrences of X in the given array
• For each occurrence of X, store the element at distance K with its frequency in a map
• At the end, just find the element in the map with most frequency and return it.

Below is the implementation of the above approach.

## C++

 ` `  `#include ` `using` `namespace` `std;` ` `  `int` `mostFrequent(vector<``int``>& nums, ` `                 ``int` `K, ``int` `X)` `{    ` `      ` `    ` `    ``map<``int``, ``int``> m;` `    ``for` `(``int` `i = 0; i < nums.size() - K;` `                                     ``i++)` `        ``if` `(nums[i] == X) {` `            ``if` `(m.find(nums[i + K]) ` `                        ``!= m.end())` `                ``m[nums[i + K]]++;` `            ``else` `                ``m.insert({ nums[i + K], 1 });` `            ``if``(i - K >= 0)` `                ``m[nums[i - K]]++;` `        ``}` `     `  `      ` `      ` `    ``int` `ans = 0, count = 0;` `    ``for` `(``auto` `i : m) {` `        ``if` `(i.second > count) {` `            ``ans = i.first;` `            ``count = i.second;` `        ``}` `    ``}` ` `  `    ` `    ``return` `ans;` `}` ` `  `int` `main()` `{` `    ``vector<``int``> nums = { 1, 100, 200, 1, 100 };` `    ``int` `K = 1, X = 1;` ` `  `    ` `    ``cout << mostFrequent(nums, K, X);` `    ``return` `0;` `}`

Time Complexity: O(N)
Auxiliary Space: O(N)