-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDominatedSubArray.java
More file actions
62 lines (49 loc) · 1.47 KB
/
DominatedSubArray.java
File metadata and controls
62 lines (49 loc) · 1.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.HashMap;
import java.util.Scanner;
public class DominatedSubArray
{
public static void main( String[] args )
{
Scanner s = new Scanner( System.in );
int t = s.nextInt();
while( t-- > 0 )
{
int n = s.nextInt();
int[] A = new int[ n ];
for( int i = 0; i < n; i++ )
A[i] = s.nextInt();
System.out.println( shortestDominatedArray( A, n ) );
}
}
private static int shortestDominatedArray( int[] A, int n )
{
if( n == 1 )
return -1;
HashMap<Integer, String> map = new HashMap<Integer, String>();
int minDist = Integer.MAX_VALUE;
for( int i = 0; i < n; i++ )
{
if( !map.containsKey( A[i] ) )
{
map.put( A[i], i + "_" + Integer.MAX_VALUE );
}
else
{
String[] value = map.get( A[i] ).split( "_" );
int index = Integer.parseInt( value[0] );
int dist = Integer.parseInt( value[1] );
if( dist > i - index )
dist = i - index;
String val = i + "_" + dist;
map.put( A[i], val );
if( dist < minDist )
minDist = dist;
}
}
if( minDist == Integer.MAX_VALUE )
minDist = -1;
else
minDist = minDist + 1;
return minDist;
}
}