Problem

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

Examples

Example 1:

1
2

Input: arr = [11, 17, 13, 19, 15, 16, 12, 14], low = 12, high = 15
Output: True

Solution

Method 1 -Sorting

Time Complexity – O(nlogn).

Method 2 - Using HashSet

Here is the approach:

  1. Create a Set: Use a HashSet to store all unique elements from the array.
  2. Check Range: Iterate over the specified range and check if each element in the range exists in the set.
  3. Return Result: If all elements in the range are found in the set, return true. Otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public class Solution {
    public static boolean containsAllInRange(int[] arr, int low, int high) {
        // Create a HashSet and add all elements of the array to it
        HashSet<Integer> elements = new HashSet<>();
        for (int num : arr) {
            elements.add(num);
        }

        // Check if all numbers in the range [low, high] exist in the HashSet
        for (int i = low; i <= high; i++) {
            if (!elements.contains(i)) {
                return false;
            }
        }
        return true;
    }

}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in the array.
    • This is constant for a given range, so it can be considered O(k), where k = high - low + 1
  • 🧺 Space complexity: O(n)

Method 3 - Using array modification

Here is the approach:

  1. Adjust Range Calculation:

    • The variable range is set to high - low + 1 to correctly include both boundaries.

  2. Mark Elements with linear scan:

    • For each element in the array, if it falls within the range [low, high], compute its adjusted index as idx = arr[i] - low.
    • Use the index to mark the position in arr[idx] by making the value at that index negative. This signifies the presence of the element.

  3. Check for Presence:

    • Iterate through the first range elements and check if every position was marked.
    • Adjust to avoid ArrayIndexOutOfBoundsException by considering only valid indices.

  4. Return Result:

    • If all elements in the specified range are marked, return true.
    • If any element in the range is not marked, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public Boolean find(int[] arr, int low, int high) {
        int range = high - low + 1; // Include the high element in the range
        int n = arr.length;

        // Find and mark elements in the range [low, high]
        for (int i = 0; i < n; i++) {
            if (arr[i] >= low && arr[i] <= high) {
                int idx = arr[i] - low;
                // Mark the element at the index position in the original range
                if (idx < n && arr[idx] > 0) {
                    arr[idx] = -arr[idx]; // Use negative marking
                }
            }
        }

        // Check if every element in the range was marked
        for (int i = 0; i < range && i < n; i++) {
            // Adjust to avoid `ArrayIndexOutOfBoundsException`
            if (arr[i] > 0) {
                return false;
            }
        }

        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1) for aux space