Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

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.

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.

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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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:

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:

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:

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.

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:

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.