Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Check if Array Contains All Elements Of Some Given Range

Objec­tive: Given an array of unsorted num­bers, check if it con­tains all ele­ments of some given range.

Exam­ples:

int[] arrA = { 11, 17, 13, 19, 15, 16, 12, 14 };
Range : 12-15
Output: True

Approach:

Naive Approach: Sort­ing . Time Com­plex­ity — O(nlogn).

Bet­ter Approach: Time Com­plex­ity — O(n).

  • Find the range = y-x;
  • Do the lin­ear scan of array.
  • Check if ele­ment falls within the range of x and y, (arrA[i]>=x && arrA[i]<=y)
  • If Yes then cal­cu­late z = arrA[i]-x;
  • Make the arrA[z] ele­ment as negative.
  • Once the lin­ear scan is done, just check all the ele­ments in arrA[] from 0 to range are neg­a­tive, if yes them array con­tains all the num­bers of the given range, return true, else false.
  • See the Pic­ture below for bet­ter explanation
Check-if-Array-Contains-All-Elements-Of-Some-Given-Range

Check-if-Array-Contains-All-Elements-Of-Some-Given-Range

Com­plete Code:


Out­put:

True

You may also like...

  • sdiz

    If we can make the assump­tion that all inte­gers are pos­i­tive, this below code I believe is slightly sim­pler 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
    vis­ited = [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 vis­ited 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 vis­ited
    return all(visited)