1257C - Dominated Subarray - CodeForces Solution


greedy implementation sortings strings two pointers *1200

Please click on ads to support us..

Python Code:

for _ in range(int(input())):
    n = int(input())
    a = input().split()
    d = dict()
    s = len(set(a))

    if 1 < n != s:
        shortest = n

        for i in range(n):
            if a[i] in d and i - d[a[i]] < shortest:
                shortest = i - d[a[i]]

            d[a[i]] = i

        print(shortest + 1)
    else:
        print(-1)

	 	   		      			    	    			

C++ Code:

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long

void hoda()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void solve() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &i: a)cin >> i;
        map<int, vector<int>> mp;
        for (int i = 0; i < n; i++)
            mp[a[i]].push_back(i);
        int ans = 1e9;

        for (const auto &i: mp) {
            for (int j = 0; j + 1 < i.second.size(); j++) {
                ans = min(ans, i.second[j + 1] - i.second[j] + 1);
            }
        }
        if (ans == 1e9)
            cout << -1 << '\n';
        else
            cout << ans << '\n';
    }
}





int main() {
    hoda();
    solve();
    return 0;
}


	  			  		 	  			    		   	  		


Comments

Submit
0 Comments
More Questions

574A - Bear and Elections
352B - Jeff and Periods
1244A - Pens and Pencils
1670A - Prof Slim
1189A - Keanu Reeves
678A - Johny Likes Numbers
1699C - The Third Problem
1697D - Guess The String
754B - Ilya and tic-tac-toe game
760A - Petr and a calendar
1573A - Countdown
166A - Rank List
1631B - Fun with Even Subarrays
727A - Transformation from A to B
822B - Crossword solving
1623A - Robot Cleaner
884B - Japanese Crosswords Strike Back
862B - Mahmoud and Ehab and the bipartiteness
429A - Xor-tree
1675C - Detective Task
950A - Left-handers Right-handers and Ambidexters
672B - Different is Good
1C - Ancient Berland Circus
721A - One-dimensional Japanese Crossword
1715B - Beautiful Array
60B - Serial Time
453A - Little Pony and Expected Maximum
1715A - Crossmarket
1715C - Monoblock
1512C - A-B Palindrome