Find the shortest sub array that contains all element from 1 to K

Question 1

I’m trying to solve this problem here. The question is all about finding the shortest sub array inside an array that contains all the element from 1 to K.

Input:

The first line contains three space-separated integers N, K and Q. N is the length of actual Array, we need to find the shortest sub-array that contains all the element from 1 to K and Q is the number of queries.
The second line contains N space-separated integers A1,A2,…,AN (the content for actual array).

There are two types of queries:

Type 1 : 1 u v -> Update the value at position u to v.
Type 2 : 2 -> Find the length of the shortest contiguous subarray which contain all the integers from 1 to K.

I wrote this code here, which I believe is efficient enough to be completed before desired time.

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef {
    
    private static int findShortestContiguousSubArray(int[] array, int k) {

        Map<Integer, Integer> mapElementAndCount = new HashMap<>();

        for (int i = 1; i <= k; i++) {
            mapElementAndCount.put(i, 1);
        }

        int count = k;
        int cursor = 0;
        int start = 0;
        int minLength = Integer.MAX_VALUE;

        while (cursor < array.length) {

            if (mapElementAndCount.containsKey(array[cursor])) {
                mapElementAndCount.put(array[cursor], mapElementAndCount.get(array[cursor]) - 1);
                if(mapElementAndCount.get(array[cursor]) == 0) {
                    count--;
                }
            }

            while (start < array.length && count == 0) {

                if (minLength > cursor - start + 1) {
                    minLength = cursor - start + 1;
                }

                if(mapElementAndCount.keySet().contains(array[start])) {

                    mapElementAndCount.put(array[start], mapElementAndCount.get(array[start]) + 1);

                    if(mapElementAndCount.get(array[start]) == 1) {
                        count++;
                    }
                }

                start++;
            }

            cursor++;
        }

        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
    
    public static void main (String[] args) throws java.lang.Exception {
        
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        String firstLine = input.readLine();
        String[] instructions = firstLine.trim().split(" ");

        int n = Integer.parseInt(instructions[0]);
        int k = Integer.parseInt(instructions[1]);
        int q = Integer.parseInt(instructions[2]);

        String[] stringArray = input.readLine().trim().split(" ");
        int[] array = new int[stringArray.length];

        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(stringArray[i]);
        }

        while (q > 0) {
            
            Integer.parseInt(instructions[0]);

            String query = input.readLine();
            instructions = query.trim().split(" ");

            if (instructions.length == 1) {
                System.out.println(findShortestContiguousSubArray(array, k));
            } else if (instructions.length == 3) {

                int targetIndex = Integer.parseInt(instructions[1]) - 1;

                if (targetIndex >= array.length || targetIndex < 0) {
                    q--;
                    continue;
                }

                array[targetIndex] = Integer.parseInt(instructions[2]);
                System.out.println();
            }

            q--;
        }
    }
}

Explanation:

I’ve created a map where I stored count 1 for each element in the range 1 to K (including K). After that I’m traversing the actual array and whenever I encounter an element which is there in the map, I reduce the value by 1 and reducing the count variable by 1 (I mean if the count of an element has become zero, I need to find K-1 rest elements in the range). And when the count variable becomes 0, which means I’ve found a sub array that contains all the element from 1 to K, then I compare it to the last encountered sub-array size (for the first time, I set it to Integer.MAX_VALUE) and I modify the size if I encounter small sub-array.

PROBLEM:

After submitting the code, it’s showing time limit exceeded.

If this algorithm is fine, what is the problem in the code?

If this algorithm is not the best way to solve this problem, what else could be done (A brief demonstration of the algorithm would be sufficient)?

I’m asking question on this platform for the first time, so may be I’m not doing this in the best possible way. Please suggest the edit, I’ll fix it.

Thank you in advance!

Question 2

This is not a complete answer with an algorithm or an implementation solving the challenge, but a hint at where to improve the approach.

Algorithm

You are using a straightforward algorithm, and programming challenges are called “challenges” as typically you need to come up with a better approach than the straightforward one.

Your find() algorithm is O(n²), and you’re repeatedly doing that very same algorithm for every Type 2 query. There might be a better find() algorithm in itself.

And there might be an incremental approach, taking into account that the Type 1 queries only change a single array element, thus allowing the find() to re-use some partial results from previous runs.

Code Style

In addition, as this is Code Review, some hints on Java style (I know, programming challenges don’t ask for production-quality code, but anyway…).

    int cursor = 0;
    // ...
    while (cursor < array.length) {
        // ...
        cursor++;
    }

This is a simple loop counting from 0 up to array.length. That should be written as

    for (int cursor = 0; cursor < array.length; cursor++) {
        // ...
    }

Although your version does exactly the same, by spreading the code parts that make up the loop over many lines of code, it’s hard to see the “simple loop” structure. Similarly, in the while (q > 0) { ... } you even have multiple places where you decrement q (because of the continue statement). With a for loop, you’d avoid that as well.

You can replace

            if (minLength > cursor - start + 1) {
                minLength = cursor - start + 1;
            }

by

            minLength = Math.max(minLength, cursor - start + 1);

The import staments should be changed.

import java.util.*;
import java.lang.*;
import java.io.*;

First of all, there’s no need to import anything from the java.lang package, as classes from that package are always visible with their simple name (implicitly being imported).

Then, I recommend not to use wildcard imports, but to import the classes you need individually.

Why? Imagine, at Java 7 times you created a class my.package.utils.IntStream to read files of integers, and you used the wildcard import style:

import java.util.*;
import java.io.*;
import my.package.utils.*;

Before Java8, there was no java.util.IntStream interface, so your code compiled perfectly. But with the introduction of Java8, suddenly your my.package.utils.IntStream class collides with the java.util.IntStream interface, both wildcard-imported, and the compiler can’t decide which one to choose if you write IntStream somewhere in your code. The introduction of a new interface into the Java library, an interface you never intended to use, suddenly breaks your code.

Had you written individual imports for only the classes you really need, the java.util.IntStream wouldn’t bother you.

As a guideline for imports:

Have your IDE manage the import statements for you.
Make sure the IDE settings use individual imports, not wildcards.
Import only the classes you really need.

Algorithm

Code Style

Leave a Reply Cancel reply