CODEWITHSUNDEEP
javaalgorithmdata-structures
brain storm
brain storm

Reputation: 31262

efficient way to remove elements from list of ranges from a bigger range

I am looking for an efficient way to remove a list of ranges from a bigger range. The list of ranges will be contained with the bigger range

eg: 

Bigger range: (0,10) 
List of Ranges:  [(2,7),(4,6),(6,8)]
expected result: {0,1,9,10}

I have an implementation below, but it is O(n2) and takes additional space of size O(n); 

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/***
* input -> (0,10) and {(2,7),(4,6),{6,8}}
 * output -> {0,1,9,10}
 ***/
public class RemoveRanges {

    public static class Range {
        int start;
        int end;

        public Range(int x, int y){
            this.start = x;
            this.end = y;

        }
    }

    public static void main(String[] args) {

        Range outer = new Range(0,10);
        Range r1 = new Range(2,7);
        Range r2 = new Range(4,6);
        Range r3 = new Range(6,8);
        List<Range> rangesToBeRemoved = new ArrayList<>();
        rangesToBeRemoved.add(r1);
        rangesToBeRemoved.add(r2);
        rangesToBeRemoved.add(r3);

        System.out.println(removeRanges(outer, rangesToBeRemoved));

    }

    public static Set<Integer> removeRanges(Range outer, List<Range> rangesToBeRemoved ) {

        Set<Integer> outerElements = new HashSet<>();

        for (int i = outer.start; i<=outer.end;i++ ){
            outerElements.add(i);
        }

        for (Range range : rangesToBeRemoved) {
            for (int j = range.start; j<=range.end; j++) {
                outerElements.remove(j);
            }
        }
        return outerElements;
    }
}

Upvotes: 4

Views: 692

Answers (6)

Sergey Prosin
Sergey Prosin

Reputation: 711

I decided to post another answer to show the optimized solution which has O(1)+O(m) complexity where m - the number of ranges so it doesn't depend on the size of the outer range. However, it requires O(n) memory.

It also doesn't use any classes and should work blazing fast.

Happy to hear comments.

The code is below:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Arrays;

/***
* input -> (0,10) and {(2,7),(4,6),{6,8}}
 * output -> {0,1,9,10}
 ***/
public class Main {

    public static class Range {
        int start;
        int end;

        public Range(int x, int y){
            this.start = x;
            this.end = y;

        }
    }

    public static void main(String[] args) {

        Range outer = new Range(0,10);
        Range r1 = new Range(2,7); //sorted ranges by range.start
        Range r2 = new Range(4,6);
        Range r3 = new Range(6,8);
        List<Range> rangesToBeRemoved = new ArrayList<>();
        rangesToBeRemoved.add(r1);
        rangesToBeRemoved.add(r2);
        rangesToBeRemoved.add(r3);


        printRange(outer, removeRanges(outer, rangesToBeRemoved));

    }

    public static void printRange(Range outer, int[] indexes)
    {
        int outerRangeSize = outer.end - outer.start + 2;
        int rangeShift = - (outer.start - 1);
        int current = 0;
        int currentNext = ((indexes[current] > 0) ? indexes[current] : current + 1);

        while (currentNext - rangeShift <= outer.end)
        {
            System.out.println(currentNext - rangeShift);
            current = currentNext;
            currentNext = ((indexes[current] > 0) ? indexes[current] : current + 1);
        }

    }

    public static int[] removeRanges(Range outer, List<Range> rangesToBeRemoved ) {
        int outerRangeSize = outer.end - outer.start + 2;
        int rangeShift = - (outer.start - 1);

        int[] outerElementsIndexes = new int[outerRangeSize];

        int currentIndex = 0; // point ot the first element in array
        int currentIndexNext = 1;

        for (Range range : rangesToBeRemoved) {
            if (currentIndex >= outerRangeSize) break;
            int nextIndexStart = range.start + rangeShift - 1; //calculate what index we should start from to exclude the range
            if (nextIndexStart < 0) nextIndexStart = 0;
            int nextIndexEnd = range.end + rangeShift + 1; // where we should jump to
            if (nextIndexEnd <= currentIndexNext) continue; // if we already skipped the range we're trying to exclude
            if (nextIndexStart <= currentIndexNext)
            {
              outerElementsIndexes[currentIndex] = nextIndexEnd; // case where we should extend the excluded range because it's intecepted with the last one we skipped

                currentIndexNext = nextIndexEnd;
            }
            else
            {
              outerElementsIndexes[nextIndexStart] = nextIndexEnd; // just exclude the range
              currentIndex = nextIndexStart;
              currentIndexNext = nextIndexEnd;
            }
        }
        return outerElementsIndexes;
    }
}

Upvotes: 1

hk6279
hk6279

Reputation: 1879

Refer to @Bohemian idea by changing your method from "add all element then remove by range" to "add element out of remove range"

  1. Sort the rangesToBeRemoved (by range.start)
  2. Loop over the range and add element that are not cover by ranges

  3. Add all element after the last range's end

    // assume rangesToBeRemoved has been sorted
public static Set<Integer> addElementbyRemovedRanges(Range outer, List<Range> rangesToBeRemoved ) {

    Set<Integer> outerElements = new HashSet<Integer>();

    // this variable record the last element that has handled and act like a borderline
    int borderElementIndex = outer.start-1;
    for (Range range : rangesToBeRemoved) {
        if (range.end <= borderElementIndex ) {
            // omit this range as it has been cover by previous range(s)
            continue;
        }

        // add range if there is gap between range
        if (range.start > borderElementIndex ) {
            addElements(outerElements, borderElementIndex + 1, range.start - 1);
        }

        // update borderline
        borderElementIndex = range.end;
    }
    // Add all element after the last range's end
    addElements(outerElements, borderElementIndex + 1, outer.end);

    return outerElements;
}

public static void addElements(Set<Integer> outerElements, int start, int end) {
    if (start > end) {
        return;
    }
    for (int i=start; i<=end; i++){
        outerElements.add(i);
    }
}

After sorting the rangesToBeRemoved, relationship between two ranges are

  1. Completely in range (e.g. (2,7) and (4,6))
  2. Partly in range (e.g. (2,7) and (6,8))
  3. Not in range (e.g. (2,3) and (6,8) || (2,3) and (4,8))

For case 1, ignore the second range. For case 2, update the borderline to second range's end. For case 3, add the gap to element list and update the borderline to second range's end.

The above code is trying to compare virtual range (outer.start-1, borderElementIndex) and all ranges in rangesToBeRemoved (sorted)

Reuse your example: {(2,7),(4,6),(6,8)}.

  • First, compare (-1,-1) with (2,7) and hit case 3, add the gap [0,1] into result set and change the borderElementIndex to 7.
  • Next, compare (-1,7) with (4,6) and hit case 1, ignore it.
  • Then, compare (-1,7) with (6,8) and hit case 2, change the borderElementIndex to 8.
  • Finally, append remaining gap [9,10] into result set.

To further reduce space usage, you could use the same idea state in @Danny_ds solution to store the range of element instead of individual elements.

Upvotes: 1

Eugene
Eugene

Reputation: 120978

I have no idea about the complexity of this, but thought it would be fun to solve using java-8:

Set<Integer> set = IntStream.concat(
            IntStream.range(outer.start, outer.end),
            rangesToBeRemoved.stream()
                    .reduce(
                            IntStream.empty(),
                            (stream, range) -> IntStream.concat(stream, IntStream.range(range.start, range.end)),
                            IntStream::concat)
                    .distinct())
            .boxed()
            .collect(Collectors.toMap(Function.identity(), x -> Boolean.TRUE, (x, y) -> null))
            .keySet();

Upvotes: 1

Danny_ds
Danny_ds

Reputation: 11406

While Bogemian's solution (comment) is probably the best ("sort the ranges, then output using a loop over the outer range, skipping ranges"), here's an additional way it can be done:

Bigger range: (0,10) 
List of Ranges:  [(2,7),(4,6),(6,8)]

Result list: [(0,10)]

to remove (2,7) split the result list: [(0,1),(8,10)]
(4,6) -> no action
(6,8) -> [(0,1),(9,10)]

This can be done without sorting the ranges, but then we have to look up the position in the result list each time.

Both solutions perform well with big ranges (if they return a list of ranges instead of a list with all the values).

For example:

Bigger range: (0,4000000000) // 4 billion in uint32
List of Ranges:  [(200,1000000),(1000000000,2000000000)]

Result list: [(0,199),(1000001,999999999),(2000000001,4000000000)]

The used space is minimal, execution instant. Using the above ranges with an algorithm that uses O(n) space, where n is the size of the outer range, would be problematic.

Upvotes: 1

arenard
arenard

Reputation: 682

To improve your solution you could merge the list of intervals, which is a classic problem, you can find code there:
https://leetcode.com/problems/merge-intervals/discuss/21222/A-simple-Java-solution

Then you can keep the same code but it becomes O(n) instead of O(n2), since all intervals are disjoint, each element appears at most in one input interval

As a second improvement you could just check if the current value is the left of an interval, if yes, skip that interval:

public static Set<Integer> removeRanges(Range outer, List<Range> rangesToBeRemoved ) {

    HashMap<Integer, Integer> Ranges = new HashMap<>();
    for (Range range : rangesToBeRemoved) {
        Ranges.put(range.start, range.end);
    }

    Set<Integer> outerElements = new HashSet<>();
    for (int j = range.start; j<=range.end; j++) {
       if(Ranges.get(j))
       {
           int left=j, right=Ranges.get(j);
           j += right - left + 1; //skip this interval
       }
       else
       {
           outerElements.add(j);
       }
    }

    return outerElements;
}

Upvotes: 1

Sergey Prosin
Sergey Prosin

Reputation: 711

My idea is to stick to indexes instead of items values. The benefit is the operation of excluding one range is O(1) because instead of going through each item of the array we need to change one index value only. After that, we should go through array indexes to compile the answer (see printRange method for details of how the result is to be constructed). As for resulted complexity, the solution is O(n) + O(m) where n is the outer range size and m is the number of ranges we'd like to exlude. In terms of memory using the solution is O(n) because we need to use additional array to store indexes of n size.

Pre-conditions: all the ranges we'd like to exclude should be sorted by range.start values. In case they are unsorted it adds O(m*log(m)) complexity to the algorithm.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Arrays;

/***
* input -> (0,10) and {(2,7),(4,6),{6,8}}
 * output -> {0,1,9,10}
 ***/
public class Main {

    public static class Range {
        int start;
        int end;

        public Range(int x, int y){
            this.start = x;
            this.end = y;

        }
    }

    public static void main(String[] args) {

        Range outer = new Range(0,10);
        Range r1 = new Range(2,7); //sorted ranges by range.start
        Range r2 = new Range(4,6);
        Range r3 = new Range(6,8);
        List<Range> rangesToBeRemoved = new ArrayList<>();
        rangesToBeRemoved.add(r1);
        rangesToBeRemoved.add(r2);
        rangesToBeRemoved.add(r3);


        printRange(outer, removeRanges(outer, rangesToBeRemoved));

    }

    public static void printRange(Range outer, int[] indexes)
    {
        int outerRangeSize = outer.end - outer.start + 2;
        int rangeShift = - (outer.start - 1);
        int current = 0;

        while (indexes[current] - rangeShift <= outer.end)
        {
            System.out.println(indexes[current] - rangeShift);
            current = indexes[current];
        }

    }

    public static int[] removeRanges(Range outer, List<Range> rangesToBeRemoved ) {
        int outerRangeSize = outer.end - outer.start + 2;
        int rangeShift = - (outer.start - 1);

        int[] outerElementsIndexes = new int[outerRangeSize];

        for (int i = 0; i<outerRangeSize;i++ ){
            outerElementsIndexes[i]=i+1; // construct indexes refereneces to the next indexes (one by one)
        }

        int currentIndex = 0; // point ot the first element in array
        int currentIndexNext = 1;

        for (Range range : rangesToBeRemoved) {
            if (currentIndex >= outerRangeSize) break;
            //int currentIndexNext = outerElementsIndexes[currentIndex];
            int nextIndexStart = range.start + rangeShift - 1; //calculate what index we should start from to exclude the range
            if (nextIndexStart < 0) nextIndexStart = 0;
            int nextIndexEnd = range.end + rangeShift + 1; // where we should jump to
            if (nextIndexEnd <= currentIndexNext) continue; // if we already skipped the range we're trying to exclude
            if (nextIndexStart <= currentIndexNext)
            {
              outerElementsIndexes[currentIndex] = nextIndexEnd; // case where we should extend the excluded range because it's intecepted with the last one we skipped

                currentIndexNext = nextIndexEnd;
            }
            else
            {
              outerElementsIndexes[nextIndexStart] = nextIndexEnd; // just exclude the range
              currentIndex = nextIndexStart;
              currentIndexNext = nextIndexEnd;
            }
        }
        return outerElementsIndexes;
    }
}

Upvotes: 1

Related Questions