What is the best way to check if ALL values in a range exist in an array? (java)

Question

I have the task of determining whether each value from 1, 2, 3... n is in an unordered int array. I'm not sure if this is the most efficient way to go about this, but I created an int[] called range that just has all the numbers from 1-n in order at range[i] (range[0]=1, range[1]=2, ect). Then I tried to use the containsAll method to check if my array of given numbers contains all of the numbers in the range array. However, when I test this it returns false. What's wrong with my code, and what would be a more efficient way to solve this problem?

public static boolean hasRange(int [] givenNums, int[] range) {
    boolean result = true;
    int n = range.length;
    for (int i = 1; i <= n; i++) {
    if (Arrays.asList(givenNums).containsAll(Arrays.asList(range)) == false) {
           result = false;
     }
   }
    return result;
}

(I'm pretty sure I'm supposed to do this manually rather than using the containsAll method, so if anyone knows how to solve it that way it would be especially helpful!)

Here's where this method is implicated for anyone who is curious:

public static void checkMatrix(int[][] intMatrix) {
    File numberFile = new File("valid3x3") ;
    intMatrix= readMatrix(numberFile);
    int nSquared = sideLength * sideLength;
    int[] values = new int[nSquared];
    int[] range = new int[nSquared];
    int valCount = 0;

    for (int i = 0; i<sideLength; i++) {
        for (int j=0; j<sideLength; j++) {

            values[valCount] = intMatrix[i][j];
            valCount++;
        }
    }

    for (int i=0; i<range.length; i++) {
        range[i] = i+1;
    }

    Boolean valuesThere = hasRange(values, range);

valuesThere is false when printed.

Answer 1

A mathematical approach: if you know the max value (or search the max value) check the sum. Because the sum for the numbers 1,2,3,...,n is always equal to n*(n+1)/2. So if the sum is equal to that expression all values are in your array and if not some values are missing. Example

public class NewClass12 {
   static int [] arr = {1,5,2,3,4,7,9,8};
   public static void main(String [] args){
      System.out.println(containsAllValues(arr, highestValue(arr)));
    }

    public static boolean containsAllValues(int[] arr, int n){        
       int sum = 0;        
       for(int k = 0; k<arr.length;k++){
          sum +=arr[k];
       }
       return (sum == n*(n+1)/2);
    }

   public static int highestValue(int[]arr){
       int highest = arr[0]; 
       for(int i = 0; i < arr.length; i++) {
           if(highest<arr[i]) highest = arr[i];
       }
       return highest;
     }
 }

according to this your method could look like this

public static boolen hasRange (int [] arr){
    int highest = arr[0];
    int sum = 0;
    for(int i = 0; i < arr.length; i++) {
           if(highest<arr[i]) highest = arr[i];
    }
    for(int k = 0; k<arr.length;k++){
          sum +=arr[k];
    }
    return (sum == highest *(highest +1)/2);
} 

Answer 2

The problem with your code is that the function hasRange takes two primitive int array and when you pass primitive int array to Arrays.asList it will return a List containing a single element of type int[]. In this containsAll will not check actual elements rather it will compare primitive array object references.

Solution is either you create an Integer[] and then use Arrays.asList or if that's not possible then convert the int[] to Integer[].

public static boolean hasRange(Integer[] givenNums, Integer[] range) {
    return Arrays.asList(givenNums).containsAll(Arrays.asList(range));
}

Check here for sample code and output.

If you are using ApacheCommonsLang library you can directly convert int[] to Integer[]. Integer[] newRangeArray = ArrayUtils.toObject(range);

Answer 3

public static boolean hasRange(int [] givenNums, int[] range) {
    Set result = new HashSet();

    for (int givenNum : givenNums) {
        result.add(givenNum);
    }

    for (int num : range) {
        result.add(num);
    }

    return result.size() == givenNums.length;
}

Answer 4

Arrays.asList(givenNums).

This does not do what you think. It returns a List<int[]> with a single element, it does not box the values in givenNums to Integer and return a List<Integer>. This explains why your approach does not work.

Using Java 8 streams, assuming you don't want to permanently sort givens. Eliminate the copyOf() if you don't care:

    int[] sorted = Arrays.copyOf(givens,givens.length);
    Arrays.sort(sorted);
    boolean result = Arrays.stream(range).allMatch(t -> Arrays.binarySearch(sorted, t) >= 0);

Answer 5

First style:

if (condition == false) // Works, but at the end you have if (true == false) or such
if (!condition) // Better: not condition

// Do proper usage, if you have a parameter, do not read it in the method.
File numberFile = new File("valid3x3") ;
intMatrix = readMatrix(numberFile);
checkMatrix(intMatrix);

public static void checkMatrix(int[][] intMatrix) {
    int nSquared = sideLength * sideLength;
    int[] values = new int[nSquared];

Then the problem. It is laudable to see that a List or even better a Set approach is the exact abstraction level: going into detail not sensible. Here however just that is wanted.

To know whether every element in a range [1, ..., n] is present.

• You could walk through the given numbers,
• and for every number look whether it new in the range, mark it as no longer new,

• and if n new numbers are reached: return true.

  int newRangeNumbers = 0;
  boolean[] foundRangeNumbers = new boolean[n]; // Automatically false
  

Think of better names.

Answer 6

What I comprehended from your description is that the array is not necessarily sorted (in order). So, we can try using linear search method.

public static void main(String[] args){
    boolean result = true;
    int[] range <- Contains all the numbers
    int[] givenNums <- Contains the numbers to check
    for(int i=0; i<givenNums.length; i++){
        if(!has(range, givenNums[i])){
            result = false;
            break;
        }
    }
    System.out.println(result==false?"All elements do not exist":"All elements exist");
}

private static boolean has(int[] range, int n){
    //we do linear search here
    for(int i:range){
        if(i == n)
        return true;
    }
    return false;
}

This code displays whether all the elements in array givenNums exist in the array range.

Answer 7

One way to solve this is to first sort the unsorted int array like you said then run a binary search to look for all values from 1...n. Sorry I'm not familiar with Java so I wrote in pseudocode. Instead of a linear search which takes O(N), binary search runs in O(logN) so is much quicker. But precondition is the array you are searching through must be sorted.

//pseudocode
int range[N] = {1...n};
cnt = 0;
while(i<-inputStream)
 int unsortedArray[cnt]=i
 cnt++;

sort(unsortedArray);

for(i from 0 to N-1)
{ 
  bool res = binarySearch(unsortedArray, range[i]);
  if(!res)
    return false;
 }

return true;

Answer 8

You say you have a one dimensional array right? Good. Then I think you are thinking to complicated. I try to explain you another way to check if all numbers in an array are in number order.

For instance you have the array with following values:

int[] array = {9,4,6,7,8,1,2,3,5,8};

First of all you can order the Array simpel with

Arrays.sort(array);

After you've done this you can loop through the array and compare with the index like (in a method):

for(int i = array[0];i < array.length; i++){
  if(array[i] != i) return false;