I'm new to programming and it's my first ever question here.

I've been trying to solve this challenge https://www.hackerrank.com/challenges/picking-numbers/problem?isFullScreen=true for three consecutive days but still got 3/10 test cases failed.

Here the algorithm I use:

1. For each element in the main array create a subarray where all elements are equal or no more or less by 1
2. Resulting number of subarrays (which equals to the number of elements in the first array) are checked for validity meaning that each element is equal or no more or less by 1
3. Find the longest valid subarray and return it's size

Here is the code for the solution:

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'pickingNumbers' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY a as parameter.
     */

    public static int pickingNumbers(List<Integer> a) {
        int maxLength = 0;
        boolean isValidArray = false;
        List<Integer> subarray = new ArrayList<Integer>();

        for (int i = 0; i < a.size(); i  ) {
            subarray = findValidSubarray(a, a.get(i));
            isValidArray = arrayValidityCheck(subarray);
            if ((isValidArray) && (subarray.size() > maxLength)) {
                maxLength = subarray.size();
            }
        }
        return maxLength;
    }

    private static List<Integer> findValidSubarray(List<Integer> array, Integer integer) {
        List<Integer> subarray = new ArrayList<Integer>();

        for (int elem : array) {
            if ((elem == integer) || (elem   1 == integer) || (elem == integer   1)) {
                subarray.add(elem);
            }
        }
        return subarray;
    }
//check that all elements are equal or not more or less than 1 to each other
    private static boolean arrayValidityCheck(List<Integer> subarray) {
        boolean isValid = false;

        for (int i = 0; i < subarray.size(); i  ) {
            for (int j = 0; j < subarray.size(); j  ) {
                if ((subarray.get(i) == subarray.get(j)) || (subarray.get(i)   1 == subarray.get(j)) || (subarray.get(i) == subarray.get(j)   1)) {
                    isValid = true;
                } else {
                    isValid = false;
                    break;
                }
            }
            if (!isValid) {
                break;
            }
        }
        return isValid;
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s $", "").split(" ");
        int n = Integer.parseInt(firstMultipleInput[0]);

        List<Integer> a = Stream.of(bufferedReader.readLine().replaceAll("\\s $", "").split(" "))
                .map(Integer::parseInt)
                .collect(toList());
        bufferedReader.close();

        int result = Result.pickingNumbers(a);
        System.out.println(result);
    }
}

Sample test case data which is failing:

100

and

14 18 17 10 9 20 4 13 19 19 8 15 15 17 6 5 15 12 18 2 18 7 20 8 2 8 11 2 16 2 12 9 3 6 9 9 13 7 4 6 19 7 2 4 3 4 14 3 4 9 17 9 4 20 10 16 12 1 16 4 15 15 9 13 6 3 8 4 7 14 16 18 20 11 20 14 20 12 15 4 5 10 10 20 11 18 5 20 13 4 18 1 14 3 20 19 14 2 5 13

Valid answer:

15

My answer:

13

I'm out of ideas where the bug is here. Could you please help me?

PS: I'm aware that this algorithm is not optimal. Any optimization tips would be much appreciated.

CodePudding user response：

Edit: As pointed out in the comments it is sufficient to do one type of check and only check if the other elements are 1 larger than the first element in the check. Answer modified accordingly

Your problem is that when you build your subarray, you allow numbers in it that are both 1 higher and 1 lower than the first element you start with. You then later try to clean up your results by re-validating your generated arrays, but this will not fix the problem that you will not generate any all possible valid subarrays with your method.

My proposal to fix your code would be:

1. Modify your findValidSubarray method so that only allows elements that are 1 higher in it. (The cases where lower numbers would be allowed in will be handled in other iteration when that lower number is the starting element for the iteration)

2. remove the arrayValidityCheck as this one will no longer be needed as the above will directly only produce valid subarrays.

Modified findValidSubarray method:

private static List<Integer> findValidSubarray(final List<Integer> array, final Integer integer) {
    final List<Integer> subarray = new ArrayList<Integer>();
    for (final int elem : array) {
         if ((elem == integer) || (elem   1 == integer)) {
             subarray.add(elem);
         }
    }
    return subarray;
}

Calling that method:

public static int pickingNumbers(final List<Integer> a) {
    int maxLength = 0;
    List<Integer> subarray = new ArrayList<Integer>();

    for (int i = 0; i < a.size(); i  ) {
        subarray = findValidSubarray(a, a.get(i));
        if ((subarray.size() > maxLength)) {
            maxLength = subarray.size();
        }
    }
    return maxLength;
}