Find Range I: Solving Coding Questions #1

Find Range I

Given a sorted array of numbers, find the first range of numbers that contains the target. A range contains the target if low <= target <= high. If a range does not exist return [-1, -1]

Example:
Array: [1, 2, 3, 4, 5, 6]
Target: 4
Output: [3, 4]

Array: [1, 2, 3, 4, 5, 6]
Target: 0
Output: [-1, -1]

Give it a shot, then come back if you get stuck or find a solution.

Solution #1

The first solution is really straight forward, we start at the second element and as we go through the array we check if the target is between the previous and current value. If at any point, the target value is between we return those two numbers. However, if the number is not found we return [-1, -1].

Code (C++)

pair<int, int> find_range(vector<int> arr, int target) {
   for(int i = 1; i < arr.size(); i++) {
      if(arr[i-1] <= target && arr[i] >= target)
         return {arr[i-1], arr[i]};
   }
   return {-1, -1};
}

Time: O(n)
Space: O(1)

As you can see, the code is simple and straight forward and our time complexity is not terrible but we can do better.

If you got the above solution, go back and reread the problem and see if you can improve your solution. Once you have done that come back and see how I will do it and compare your solution.

Solution #2

If we go back and reread the question, we will find a little nugget that will help us improve our time complexity.

Given a sorted array of numbers

We can take advantage of knowing the array will be sorted and implement the solution doing a binary search.

Code (C++)

pair<int, int> find_range(vector<int> arr, int target) {
  int low = 0, high = arr.size() - 1, mid;
    while(low <= high) {
      mid = (high + low) / 2;
      if(arr[mid] <= target && arr[mid + 1] >= target) {
        return {arr[mid], arr[mid+1]};
      } else if(arr[mid] < target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  return {-1, -1};
}

We implemented a binary search and it brings our time to O(log n) but if we go back and reread the question, we find that we are not covering all the cases.

first range of numbers that contains the target

If we run the code, we find out it does not cover it for the following case
arr = [0 1 1 1 1 1 1 1 1 1 1]
target = 1
expected = [0, 1]
actual = [1, 1]

To cover for this edge case we need to do some checks when we find out the target is in range. If our actual and next one are the same, then we can safely return as we are. If they are the same and the previous one and the first is not the same we return the previous and current. If none is the case we have high be the mid — 1.

Code (C++)

if(arr[mid] != arr[mid + 1])
  return {arr[mid], arr[mid + 1]};
if(arr[mid - 1] != arr[mid] && arr[mid] == arr[mid + 1])
  return {arr[mid - 1], arr[mid]};
high = mid - 1;

Okay, that was not too bad of a tweak to get that test case to pass. However we still have a problem in the code. If we get an array of the max size, and we are looking for a value greater than the last value, we will overflow. To fix the issue, it is a simple fix we make mid = low + ((high — low) / 2). Having done that our final solution will be

Code (C++)

pair<int, int> find_range(vector<int> arr, int target) {
  int low = 0, high = arr.size() - 1, mid;
    while(low <= high) {
      mid = low + ((high - low) / 2);
      if(arr[mid] <= target && arr[mid + 1] >= target) {
        if(arr[mid] != arr[mid + 1])
          return {arr[mid], arr[mid + 1]};
        if(arr[mid - 1] != arr[mid] && arr[mid] == arr[mid + 1])
          return {arr[mid - 1], arr[mid]};
        high = mid - 1;
      } else if(arr[mid] < target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  return {-1, -1};
}

Time: O(log n)

Space: O(1)

Hope you have found my explanation helpful and that you learned something from it.