PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given an array A, find the shortest subarray consisting of exactly two distinct elements; or claim that no such subarrays exist.
EXPLANATION:
If A contains two adjacent elements that are not equal, we can simply take the subarray consisting of those two elements - it has length 2 and two distinct elements, so the answer will be 2 (and it’s clearly not possible to do any better).
What if A doesn’t contain adjacent unequal elements?
This would mean that all the elements of A are equal, which in turn means every subarray has only one distinct element.
So, the answer is -1 in this case.
This gives us a simple solution: if all the elements of A are equal, print -1, otherwise print 2.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if min(a) == max(a): print(-1)
else: print(2)