Number Range (medium)

Problem Statement

Given an array of numbers sorted in ascending order, find the range of a given number ‘key’. The range of the ‘key’ will be the first and last position of the ‘key’ in the array.

Write a function to return the range of the ‘key’. If the ‘key’ is not present return [-1, -1].

Example 1:

Input: [4, 6, 6, 6, 9], key = 6
Output: [1, 3]

Example 2:

Input: [1, 3, 8, 10, 15], key = 10
Output: [3, 3]

Example 3:

Input: [1, 3, 8, 10, 15], key = 12
Output: [-1, -1]

Constraints:

0 <= nums.length <= 10<sup>5</sup>

.....

Like the course? Get enrolled and start learning!

klden

· 4 years ago

Show 1 reply

Shane

· 3 years ago

my approach. when mid is found use two pointers to check either side of mid.

function find_range(arr, key) {
  let left=0, right=arr.length-1
  while(left <= right){
    let mid = (left+right) >>> 1
    if(arr[mid] < key) left = mid + 1
    else if(arr[mid] > key) right = mid - 1  
    else{
      let lft = mid, rgt = mid
      while(lft >= 0 && arr[lft-1] == arr[mid]) lft--
      while(rgt <= arr.length-1 && arr[rgt+1] == arr[mid]) rgt++
      return [lft,rgt]
    }
  }
  return [-1,-1];
}

Show 1 reply

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findRange(self, arr, key):
    def find_first():
      b, e = 0, len(arr) - 1
      index = 0 
      while b <= e:
        m = (b + e) // 2 
        if arr[m] >= key:
          index = m
          e = m - 1
        else:
          b = m + 1
      return index

    def find_last():
      b, e = 0, len(arr) - 1
      index = 0 
      while b <= e:
        m = (b + e) // 2 
        if arr[m] <= key:
          index = m
          b = m + 1
        else:
          e = m - 1
      return index
    
    first = find_first()
    last = find_last()
   
    return [first if arr[first] == key else -1, last if arr[last] == key else -1]

nirmal kumar ravi

· 2 years ago

class Solution:
  def findRange(self, arr, key):

    # out of bounds check
    if key < arr[0] or key > arr[-1]:
      return [-1, -1]

    
    def search(go_left):
      left, right = 0, len(arr) - 1

      while left <= right:
        mid = left + (right - left) // 2

        if go_left(key, arr[mid]):
          right = mid -1
        else:
          left = mid + 1
      
      return right
    
    # + 1 because it will point to smaller element to the key
    floor = search(lambda key, mid: key <= mid) + 1
    ceiling = search(lambda key, mid: key < mid)

    # if key found
    return [floor, ceiling] if arr[floor] == key else [-1, -1]

lejafilip

· 2 years ago

  vector<int> findRange(const vector<int> &arr, int key) {
    vector<int> result(2, -1);
    
    auto n = arr.size() - 1;
    if(arr[n] < key)
      return result;
    else if(arr[0] > key)
      return result;
    
    result[0] = findLeftIdx(arr, key, 0, n);
    result[1] = findRightIdx(arr, key, 0, n);

    return result;
  }

  int findLeftIdx(const vector<int> &arr, int key, int start, int end)
  {
    auto pivot = (start + end) / 2;
    if(start >= end)
    {
      if(arr[pivot] == key)
        return pivot;
      else if(pivot < arr.size() - 1 && arr[pivot + 1] == key)
        return pivot + 1;
      else
        return -1;
    }

    if(arr[pivot] >= key)
      return findLeftIdx(arr, key, start, pivot - 1);
    else
      return findLeftIdx(arr, key, pivot + 1, end);
  }