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.
So the answer is 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++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find most frequent elementint mostFrequent(vector<int>& nums, int K, int X){ // Take one map to store count of // frequent element 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]]++; } // Initialize variable ans to store // most frequent element int ans = 0, count = 0; for (auto i : m) { if (i.second > count) { ans = i.first; count = i.second; } } // Return ans return ans;}// Driver codeint main(){ vector<int> nums = { 1, 100, 200, 1, 100 }; int K = 1, X = 1; // Function call cout << mostFrequent(nums, K, X); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.HashMap;import java.util.Map;class GFG { // Function to find most frequent element static int mostFrequent(int[] nums, int K, int X) { // Take one map to store count of // frequent element HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length - K; i++) if (nums[i] == X) { if (m.containsKey(nums[i + K])){ m.put(nums[i + K], m.get(nums[i + K]) + 1 ); } else m.put( nums[i + K], 1 ); if(i - K >= 0){ if(m.containsKey(nums[i - K])) m.put(nums[i - K], m.get(nums[i - K]) + 1); } } // Initialize variable ans to store // most frequent element int ans = 0, count = 0; for (Map.Entry<Integer, Integer> e : m.entrySet()){ if(e.getValue() > count){ ans = e.getKey(); count = e.getValue(); } } // Return ans return ans; } // Driver code public static void main (String[] args) { int[] nums = { 1, 100, 200, 1, 100 }; int K = 1, X = 1; // Function call System.out.print(mostFrequent(nums, K, X)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python3 code to implement the above approach# function to find the most frequent elementdef mostFrequent(nums, K, X): # a dictionary/map to store the counts of frequency m = dict() for i in range(len(nums) - K): if nums[i + K] in m: m[nums[i + K]] += 1 else: m[nums[i + K]] = 1 if (i - K >= 0): if (nums[i - K] in m): m[nums[i - K]] += 1 else: m[nums[i - K]] = 1 # initialize variable answer to store the # most frequent element ans = 0 count = 0 for i in m: if m[i] > count: ans = i count = m[i] # return ans return ans# Driver Codenums = [1, 100, 200, 1, 100]K = 1X = 1# Function Callprint(mostFrequent(nums, K, X))# This code is contributed by phasing17 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { // Function to find most frequent element static int mostFrequent(int[] nums, int K, int X) { // Take one map to store count of // frequent element Dictionary<int, int> m = new Dictionary<int, int>(); for (int i = 0; i < nums.Length - K; i++) if (nums[i] == X) { if (m.ContainsKey(nums[i + K])) m[nums[i + K]] = m[nums[i + K]] + 1; else m.Add(nums[i + K], 1); if (i - K >= 0 && m.ContainsKey(nums[i - K])) { m[nums[i - K]] = m[nums[i - K]] + 1; } } // Initialize variable ans to store // most frequent element int ans = 0, count = 0; foreach(KeyValuePair<int, int> x in m) { if (x.Value > count) { ans = x.Key; count = x.Value; } } // Return ans return ans; } // Driver code public static void Main() { int[] nums = { 1, 100, 200, 1, 100 }; int K = 1, X = 1; // Function call Console.Write(mostFrequent(nums, K, X)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code to implement the approach // Function to find most frequent element const mostFrequent = (nums, K, X) => { // Take one map to store count of // frequent element let m = {}; for (let i = 0; i < nums.length - K; i++) if (nums[i] == X) { if (nums[i + K] in m) m[nums[i + K]]++; else m[nums[i + K]] = 1; if (i - K >= 0) if (nums[i - K] in m) m[nums[i - K]]++; else m[nums[i - K]] = 1; } // Initialize variable ans to store // most frequent element let ans = 0, count = 0; for (let i in m) { if (m[i] > count) { ans = i; count = m[i]; } } // Return ans return ans; } // Driver code let nums = [1, 100, 200, 1, 100]; let K = 1, X = 1; // Function call document.write(mostFrequent(nums, K, X));// This code is contributed by rakeshsahni</script> |
Output
100
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
