0
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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);
} 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.