Check if array contains contiguous integers with duplicates allowed in Java

Question

Given an array of n integers(duplicates allowed). Print "Yes" if it is a set of contiguous integers else print "No".

INPUT: The first line consists of an integer T i.e. the number of test cases. First line of each test case consists of an integer n, denoting the size of array. Next line consists of n spaced integers, denoting elements of array.

OUTPUT: Print "Yes" if it is a set of contiguous integers else print "No".

CONSTRAINTS: 1<=T<=100 1<=n<100000 a[i]<=105

Example:

2
8
5 2 3 6 4 4 6 6
7
10 14 10 12 12 13 15

Output : Yes No

Explanation: Test Case 1 : The elements of array form a contiguous set of integers which is {2, 3, 4, 5, 6} so the output is Yes. Test Case 2: We are unable to form contiguous set of integers using elements of array.

My approach:

/*package whatever //do not write package name here */
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class GFG {
 private static void checkContig (int [] arr, int n)
 {
 Set <Integer> set = new HashSet <>();
 for (int elem:arr)
 {
 set.add(elem);
 }
 List <Integer> arrNoReps = new ArrayList <>();
 arrNoReps.addAll(set);
 Collections.sort(arrNoReps);
 int first = arrNoReps.get(0);
 int last = first + arrNoReps.size() - 1;
 for (int i = first; i <= last; i++)
 {
 if( !arrNoReps.contains(i))
 {
 System.out.println("No");
 return;
 }
 }
 System.out.println("Yes");
 }
 public static void main (String[] args) throws IOException {
 BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
 String line = br.readLine();
 int T = Integer.parseInt(line);
 String line2;
 String line3;
 String [] inps;
 int n;
 for (int i = 0; i < T; i++)
 {
 line2 = br.readLine();
 n = Integer.parseInt(line2);
 int [] arr = new int[n];
 line3 = br.readLine();
 inps = line3.split(" ");
 // System.out.println(n);
 for (int j = 0; j < n; j++)
 {
 arr[j] = Integer.parseInt(inps[j]);
 //System.out.println(inps[j]);
 }
 checkContig(arr,n);
 }
 }
}

I have the following questions with regards to the code written above:

1) Does there exist a smarter way to solve this question?

2) Am I violating some serious Java coding conventions?

3) How can I improve my time and space complexity?

4) Can I use some different data structures which can solve the question faster?

Source

Answer 1

Code. Separate the business logic from the IO. checkContig shall not print anything, but only return a success/failure indication. Printing is up to a caller.

Algorithm. arrNoReps.contains(i) fails to take into account the fact that arrNoReps is already sorted, effectively leading to a quadratic complexity. If the array is sorted, you can test its contiguity in a linear time:

 for (i = 1; i < arr.size(); i++) {
 if (arr[i] - arr[i-1] != 1) {
 return false;
 }
 }
 return true;

Notice that the same logic is applicable to the sorted array with repetitions. A difference between to successive elements in a sorted array is either 0 (a dupe), or 1 (contiguity maintained), or any other positive number (contiguity broken), so

 for (i = 1; i < arr.size(); i++) {
 if (arr[i] - arr[i-1] > 1) {
 return false;
 }
 }
 return true;

which means that the conversion to the set and back to array is quite redundant.

Answer 2

Apart from the suggestions given by @vnp, you can also try the logic with Java 8 Streams.

private static boolean isContiguous(List<Integer> numbers) {
 List<Integer> sortedDistinct = numbers.stream()
 .distinct()
 .sorted()
 .collect(Collectors.toList());
 return IntStream.range(1, sortedDistinct.size())
 .noneMatch(i -> sortedDistinct.get(i) - sortedDistinct.get(i - 1) > 1);
}