1208B - Uniqueness - CodeForces Solution

binary search brute force implementation two pointers *1500

Please click on ads to support us..

Python Code: 


def works(x):
    curr = rep
    freq_ = freq.copy()
    for i in range(x):
        freq_[a[i]] -= 1
        if freq_[a[i]] == 1:
            curr -= 1

    if curr == 0:
        return True

    for i in range(x, n):
        freq_[a[i-x]] += 1
        if freq_[a[i-x]] == 2:
            curr += 1
        freq_[a[i]] -= 1
        if freq_[a[i]] == 1:
            curr -= 1
        if curr == 0:
            return True

    return False


n = int(input())

a = list(map(int, input().split()))

rep = 0
freq = {}
for i in range(n):
    if a[i] not in freq:
        freq[a[i]] = 0
    freq[a[i]] += 1
    if freq[a[i]]==2:
        rep += 1

left = 0
right = n
while left < right:
    mid = (left+right)//2
    if works(mid):
        right = mid
    else:
        left = mid+1

print(left)

C++ Code: 

#include<bits/stdc++.h>
#include<queue>
#define ll long long
using namespace std;
const int mod=1e9+7;

int main(){
    

        ll n ;
        cin>>n;

        ll arr[n];
        for(ll i=0 ; i<n ; i++) cin>>arr[i] ;

        map<ll,ll> mp ;

        ll ans = INT_MAX ;

        for(ll i=0 ; i<n ; i++){

                if(mp[arr[i]] > 0) {
                            break ;
                }

                mp[arr[i]]++ ;

                map<ll,ll> mp2 = mp ;

                ll j = n-1 ;
                for(j=n-1 ; j>i ; j--){

                        if(mp2[arr[j]] > 0){
                            break ;
                        }

                        mp2[arr[j]]++;
                }

                ans = min(ans , j-i) ;
                
        }


        mp.clear() ;

        for(ll i=n-1 ; i>=0 ; i--){

                if(mp[arr[i]] > 0) {
                            break ;
                }

                mp[arr[i]]++ ;

                map<ll,ll> mp2 = mp ;

                ll j = 0 ;
                for(j=0 ; j < i ; j++){

                        if(mp2[arr[j]] > 0){
                            break ;
                        }

                        mp2[arr[j]]++;
                }

                ans = min(ans ,i-j) ;
                
        }

        cout<<ans<<endl;
       
}


Comments

Submit
0 Comments
More Questions

1221. Split a String in Balanced Strings
1002. Find Common Characters
1602A - Two Subsequences
1555A - PizzaForces
1607B - Odd Grasshopper
1084A - The Fair Nut and Elevator
1440B - Sum of Medians
1032A - Kitchen Utensils
1501B - Napoleon Cake
1584B - Coloring Rectangles
1562B - Scenes From a Memory
1521A - Nastia and Nearly Good Numbers
208. Implement Trie
1605B - Reverse Sort
1607C - Minimum Extraction
1604B - XOR Specia-LIS-t
1606B - Update Files
1598B - Groups
1602B - Divine Array
1594B - Special Numbers
1614A - Divan and a Store
2085. Count Common Words With One Occurrence
2089. Find Target Indices After Sorting Array
2090. K Radius Subarray Averages
2091. Removing Minimum and Maximum From Array
6. Zigzag Conversion
1612B - Special Permutation
1481. Least Number of Unique Integers after K Removals
1035. Uncrossed Lines
328. Odd Even Linked List