Most Frequent Adjacent Pairs

Moderate

0/80

1 upvote

Asked in company

Problem statement

You are given an array 'arr' of length 'n', consisting of integers. An adjacent pair in the array is a sequence of two consecutive elements, i.e., {arr[i], arr[i+1]} for 0 <= i < n-1.

Your task is to find the adjacent pair that appears most frequently in the array. If there are multiple pairs with the same maximum frequency, you can return any one of them. The output should be the two integers forming the most frequent pair.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'n', representing the size of the array.

The second line contains 'n' space-separated integers, representing the elements of the array 'arr'.

Output Format:

Print two space-separated integers representing the most frequent adjacent pair. For instance, if the most frequent pair is {x, y}, the output should be x y.

Note:

If multiple pairs share the same highest frequency, any of these pairs is an acceptable answer.

An array of size 'n' will have 'n-1' adjacent pairs.

Sample Input 1:

10
1 2 2 3 2 3 4 4 4 4

Sample Output 1:

4 4

Explanation for Sample 1:

The adjacent pairs in the array and their frequencies are:
{1, 2}: 1 time
{2, 2}: 1 time
{2, 3}: 2 times
{3, 2}: 1 time
{3, 4}: 1 time
{4, 4}: 3 times
The pair {4, 4} has the highest frequency of 3.

Sample Input 2:

7
10 20 10 20 10 30 40

Sample Output 2:

10 20

Explanation for Sample 2:

The adjacent pairs and their frequencies are:
{10, 20}: 2 times
{20, 10}: 2 times
{10, 30}: 1 time
{30, 40}: 1 time
The pairs {10, 20} and {20, 10} both have the maximum frequency of 2. Either 10 20 or 20 10 would be a correct answer.

Expected Time Complexity:

The expected time complexity is O(n), where 'n' is the size of the array.

Constraints:

2 <= 'n' <= 10^5
-10^9 <= 'arr[i]' <= 10^9

Approaches (1)

Approach 1

Most Frequent Adjacent Pairs

Time Complexity

The expected time complexity is O(n), where 'n' is the size of the array.

Space Complexity

(100% EXP penalty)

Most Frequent Adjacent Pairs

Console