Be the first user to complete this post

  • 0
Add to List
Medium

92. Check if Array Contains All Elements Of Some Given Range

Objective: Given an array of unsorted numbers, check if it contains all elements of some given range.

Examples:

int[] arrA = { 11, 17, 13, 19, 15, 16, 12, 14 };

Range : 12-15
Output: True

Range: 17-20
Output: False

Approach:

Naive Approach: Sorting. Time Complexity - O(nlogn).

Better Approach: Time Complexity - O(n).

  • Find the range = y-x;
  • Do the linear scan of the array.
  • Check if element falls within the range of x and y, (arrA[i]>=x && arrA[i]<=y)
  • If Yes then calculate z = arrA[i]-x;
  • Make the arrA[z] element as negative.
  • Once the linear scan is done, Check all the elements in arrA[] from 0 to range are negative, If yes then the array contains all the numbers of the given range, return true, else return false.
  • See the Picture below for a better explanation

Check if Array Contains All Elements Of Some Given Range 

 

Output:

True