educative.io

There is no way O(N^3) is an optimum solution here. Can someone review my sample code?

Courses
,
#1

if (input.length == 0 || target == 0)

        throw new IllegalArgumentException();

    List<List<Integer>> result = new ArrayList();

    for (int i = 0; i < input.length; i++) {

        int rightpointer = input.length - 1 - i;

        int runningProductSum = 1 * input[rightpointer];

        while (runningProductSum < target) {

            if (runningProductSum < target && !result.contains(Arrays.asList(input[rightpointer]))) {

                result.add(Arrays.asList(input[rightpointer]));

                if (rightpointer - 1 < 0) {

                    return result;

                }

                int currentValue = input[rightpointer] * input[rightpointer - 1];

                if (rightpointer <= input.length - 1 && currentValue < target) {

                    result.add(Arrays.asList(input[rightpointer - 1], input[rightpointer]));

                }

            }

            rightpointer--;

            runningProductSum = runningProductSum * input[rightpointer];

        }

    }

    return result;
#2

@Emmanuel_Amadi

Kindly provide your complete code to verify the correctness, other than that logic of your code seems fine.

1 Like
#3

public static List<List> productLessThanTarget(int[] input, int target) {
List<List> result = new ArrayList<List>();
int i = 0, j = 0, product = 1;
List runningSubArray = new ArrayList();

    while (j < input.length) {
        product *= input[j];
        runningSubArray.add(input[j]);
        while (i <= j && product >= target) {
            product /= input[i++];
            runningSubArray.remove(0);
        }
        result.add(Arrays.asList(input[j]));

        if (runningSubArray.size() > 1)
            result.add(new ArrayList<>(runningSubArray));

        j++;
    }

    return result;
}
#4

Yes, your solution is correct.

Happy learning :slight_smile:

1 Like