Home > Enterprise >  How to get index in Java array that defines start and end of available space
How to get index in Java array that defines start and end of available space

Time:02-24

So I tried searching for how to solve this issue I'm having. I need some sort of way in Java to go through an array and find slots (indexes) where it's empty (zeros) so for example I have this array:

int[] arr = {1,1,0,0,0,0,0,1,0,0};

So I want to for example get out two values from here. If my objSize (see below) is 4. I want to get the array index of 2 and 6 since the size of objSize will fit there. These indexes specify space between that is available. I can't really seem to figure this out.

for (int x = 0; x < matrix.length; x  ) {
    if (arr[x] == 0) {
        start = col;
        if (start == objSize) {
            stop = col;
        }
    } else {
        start = 0;
    }
}

How can I do this? I've made an attempt that doesn't work for obvious reasons.

CodePudding user response:

Well, first off I don't really understand your intentions behind the code you already submitted, so it is hard to just improve on it. Instead, I am going to walk you through a similar solution, which is the following.

int objsize = 4;
int[] arr = {1,1,0,0,0,0,0,1,0,0};
int start = 0;
int stop = 0;
for(int i = 0; i < arr.length - 1; i  ) {
    if(arr[i] != 0){
        start = i;
        stop = i;
        continue;
    } else {
        stop  ;
        if(stop-start >= objsize) {
            break;
        }
    }
}

When looking for a sequence in an array, that matches a given condition (in your case 4 consecutive 0 values) you should have two "pointers" for your start and stop value, where the stop value could be the i/the current array pointer as well. Then you go sequentially through your array and have two general cases:

  1. The value at your current index doesn't match your condition of being 0, so you reset your start and stop pointer to the current position in the array and continue.
  2. Your current index matches the condition. In this case, you leave the starting pointer where it last didn't match the condition and move your stop-pointer forward. If then your finishing criteria of 4 consecutive 0 values is matched, you can leave the for loop over the array.

In the code provided above, the returned/final start and stop value are:

  • start: exclusively indexed
  • stop: inclusively indexed.

You said you expected the values returned to be 2 and 6, as this would be the longest concurrent series of 0 values. But as the criteria of 4 consecutive values is already matched at 2 and 5, the code above delivers those values, but can easily be adopted to return the full consecutive sequence.

CodePudding user response:

to go through an array and find slots (indexes) where it's empty (zeros)

In order to find all the slots in the given array, you need a container to store them. A plain array isn't applicable here, because you have to provide the length and it's not possible to know how many slots there are in the given array. For that purpose, we can use ArrayList which utilizes array under the hood and grows gradually while elements are being added into it.

And because each slot is comprised of two values we need an object that encapsulates them. There are two options here: it could be easier a class or record (available since Java 16). And it will look like that:

public record Slot(int start, int end) {
    public int getSize() {
        return end - start;
    }
}

The class below is absolutely identical in terms of functionality. Constructor, getters, equals(), hashCode(), toString() are provided to a record implicitly, but if your choice is class then you have to declare them yourself). Meanwhile with record you need to declare only a custom method getSize().

public class Slot {
    private final int start;
    private final int end;

    public Slot(int start, int end) {
        this.start = start;
        this.end = end;
    }

    public int getSize() {
        return end - start;
    }

    // getters, equals(), hashCode(), toString()
}

To implement this algorithm only one local variable start is needed. It's convenient to initialize it will -1 because this illegal position in the array. Therefore it's easy to distinguish the default value of start and beginning of a slot.

The end of the slot will be the first occurrence of the 1 when start != -1. When the end is found a new instance of the Slot is being created and added to the list.

The case when the given array contains a slot at the end must be treated separately after the loop.

A ternary operator start == -1 ? x : start; that is used to update the value of start is an equivalent of if (start == -1) start = x;.

public static void main(String[] args) {
    int[] arr = {1,1,0,0,0,0,0,1,0,0};

    List<Slot> slots = new ArrayList<>();
    int start = -1;
    for (int x = 0; x < arr.length; x  ) {
        if (arr[x] == 0) {
            start = start == -1 ? x : start;
        } else if(start != -1) {
            slots.add(new Slot(start, x));
            start = -1;
        }
    }
    // adding the last slot at the end of array
    if(start != -1) {
        slots.add(new Slot(start, arr.length));
    }

    System.out.println("All slots: "   slots); // all slots that are found
    System.out.println("Slots of size 2: "   getSlotOfSize(slots, 2));
    System.out.println("Slots of size 5: "   getSlotOfSize(slots, 5));
}

This method is used to filter out slots of a particular size:

public static List<Slot> getSlotOfSize(List<Slot> slots, int size) {
    List<Slot> result = new ArrayList<>(); // a new list to preserve the slots list intact
    for (Slot slot: slots) {
        if (slot.getSize() == size)
            result.add(slot);
    }
    return result;
}

Output (starting index inclusive, ending index exclusive)

All slots: [Slot[start=2, end=7], Slot[start=8, end=10]]
Slots of size 2: [Slot[start=8, end=10]]
Slots of size 5: [Slot[start=2, end=7]]
  • Related