Delete Element from Interval Array by Index

Problem Overview

You are given an array of non-overlapping intervals sorted by start position. Each interval represents a range of consecutive integers. You are also given an index into the "flattened" or "covered" list of all elements across all intervals. Your task is to remove the element at that index from the covered list and return the resulting interval array.

Key Points:

• Intervals are non-overlapping and sorted
• The index refers to the position in the flattened list of all covered elements
• After removing an element, you may need to split an interval into two parts

Problem Statement

Given:

• intervals: List of non-overlapping intervals [(start, end), ...] where both endpoints are inclusive
• index: An integer representing the position in the flattened covered list (0-indexed)

Return:

• A new list of intervals after removing the element at the given index

Examples

Example 1: Delete from Middle of Interval

intervals = [(4, 7), (10, 11), (13, 15)]
index = 2

# Covered list: [4, 5, 6, 7, 10, 11, 13, 14, 15]
# Index 2 points to element 6
# After removing 6: [4, 5, 7, 10, 11, 13, 14, 15]
# Result: [(4, 5), (7, 7), (10, 11), (13, 15)]

Explanation:

• The flattened list contains 9 elements: [4, 5, 6, 7, 10, 11, 13, 14, 15]
• Index 2 corresponds to the value 6
• Removing 6 splits the interval (4, 7) into (4, 5) and (7, 7)

Example 2: Delete from Start of Interval

intervals = [(4, 7), (10, 11), (13, 15)]
index = 0

# Covered list: [4, 5, 6, 7, 10, 11, 13, 14, 15]
# Index 0 points to element 4
# After removing 4: [5, 6, 7, 10, 11, 13, 14, 15]
# Result: [(5, 7), (10, 11), (13, 15)]

Example 3: Delete from End of Interval

intervals = [(4, 7), (10, 11), (13, 15)]
index = 3

# Covered list: [4, 5, 6, 7, 10, 11, 13, 14, 15]
# Index 3 points to element 7
# After removing 7: [4, 5, 6, 10, 11, 13, 14, 15]
# Result: [(4, 6), (10, 11), (13, 15)]

Example 4: Delete Entire Single-Element Interval

intervals = [(4, 7), (10, 10), (13, 15)]
index = 4

# Covered list: [4, 5, 6, 7, 10, 13, 14, 15]
# Index 4 points to element 10 (the only element in interval (10, 10))
# After removing 10: [4, 5, 6, 7, 13, 14, 15]
# Result: [(4, 7), (13, 15)]

Constraints

• 1 <= len(intervals) <= 10^4
• 0 <= intervals[i][0] <= intervals[i][1] <= 10^9
• Intervals are non-overlapping and sorted
• 0 <= index < total number of covered elements
• All interval endpoints are integers

Approach 1: Direct Calculation (Optimal)

Algorithm

The key insight is that you don't need to build the entire flattened list. Instead:

1. Find which interval contains the target element:

   • Iterate through intervals, counting how many elements each one covers
   • Track cumulative count until you find the interval containing the index

2. Calculate the actual value to delete:

   • Use the index offset within that interval to determine the exact value

3. Modify the interval:

   • If deleting from the start: increment start by 1
   • If deleting from the end: decrement end by 1
   • If deleting from middle: split into two intervals
   • If interval becomes empty: remove it entirely

Time Complexity

• O(n) where n is the number of intervals
• We iterate through intervals once to find the target
• All other operations are O(1)

Space Complexity

• O(n) for the output array
• O(1) additional space

Implementation

def delete_from_intervals(intervals, index):
    """
    Delete element at given index from flattened interval array.

    Args:
        intervals: List of (start, end) tuples (inclusive)
        index: Position in flattened covered list

    Returns:
        List of intervals after deletion
    """
    if not intervals:
        return []

    result = []
    cumulative_count = 0

    for i, (start, end) in enumerate(intervals):
        interval_size = end - start + 1

        # Check if target index falls in this interval
        if cumulative_count + interval_size > index:
            # Calculate which element within this interval to delete
            offset = index - cumulative_count
            target_value = start + offset

            # Handle deletion based on position
            if target_value == start and target_value == end:
                # Single-element interval, delete entire interval
                pass  # Don't add to result
            elif target_value == start:
                # Delete from start, shift start forward
                result.append((start + 1, end))
            elif target_value == end:
                # Delete from end, shift end backward
                result.append((start, end - 1))
            else:
                # Delete from middle, split into two intervals
                result.append((start, target_value - 1))
                result.append((target_value + 1, end))

            # Add all remaining intervals unchanged
            result.extend(intervals[i + 1:])
            break
        else:
            # This interval comes before the target
            result.append((start, end))
            cumulative_count += interval_size

    return result

# Test cases
def test_delete_from_intervals():
    # Example 1: Delete from middle
    intervals = [(4, 7), (10, 11), (13, 15)]
    result = delete_from_intervals(intervals, 2)
    assert result == [(4, 5), (7, 7), (10, 11), (13, 15)]

    # Example 2: Delete from start
    intervals = [(4, 7), (10, 11), (13, 15)]
    result = delete_from_intervals(intervals, 0)
    assert result == [(5, 7), (10, 11), (13, 15)]

    # Example 3: Delete from end
    intervals = [(4, 7), (10, 11), (13, 15)]
    result = delete_from_intervals(intervals, 3)
    assert result == [(4, 6), (10, 11), (13, 15)]

    # Example 4: Delete single-element interval
    intervals = [(4, 7), (10, 10), (13, 15)]
    result = delete_from_intervals(intervals, 4)
    assert result == [(4, 7), (13, 15)]

    print("All tests passed!")

test_delete_from_intervals()

Why This is Better Than Prefix Sum

Interviewer Feedback: The prefix sum approach was considered "overly complicated."

Reason:

• Prefix sum requires extra space: O(n) array
• Prefix sum requires extra preprocessing: O(n) time
• Binary search on prefix sum: O(log n)
• Total: O(n) space + O(n + log n) time

Direct approach:

• No preprocessing needed
• No extra data structures
• Single pass: O(n) time
• Total: O(1) space + O(n) time

The direct calculation is simpler, more intuitive, and equally efficient.

Approach 2: Flatten and Rebuild (Naive)

For comparison, here's the naive approach (not recommended for interview):

def delete_from_intervals_naive(intervals, index):
    """Naive approach: build entire flattened list."""
    # Build covered list
    covered = []
    for start, end in intervals:
        covered.extend(range(start, end + 1))

    # Remove element at index
    if 0 <= index < len(covered):
        del covered[index]

    # Rebuild intervals
    if not covered:
        return []

    result = []
    start = covered[0]
    end = covered[0]

    for i in range(1, len(covered)):
        if covered[i] == end + 1:
            # Consecutive, extend interval
            end = covered[i]
        else:
            # Gap found, save current interval
            result.append((start, end))
            start = covered[i]
            end = covered[i]

    # Don't forget last interval
    result.append((start, end))

    return result

Why this is bad:

• Time: O(m) where m is total number of covered elements (could be 10^9!)
• Space: O(m) to store flattened list
• Memory inefficient for large intervals like (1, 1000000000)

Follow-Up 1: Frequent Deletions with Large Interval Arrays

Question: If the interval array is very large (10^4 intervals) and delete operations are performed frequently (10^5 deletions), how would you optimize the deletion operation?

Alternative: Skip List with Interval Nodes

For similar performance with simpler implementation:

import random

class IntervalSkipNode:
    def __init__(self, start, end, level):
        self.start = start
        self.end = end
        self.covered_count = end - start + 1
        self.forward = [None] * (level + 1)
        self.span = [0] * (level + 1)  # Distance to next node

class IntervalSkipList:
    def __init__(self, max_level=16):
        self.max_level = max_level
        self.header = IntervalSkipNode(-1, -1, max_level)
        self.level = 0

    def find_at_index(self, index):
        """Find interval containing element at index."""
        current = self.header
        cumulative = 0

        for i in range(self.level, -1, -1):
            while current.forward[i] and cumulative + current.span[i] <= index:
                cumulative += current.span[i]
                current = current.forward[i]

        return current, cumulative

    # Delete, insert, and other operations omitted

Advantages over tree:

• Simpler to implement
• Better cache locality
• Probabilistic balancing (no rotations)

Follow-Up 2: Dynamic Insert and Delete with Non-Overlapping Constraint

Question: Extend the system to support both insertion and deletion of elements while maintaining the non-overlapping interval invariant. When inserting an element, merge overlapping intervals if necessary.

Operations to Support

1. delete_at_index(index): Delete element at given index (same as before)
2. insert_value(value): Insert a value and merge with adjacent intervals if they become consecutive
3. get_intervals(): Return current list of non-overlapping intervals

Algorithm

class DynamicIntervalSet:
    def __init__(self, intervals=None):
        """Initialize with optional list of intervals."""
        self.intervals = sorted(intervals) if intervals else []

    def delete_at_index(self, index):
        """Delete element at given index from flattened list."""
        if not self.intervals:
            return

        result = []
        cumulative_count = 0

        for i, (start, end) in enumerate(self.intervals):
            interval_size = end - start + 1

            if cumulative_count + interval_size > index:
                offset = index - cumulative_count
                target_value = start + offset

                if target_value == start and target_value == end:
                    pass  # Remove entire interval
                elif target_value == start:
                    result.append((start + 1, end))
                elif target_value == end:
                    result.append((start, end - 1))
                else:
                    result.append((start, target_value - 1))
                    result.append((target_value + 1, end))

                result.extend(self.intervals[i + 1:])
                break
            else:
                result.append((start, end))
                cumulative_count += interval_size

        self.intervals = result

    def insert_value(self, value):
        """
        Insert a single value and merge with adjacent intervals.

        Time Complexity: O(n) to find position + O(n) to rebuild
        """
        if not self.intervals:
            self.intervals = [(value, value)]
            return

        # Binary search to find insertion point
        insert_pos = self._find_insert_position(value)

        # Check if value already covered
        if insert_pos > 0:
            prev_start, prev_end = self.intervals[insert_pos - 1]
            if prev_start <= value <= prev_end:
                return  # Already covered

        # Check if we can merge with previous interval
        merge_prev = False
        if insert_pos > 0:
            prev_start, prev_end = self.intervals[insert_pos - 1]
            if prev_end + 1 == value:
                merge_prev = True

        # Check if we can merge with next interval
        merge_next = False
        if insert_pos < len(self.intervals):
            next_start, next_end = self.intervals[insert_pos]
            if next_start - 1 == value:
                merge_next = True

        # Perform merge
        if merge_prev and merge_next:
            # Merge with both neighbors
            prev_start, prev_end = self.intervals[insert_pos - 1]
            next_start, next_end = self.intervals[insert_pos]
            new_interval = (prev_start, next_end)
            self.intervals = (
                self.intervals[:insert_pos - 1] +
                [new_interval] +
                self.intervals[insert_pos + 1:]
            )
        elif merge_prev:
            # Extend previous interval
            prev_start, prev_end = self.intervals[insert_pos - 1]
            self.intervals[insert_pos - 1] = (prev_start, value)
        elif merge_next:
            # Extend next interval
            next_start, next_end = self.intervals[insert_pos]
            self.intervals[insert_pos] = (value, next_end)
        else:
            # Insert new interval
            self.intervals.insert(insert_pos, (value, value))

    def _find_insert_position(self, value):
        """Binary search to find where to insert value."""
        left, right = 0, len(self.intervals)
        while left < right:
            mid = (left + right) // 2
            if self.intervals[mid][0] < value:
                left = mid + 1
            else:
                right = mid
        return left

    def get_intervals(self):
        """Return current intervals."""
        return self.intervals.copy()

# Usage Example
dynamic_set = DynamicIntervalSet([(4, 7), (10, 11), (13, 15)])

# Delete element at index 2 (removes 6)
dynamic_set.delete_at_index(2)
print(dynamic_set.get_intervals())  # [(4, 5), (7, 7), (10, 11), (13, 15)]

# Insert 6 (merges intervals)
dynamic_set.insert_value(6)
print(dynamic_set.get_intervals())  # [(4, 7), (10, 11), (13, 15)]

# Insert 9 (merges with adjacent interval)
dynamic_set.insert_value(9)
print(dynamic_set.get_intervals())  # [(4, 7), (9, 11), (13, 15)]

# Insert 8 (merges three intervals)
dynamic_set.insert_value(8)
print(dynamic_set.get_intervals())  # [(4, 11), (13, 15)]

Complexity Analysis

Time Complexity:

• delete_at_index(): O(n) to find and modify
• insert_value(): O(log n) binary search + O(n) to rebuild array
• get_intervals(): O(n) to copy

Space Complexity:

• O(n) for storing intervals

Optimization: Use Balanced BST

For better insertion performance:

from sortedcontainers import SortedList

class OptimizedDynamicIntervalSet:
    def __init__(self, intervals=None):
        # Store intervals in sorted list (Red-Black Tree internally)
        self.intervals = SortedList(intervals or [])

    def insert_value(self, value):
        """O(log n) insertion with merge."""
        # Find position: O(log n)
        idx = self.intervals.bisect_left((value, value))

        # Check and merge: O(1)
        # Insert: O(log n)
        # (Implementation similar to above)

Improved Time Complexity:

• insert_value(): O(log n)

Follow-Up 3: Find Optimal Cover After Deletion

Question: After deleting an element at a given index, find the minimum number of intervals needed to cover all remaining elements. What if you can add at most K elements back to minimize the number of intervals?

Part A: Count Intervals After Deletion

This is straightforward—just return len(result) from the delete operation.

Part B: Add K Elements to Minimize Intervals

Problem: After deletion, you have a set of intervals. You can add up to K elements back. What elements should you add to minimize the total number of intervals?

Example:

# After deletion
intervals = [(1, 3), (5, 7), (9, 11), (15, 20)]
# 4 intervals with gaps at: 4, 8, 12, 13, 14

# K = 1: Add 4 → [(1, 7), (9, 11), (15, 20)] (3 intervals)
# K = 2: Add 4, 8 → [(1, 11), (15, 20)] (2 intervals)
# K = 5: Add 4, 8, 12, 13, 14 → [(1, 20)] (1 interval)

Algorithm:

1. Calculate gap sizes between consecutive intervals
2. Sort gaps by size (smallest first)
3. Fill the smallest K gaps to minimize interval count

def minimize_intervals_with_k_additions(intervals, k):
    """
    Add up to K elements to minimize number of intervals.

    Returns:
        - Minimum number of intervals achievable
        - List of values to add
    """
    if len(intervals) <= 1:
        return len(intervals), []

    # Calculate gaps between consecutive intervals
    gaps = []
    for i in range(len(intervals) - 1):
        end_current = intervals[i][1]
        start_next = intervals[i + 1][0]
        gap_size = start_next - end_current - 1

        if gap_size > 0:
            gaps.append({
                'size': gap_size,
                'start': end_current + 1,
                'end': start_next - 1,
                'index': i
            })

    # Sort by gap size (prioritize small gaps)
    gaps.sort(key=lambda g: g['size'])

    # Greedily fill gaps
    elements_to_add = []
    merged_count = 0

    for gap in gaps:
        if k >= gap['size']:
            # Fill entire gap
            elements_to_add.extend(range(gap['start'], gap['end'] + 1))
            k -= gap['size']
            merged_count += 1
        else:
            # Partial fill (may not merge intervals)
            break

    min_intervals = len(intervals) - merged_count
    return min_intervals, elements_to_add

# Example
intervals = [(1, 3), (5, 7), (9, 11), (15, 20)]
min_count, to_add = minimize_intervals_with_k_additions(intervals, 2)
print(f"Minimum intervals: {min_count}")  # 3
print(f"Add elements: {to_add}")  # [4, 8]

Time Complexity: O(n log n) for sorting gaps

Edge Cases

1. Empty intervals: Return empty list
2. Single interval, single element: Return empty list if deleted
3. Index out of bounds: Should validate or raise error
4. Delete first element: Adjust start of first interval
5. Delete last element: Adjust end of last interval
6. Very large intervals: Algorithm works with large numbers (e.g., (1, 10^9))
7. Consecutive single-element intervals: [(1,1), (2,2), (3,3)] should work correctly

Test Cases

def test_edge_cases():
    # Empty intervals
    assert delete_from_intervals([], 0) == []

    # Single element interval
    assert delete_from_intervals([(5, 5)], 0) == []

    # Delete first element of first interval
    assert delete_from_intervals([(1, 5), (10, 12)], 0) == [(2, 5), (10, 12)]

    # Delete last element of last interval
    assert delete_from_intervals([(1, 5), (10, 12)], 7) == [(1, 5), (10, 11)]

    # Large interval
    assert delete_from_intervals([(1, 1000000000)], 500000001) == [
        (1, 500000001), (500000003, 1000000000)
    ]

    # Consecutive single-element intervals
    assert delete_from_intervals([(1, 1), (2, 2), (3, 3)], 1) == [(1, 1), (3, 3)]

    print("All edge case tests passed!")

test_edge_cases()

Related Problems

• LeetCode 56: Merge Intervals
• LeetCode 57: Insert Interval
• LeetCode 228: Summary Ranges
• LeetCode 352: Data Stream as Disjoint Intervals
• LeetCode 715: Range Module