# Contained Ranges

Problem: Contained Ranges

A range [x1, x2] where x1 (start of range) and x2 (end of range) are integer and x1 ≤ x2 includes all numbers x such that x1 ≤ x ≤ x2. A range [x1, x2] is contained in a range [y1, y2] if y1 ≤ x1 ≤ x2 ≤ y2. Given a list of ranges A, check whether there exists a pair of ranges such that one range is contained in the other range.

Discussion

A naive solution which runs in O(N2) where N is the number of ranges is that we verify all pairs of ranges and check whether one range is contained in the other range.

Since the condition of range [x1, x2] is contained in range [y1, y2] is that y1 ≤ x1 ≤ x2 ≤ y2, we want to sort ranges by start of range in increasing order. Sorting only takes O(NlogN).

For example, assume after sorting, we have list of ranges A = [[1, 3], [2, 4], [5, 9], [6, 10], [7, 8]]. Since the ranges are sorted, we just check whether A[i] is contained in A[j] where i > j. However, this still requires O(N2).

Intuitively, we will iterate on ranges and given a new range, we check whether it is contained in any previous range. For example, we check [5, 9] is contained by [1, 3] or [2, 4]. Thus, verifying range A[i] requires checking on i previous ranges. Can we do it better?

Yes we can. Given A[i], do we need to check all A[j] where j < i whether A[i] is contained in A[j]? Actually, it is sufficient to check whether A[i] is contained in A[i-1]. Given any range A[j] before A[i-1], since A[i-1] is not contained by A[j], the end of range A[i-1] must greater than the end of range A[j]. Therefore, if A[i] is contained in A[j], it is also contained in A[i-1]. This is similar to the range [7, 8] is contained in [5, 9] and also [6, 10].

Below is the implementation which runs in O(NlogN).

```public class Range{
public int start;
public int end;
public Range(int s, int e){
start = s;
end = e;
}

@Override
public String toString() {
return "[" + start + "," + end + "]";
}

@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Range)) {
return false;
}
Range c = (Range) o;
return start == c.start && end == c.end;
}
}

//compare two range by start, used to sort list of ranges by their starts
public class RangeComparator implements Comparator<Range> {
public int compare(Range range1, Range range2) {
return Integer.compare(range1.start, range2.start);
}
}

public boolean hasContainedRange(List<Range> ranges){
if (ranges.size() < 2){
return false;
}

ranges.sort(new RangeComparator());
for(int i = 1; i < ranges.size(); i++) {
if (ranges.get(i).end <= ranges.get(i - 1).end){
return true;
}
}

return false;
}
```

# Bit Manipulation Questions

In this post, I will discuss many bit manipulation questions. Those questions are often related with And (&), Or (|), and Xor (&) operators. We use x and y as bit sequence, x[i] as i.th bit in x, and b is a boolean variable. Moreover, ~x denotes a bit sequence where (~x)[i] = !x[i]. 1. […]

# Split String into Palindromes

Problem This problem is also known as Palindrome Partitioning. Given a string s, return minimum number of cuts to split string into palindromes. For example, if s = “abbab”, we can partition the string into 2 palindromes “abba” and “b”. Source code Check your program with these unit tests Discussion This is another dynamic programming […]

# Remove Digits To Have Minimum Number

Problem Given natural numbers N and k, you need to remove k digits from N to have minimum number. For example, if N = 32674, K = 3, we will remove 3, 6, and 7 to have 24 which is minimum. Discussion Actually, this problem asks us to decide which digit to keep to have […]

# Finding maximums for all K-windows in linear time

Problem Given an array A of N elements. For all windows of size K (aka contiguous sub-array of size K) of A, find the maximum elements. Input: A = [8, 5, 10, 7, 9, 4, 15, 12, 90, 13], K = 4 Output: [10, 10, 10, 15, 15, 90, 90] Discussion A trivial solution is […]

# Longest SubString without Repeating Characters

Problem Given a string s composed of characters from ‘a’ to ‘z’, return the longest substring without repeating characters. For example, if s = “ababcb”, return “abc”. Any other substring length of 3 contains duplication. Check your program with these unit tests Discussion This is another dynamic programming problem. When hearing the problem is finding […]

# Merge Ranges

Problem: Merge Ranges A range [x1, x2] where x1 (start of range) and x2 (end of range) are integer and x1 ≤ x2 includes all numbers x such that x1 ≤ x ≤ x2. Given a list of ranges, merge them and return a list of ranges such that no pair of ranges overlap. For […]