title: Check if All the Integers in a Range Are Covered
slug: check-if-all-integers-in-range-are-covered
difficulty: easy
leetcode_id: 1893
leetcode_url: https://leetcode.com/problems/check-if-all-the-integers-in-a-range-are-covered/
categories:
  - arrays
  - hash-tables
patterns:
  - slug: prefix-sum
    is_optimal: true

function_signature: "def is_covered(ranges: list[list[int]], left: int, right: int) -> bool:"

test_cases:
  visible:
    - input: { ranges: [[1, 2], [3, 4], [5, 6]], left: 2, right: 5 }
      expected: true
    - input: { ranges: [[1, 10], [10, 20]], left: 21, right: 21 }
      expected: false
  hidden:
    - input: { ranges: [[1, 50]], left: 1, right: 50 }
      expected: true
    - input: { ranges: [[1, 2]], left: 1, right: 3 }
      expected: false
    - input: { ranges: [[1, 1], [3, 3]], left: 1, right: 3 }
      expected: false
    - input: { ranges: [[1, 5], [6, 10]], left: 1, right: 10 }
      expected: true

description: |
  You are given a 2D integer array `ranges` and two integers `left` and `right`. Each `ranges[i] = [start_i, end_i]` represents an **inclusive** interval between `start_i` and `end_i`.

  Return `true` *if each integer in the inclusive range* `[left, right]` *is covered by **at least one** interval in* `ranges`. Return `false` *otherwise*.

  An integer `x` is covered by an interval `ranges[i] = [start_i, end_i]` if `start_i <= x <= end_i`.

constraints: |
  - `1 <= ranges.length <= 50`
  - `1 <= start_i <= end_i <= 50`
  - `1 <= left <= right <= 50`

examples:
  - input: "ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5"
    output: "true"
    explanation: "Every integer between 2 and 5 is covered: 2 is covered by the first range, 3 and 4 are covered by the second range, and 5 is covered by the third range."
  - input: "ranges = [[1,10],[10,20]], left = 21, right = 21"
    output: "false"
    explanation: "21 is not covered by any range."

explanation:
  intuition: |
    Imagine you have a number line with some segments painted on it. Each interval `[start, end]` paints all integers from `start` to `end`. Your task is to check whether every integer from `left` to `right` has been painted at least once.

    Think of it like checking if a road is fully paved: you have several paving crews, each covering a section of road. You need to verify that the stretch from mile marker `left` to mile marker `right` has no gaps.

    The key insight is that with small constraints (all values ≤ 50), we can afford to explicitly mark which integers are covered. We don't need sophisticated interval merging — we can simply "paint" each covered integer in a set or array and then check if our target range is fully painted.

  approach: |
    We solve this using a **Set-Based Coverage Check**:

    **Step 1: Create a set to track covered integers**

    - `covered`: An empty set that will store all integers covered by any interval

    &nbsp;

    **Step 2: Mark all covered integers**

    - For each interval `[start, end]` in `ranges`:
      - Add every integer from `start` to `end` (inclusive) to the `covered` set

    &nbsp;

    **Step 3: Check if the target range is fully covered**

    - For each integer `i` from `left` to `right`:
      - If `i` is not in `covered`, return `false` immediately
    - If we complete the loop without finding a gap, return `true`

    &nbsp;

    This approach leverages the small constraint (values ≤ 50) to use O(n) space where n is the range of possible values, which is acceptable and leads to a clean, readable solution.

  common_pitfalls:
    - title: Over-Engineering with Interval Merging
      description: |
        A tempting approach is to sort and merge intervals, then perform a binary search or scan. While this works, it's unnecessary complexity for this problem.

        With constraints limiting all values to 50 or less, the simpler set-based approach is both efficient and easier to implement correctly. Save interval merging for problems where the value range is large (e.g., `10^9`).
      wrong_approach: "Complex interval sorting and merging"
      correct_approach: "Simple set-based coverage tracking"

    - title: Using Only the Query Range
      description: |
        Some might try to optimise by only considering integers in `[left, right]` when iterating through intervals. While this works, it's an unnecessary micro-optimisation.

        Given the small constraints, marking all covered integers is fast and leads to simpler code. The overall complexity remains O(n × m) where n is the number of intervals and m is the average interval size.

    - title: Off-by-One Errors
      description: |
        Remember that intervals are **inclusive** on both ends. When marking `[start, end]`, you must include both `start` and `end`.

        Similarly, when checking `[left, right]`, ensure you check the entire inclusive range. Use `range(left, right + 1)` in Python to include `right`.
      wrong_approach: "range(start, end) missing the endpoint"
      correct_approach: "range(start, end + 1) to include both boundaries"

  key_takeaways:
    - "**Leverage constraints**: When value ranges are small (≤ 50), direct marking with sets or arrays is simpler than interval algorithms"
    - "**Sets for membership**: Python sets provide O(1) lookup, making coverage checks efficient"
    - "**Foundation for harder problems**: This concept extends to problems like merge intervals, meeting rooms, and range coverage with larger constraints"
    - "**Simplicity wins**: Don't over-engineer — choose the simplest approach that meets the complexity requirements"

  time_complexity: "O(n × m + k). We iterate through each of the `n` intervals, marking up to `m` integers per interval (where `m ≤ 50`). Then we check `k = right - left + 1` integers for coverage."
  space_complexity: "O(n × m). In the worst case, we store all covered integers in the set, which could be up to 50 unique values given the constraints."

solutions:
  - approach_name: Set-Based Coverage
    is_optimal: true
    code: |
      def is_covered(ranges: list[list[int]], left: int, right: int) -> bool:
          # Track all integers covered by any interval
          covered = set()

          # Mark each integer in every interval as covered
          for start, end in ranges:
              for i in range(start, end + 1):
                  covered.add(i)

          # Check if every integer in [left, right] is covered
          for i in range(left, right + 1):
              if i not in covered:
                  return False

          return True
    explanation: |
      **Time Complexity:** O(n × m + k) — We process all intervals and then check the query range.

      **Space Complexity:** O(n × m) — We store all covered integers in a set.

      This approach directly marks all covered integers and then verifies the target range. Clean, readable, and efficient given the small constraints.

  - approach_name: Direct Range Check
    is_optimal: false
    code: |
      def is_covered(ranges: list[list[int]], left: int, right: int) -> bool:
          # Check each integer in the target range
          for num in range(left, right + 1):
              # See if any interval covers this number
              is_num_covered = False
              for start, end in ranges:
                  if start <= num <= end:
                      is_num_covered = True
                      break

              # If no interval covers this number, return False
              if not is_num_covered:
                  return False

          return True
    explanation: |
      **Time Complexity:** O(k × n) — For each of the `k` integers in `[left, right]`, we check up to `n` intervals.

      **Space Complexity:** O(1) — No additional data structures used.

      This approach checks each number individually against all intervals. It uses constant space but may do redundant work checking the same intervals multiple times. Still efficient given the small constraints.

  - approach_name: Boolean Array (Difference Array Concept)
    is_optimal: false
    code: |
      def is_covered(ranges: list[list[int]], left: int, right: int) -> bool:
          # Boolean array to mark covered positions (index 0-51)
          covered = [False] * 52

          # Mark all positions covered by each interval
          for start, end in ranges:
              for i in range(start, end + 1):
                  covered[i] = True

          # Check if all positions in [left, right] are covered
          for i in range(left, right + 1):
              if not covered[i]:
                  return False

          return True
    explanation: |
      **Time Complexity:** O(n × m + k) — Same as the set-based approach.

      **Space Complexity:** O(52) = O(1) — Fixed-size array based on constraint that values ≤ 50.

      This variant uses a boolean array instead of a set. It's slightly more memory-efficient since we know the maximum value is 50. The array approach hints at the "difference array" technique used for larger constraint problems.
