Amr and The Large Array (Codeforces 558B)
Tags: Implement, implementation

Amr has got a large array of size n. Amr doesn't like large arrays so he intends to make it smaller.Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.Help Amr by choosing the smallest subsegment possible.

Input: The first line contains one number n (1 ≤ n ≤ 105), the size of the array.The second line contains n integers ai (1 ≤ ai ≤ 106), representing elements of the array.

Output: Output two integers l, r (1 ≤ l ≤ r ≤ n), the beginning and the end of the subsegment chosen respectively.If there are several possible answers you may output any of them. 

Note: A subsegment B of an array A from l to r is an array of size r - l + 1 where Bi = Al + i - 1 for all 1 ≤ i ≤ r - l + 1

Sample Inputs:
5
1 1 2 2 1

5
1 2 2 3 1

6
1 2 2 1 1 2

Sample Outputs:
1 5

2 3

1 5

Solution (Python):
def main():
    n = int(input())
    arr = list(map(int, input().split()))
    temp_dict = {}
    (min_distance, max_occurance, min_distance_l, min_distance_r) = (float('inf'), float('-inf'), 0, 0)
    for (index, element) in enumerate(arr):
        if element in temp_dict:
            temp_dict[element].append(index + 1)
        else:
            temp_dict[element] = [index + 1]
        if len(temp_dict[element]) > max_occurance:
            max_occurance = len(temp_dict[element])
            l = temp_dict[element][0]
            r = temp_dict[element][-1]
            distance = r - l + 1
            min_distance = distance
            min_distance_l = l
            min_distance_r = r
        elif len(temp_dict[element]) == max_occurance:
            l = temp_dict[element][0]
            r = temp_dict[element][-1]
            distance = r - l + 1
            if distance < min_distance:
                min_distance = distance
                min_distance_l = l
                min_distance_r = r
    print(min_distance_l, min_distance_r)
if __name__ == '__main__':
    main()

Solution (Python):
import os, sys, math, bisect
from io import BytesIO, IOBase
from collections import Counter, deque
alphabet = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ'.lower())
MOD = int(1000000000.0 + 7)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
''

def solve():
    n = int(input())
    l = list(map(int, input().split()))
    counter = Counter(l)
    ans = MOD
    l1 = []
    maxn = max(counter.items(), key=lambda item: item[1])[-1]
    out = 0
    out1 = 0
    ''
    d = dict()
    for i in range(n):
        if l[i] not in d:
            d[l[i]] = [i, i]
        else:
            d[l[i]][1] = i
    for i in d:
        if counter[i] == maxn:
            if d[i][1] - d[i][0] < ans:
                ans = d[i][1] - d[i][0]
                out = d[i][0] + 1
                out1 = d[i][1] + 1
    print(out, out1)
if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
_ = input()
nums = [int(i) for i in input().split()]
count = 1
left = 0
right = 0
table = {}
for i in range(len(nums)):
    n = nums[i]
    if n not in table:
        table[n] = [1, i, i]
    else:
        table[n][0] += 1
        table[n][2] = i
        (c, l, r) = table[n]
        size = r - l + 1
        max_size = right - left + 1
        if c > count or (c == count and size < max_size):
            count = c
            left = l
            right = r
print(left + 1, right + 1)