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

Approach:

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

Better Approach: Time Complexity – O(n).

  • Find the range = y-x;
  • Do the linear scan of 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, just check all the elements in arrA[] from 0 to range are negative, if yes them array contains all the numbers of the given range, return true, else false.
  • See the Picture below for better explanation
Check if Array Contains All Elements Of Some Given Range

Check if Array Contains All Elements Of Some Given Range

Complete Code:


Output:

True

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • sdiz

    If we can make the assumption that all integers are positive, this below code I believe is slightly simpler than your O(N) solution.

    O(range_start-range_end) space
    O(N) runtime

    def check_in_range(items, start, end):
    # define an array 4 slots wide
    visited = [False]*(end-start+1)

    for item in items:

    # check for only items between our range
    if item >= start and item <= end:
    # if we find an item IE; 12 we need to mark it
    # as visited in our array, so 12-12 = 0, so it
    # goes it slot 0, 13 goes in slot 1, 13-12 1 etc...
    visited[item-start] = True

    # return True if all were visited
    return all(visited)

%d bloggers like this: