Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Algorithm
5.
Code:
6.
Complexity Analysis
6.1.
Time Complexity
6.2.
Space Complexity
7.
Frequently Asked Questions
7.1.
What are sliding windows?
7.2.
Explain the technique involve in the sliding window?
7.3.
What is the DP problem?
7.4.
What are some popular Sliding Window Problems?
7.5.
What are some standard string problems?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Smallest Subarray With All Occurrences of the Most Frequent Element

Author Shiva
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

If you want to have a successful career in the tech field, you really need to have a strong knowledge of Data Structure and Algorithms. In this article, we’ll solve a question that is frequently asked in the technical interview, based on the concept of the Sliding Window, Smallest Subarray With All Occurrences of the Most Frequent Element.

Sliding_Window

The sliding window problem usually involves maintaining a window that complies with the problem limitations is the basic principle. Two pointers, let's say left and right, that point to a certain index in an array or a specific character in the case of a string might be used to represent a window.

Also Read, Byte Array to String

Problem Statement

We have provided an array for the Smallest Subarray With All Occurrences of the Most Frequent Element problem. Consider the n-th element of an array with the highest frequency. You are required to identify the smallest subarray that contains every instance of the number "n" in that subarray, according to the problem description.

Example

Input Array: [1, 5, 3, 5, 3]

Output Array: [5, 3, 5]

Output Explanation: Since there are two frequent elements with the same frequency in this example, the smallest sub-array will be created using the first frequent element.

Algorithm

  • For better optimization, declare two unordered maps i.e. FrqCnt(Frequency_Count) and Cnt; to keep track of elements.
     
  • Put winidx(window_index), mnlen(minimumm_length_counter), and mxfreq(maximum frequency) at 0.
     
  • While 0 < n

    • The frequency of array numbers is counted and stored into the map for each iteration
       
    • Check to see if the frequency of the current element exceeds mxfreq, and if so, take the following action:

      • mxfreq = cnt[a[i]];
         
      • mnlen = i – frqCnt[a[i]] + 1;
         
      • winidx = frqCnt[a[i]];
         
    • Otherwise, if the highest frequency matches the frequency of the current element and the length of the subarray so produced is less than the minlen, then take the following action:

      • mnlen = i – frqCnt[a[i]] + 1;
         
      • winidx = frqCnt[a[i]];
         
  • print the array from (winidx) to (winidx + minlen).

 

Algorithm Walkthrough

Starting Point:

Update the Data Structure and variables as we encounter element while we iterate:

The Length of the Element is calculated by: ending point - starting point + 1

Here we have 2 valid answers i.e. 5,3,5 and 3,5,3, we can return any or the first one depending on the question:

Code:

C++ Solution:

/* Solution of Smallest Subarray With All Occurrences of the Most Frequent Element */
#include<bits/stdc++.h>
using namespace std;

void smallestfrequentSubArray(vector<int>& a) {
	int n = a.size();
	unordered_map<int, int> frqCnt;
	unordered_map<int, int> cnt;
	int mxFrq = 0;
	int mnln, winidx;

	for (int i = 0; i < n; i++) {
		if (cnt[a[i]] == 0) {
			frqCnt[a[i]] = i;
			cnt[a[i]] = 1;
		}
		else
			cnt[a[i]]++;
		if (cnt[a[i]] > mxFrq) {
			mxFrq = cnt[a[i]];
			mnln = i - frqCnt[a[i]] + 1;
			winidx = frqCnt[a[i]];
		}
		else if (cnt[a[i]] == mxFrq && i - frqCnt[a[i]] + 1 < mnln) {
			mnln = i - frqCnt[a[i]] + 1;
			winidx = frqCnt[a[i]];
		}
	}
	
	for (int i = winidx; i < winidx + mnln; i++)
		cout << a[i] << " ";
}

int main() {
	vector<int> arr{ 1, -5, 4, 6, -5, 1 };
	smallestfrequentSubArray(arr);
	return 0;
}

 

Output: 

output

Java Solution: 

/* Solution of Smallest Subarray With All Occurrences of the Most Frequent Element. */
import java.io.*;
import java.util.*;

class HelloWorld {
	public static void smallestfrequentSubArray(int a[], int n) {
		HashMap<Integer, Integer> frqCnt= new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> cnt= new HashMap<Integer, Integer>();
		int mxFrq = 0;
		int mnln = -1, winidx = -1;
		
		for (int i = 0; i < n; i++) {
			if (cnt.containsKey(a[i])) {
				cnt.put(a[i], cnt.get(a[i]) + 1);
			}
			else {
				frqCnt.put(a[i], i);
				cnt.put(a[i], 1);
			}
			if (cnt.get(a[i]) > mxFrq) {
				mxFrq = cnt.get(a[i]);
				mnln = i - frqCnt.get(a[i]) + 1;
				winidx = frqCnt.get(a[i]);
			}
			else if ((cnt.get(a[i]) == mxFrq) && (i - frqCnt.get(a[i]) + 1 < mnln)) {
				mnln = i - frqCnt.get(a[i]) + 1;
				winidx = frqCnt.get(a[i]);
			}
		}
		
		for (int i = winidx; i < winidx + mnln; i++)
			System.out.print(a[i] + " ");
	}
	
	public static void main(String[] args) {
		int arr[] = { 1, -5, 4, 6, -5, 1 };
		smallestfrequentSubArray(arr, arr.length);
	}
}

 

Output: 

output

Python Code:

#Solution of Smallest Subarray With All Occurrences of the Most Frequent Element 
# Python3 implementation to find smallest subarray with all occurrences of a most frequent element

def smallestArray(a, n):
	# To store left most occurrence of elements
	left = dict()
	# To store counts of elements
	cnt = dict()
	# To store maximum frequency
	max = 0
	# To store length and starting index of smallest result window
	min, stridx = 0, 0
	
	for i in range(n):
		x = a[i]
		# First occurrence of an element, store the index
		if (x not in cnt.keys()):
			left[x] = i
			cnt[x] = 1
			
		# increase the frequency of elements
		else:
			cnt[x] += 1
	
		# Find maximum repeated element and store its last occurrence and first occurrence
		if (cnt[x] > max):
			max = cnt[x]
			min = i - left[x] + 1 # length of subsegment
			stridx = left[x]
			
		# select subsegment of smallest size
		elif (cnt[x] == max andi - left[x] + 1 < min):
			min = i - left[x] + 1
			strindex = left[x]
	
	# Print the subsegment with all occurrences of a most frequent element
	for i in range(stridx, stridx + min):
		print(a[i], end = " ")

A = [1, 4, 4, 4, 3]
n = len(A)
smallestArray(A, n)

 

Output:

output

Complexity Analysis

Time Complexity

O(N): Where ‘N’ stands for the length of the array as provided in the problem statement of Smallest Subarray With All Occurrences of the Most Frequent Element.

Reason: O(n), where "n" is the array's length. Cause there is only one loop. Assuming the time complexity of the methods os HashSet is O(1).

Space Complexity

O(n):  “n” -> Where ‘n’ stands for the length of the array as provided in the problem statement of Smallest Subarray With All Occurrences of the Most Frequent Element.

Reason: In the worst-case scenario, HashSet can fill up O(N) space i.e. the length of the array.

Check out this problem - Subarray With 0 Sum

Frequently Asked Questions

What are sliding windows?

Sliding window problems are regularly asked in software engineering interviews. Although the method for solving them is very different from the method used to solve tabulation or memoization questions, they are a subset of questions involving dynamic programming.

Explain the technique involve in the sliding window?

Using a single loop instead of a nested loop is a computational technique known as the "window sliding technique" that tries to reduce the complexity of the computation's time requirements.

What is the DP problem?

Dynamic programming, often known as DP, is an algorithmic technique for solving problems by recursively dividing them into easier subproblems and taking advantage of the fact that the best solution to the whole problem depends on the best solution to each of its individual subproblems.

What are some popular Sliding Window Problems?

Here is the list of some standard sliding window problems:

  • Identify the longest substring of a string with k different characters.
  • Find every string's substrings that are combinations of other strings.
  • Identify the longest substring of a string with unique characters.
  • locate the smallest sum subarray of size k.

What are some standard string problems?

Here is the list of some standard string problems:

  • reverse a given string in place
  • print duplicate characters from a string
  • check if two strings are anagrams of each other 
  • find all the permutation of string
  • string be reversed using recursion

Conclusion

In this article, we have discussed a standard Sliding Window Question: Smallest Subarray With All Occurrences of the Most Frequent Element, in multiple programming languages.

Here are some more Sliding Window Questions:

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.
Do upvote our blog to help other ninjas grow.
Happy Learning!

codingNinja__thank_you
Live masterclass