Insert Interval into Sorted List in DSA C - Time & Space Complexity

Time Complexity: Insert Interval into Sorted List

O(n)

Understanding Time Complexity

We want to know how the time to insert a new interval into a sorted list changes as the list grows.

Specifically, how many steps does it take to find the right place and merge intervals if needed?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void insertInterval(int intervals[][2], int* size, int newInterval[2]) {
    int i = 0, pos = 0;
    while (i < *size && intervals[i][1] < newInterval[0]) i++;
    pos = i;
    while (i < *size && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = (intervals[i][0] < newInterval[0]) ? intervals[i][0] : newInterval[0];
        newInterval[1] = (intervals[i][1] > newInterval[1]) ? intervals[i][1] : newInterval[1];
        i++;
    }
    // Shift intervals and insert merged newInterval at pos
    // ... (shifting code omitted for brevity)
}
    

This code finds where to insert a new interval in a sorted list and merges overlapping intervals.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two while loops scanning parts of the intervals array.
• How many times: Each loop runs at most n times combined, where n is the number of intervals.

How Execution Grows With Input

As the number of intervals grows, the loops scan through the list to find overlaps and insertion point.

Input Size (n)	Approx. Operations
10	Up to 10 steps scanning intervals
100	Up to 100 steps scanning intervals
1000	Up to 1000 steps scanning intervals

Pattern observation: The number of steps grows roughly in direct proportion to the number of intervals.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows linearly with the number of intervals in the list.

Common Mistake

[X] Wrong: "Since the list is sorted, insertion can be done in constant time."

[OK] Correct: Even though the list is sorted, we must scan to find the correct position and merge overlaps, which takes time proportional to the list size.

Interview Connect

Understanding how to efficiently insert and merge intervals is a common skill that shows your ability to work with sorted data and handle edge cases.

Self-Check

"What if the intervals were stored in a balanced tree instead of an array? How would the time complexity change?"

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. Sort the list again after insertion without merging

B. Add the new interval at the end without merging

C. Remove all intervals that come before the new interval

D. Merge overlapping intervals and keep the list sorted

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. Inserting a new interval may cause overlaps.

2. Step 2: Determine the correct insertion approach

   We must merge any overlapping intervals with the new one and keep the list sorted to maintain the property.

3. Final Answer:

   Merge overlapping intervals and keep the list sorted -> Option D

4. Quick Check:

   Insert interval = merge + sort [OK]

Hint: Always merge overlaps to keep intervals sorted and non-overlapping [OK]

Common Mistakes:

• Inserting without merging causes overlaps
• Appending at the end breaks sorting
• Removing intervals unnecessarily

2. Which of the following C code snippets correctly declares a structure for an interval with start and end integers?

easy

A. typedef struct Interval { int start; int end; } Interval;

B. struct Interval { int start; int end; };

C. struct { int start; int end; } Interval;

D. typedef struct Interval { int start; int end; };

Solution

1. Step 1: Understand C struct typedef syntax

   To define a struct and typedef it simultaneously, use: typedef struct Name { ... } Name;

2. Step 2: Match the correct syntax

   typedef struct Interval { int start; int end; } Interval; uses typedef struct Interval { int start; int end; } Interval; which is correct.

3. Final Answer:

   typedef struct Interval { int start; int end; } Interval; -> Option A

4. Quick Check:

   typedef struct Name { ... } Name; = typedef struct Interval { int start; int end; } Interval; [OK]

Hint: Use typedef struct Name { ... } Name; for clean interval type [OK]

Common Mistakes:

• Missing typedef keyword
• Incorrect struct declaration without name
• Declaring variable instead of type

3. Given the sorted intervals: [[1,3], [6,9]] and a new interval [2,5], what will be the resulting list after insertion and merging?

medium

A. [[1,5], [6,9]]

B. [[1,3], [2,5], [6,9]]

C. [[2,5], [6,9]]

D. [[1,3], [6,9], [2,5]]

Solution

1. Step 1: Identify overlapping intervals

   The new interval [2,5] overlaps with [1,3] because 2 ≤ 3.

2. Step 2: Merge overlapping intervals

   Merge [1,3] and [2,5] into [1,5]. The interval [6,9] remains unchanged.

3. Final Answer:

   [[1,5], [6,9]] -> Option A

4. Quick Check:

   Merge [1,3] & [2,5] = [1,5] [OK]

Hint: Merge intervals if new start ≤ current end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Inserting new interval without sorting
• Appending new interval at wrong position

4. Consider this buggy C code snippet to insert an interval into a sorted list. What is the main error?

void insertInterval(Interval* intervals, int* size, Interval newInterval) {
    int i = 0;
    while (i < *size && intervals[i].end < newInterval.start) {
        i++;
    }
    intervals[i] = newInterval; // Bug here
    (*size)++;
}

medium

A. Increments size before insertion

B. Does not check for overlapping intervals

C. Overwrites an existing interval without shifting elements

D. Uses wrong comparison operator in while loop

Solution

1. Step 1: Analyze insertion logic

   The code finds position i but directly overwrites intervals[i] without moving later intervals.

2. Step 2: Identify the error impact

   Overwriting causes loss of data and corrupts the list. Proper insertion requires shifting elements right.

3. Final Answer:

   Overwrites an existing interval without shifting elements -> Option C

4. Quick Check:

   Overwrite without shift = data loss [OK]

Hint: Shift elements right before inserting new interval [OK]

Common Mistakes:

• Ignoring element shifting
• Not handling overlaps
• Incorrect loop conditions

5. You have intervals [[1,2], [3,5], [6,7], [8,10], [12,16]] and want to insert [4,8]. What is the final list after insertion and merging?

hard

A. [[1,2], [4,8], [12,16]]

B. [[1,2], [3,10], [12,16]]

C. [[1,2], [3,5], [4,8], [6,7], [8,10], [12,16]]

D. [[1,2], [3,8], [12,16]]

Solution

1. Step 1: Find intervals overlapping with [4,8]

   Intervals [3,5], [6,7], and [8,10] overlap with [4,8].

2. Step 2: Merge all overlapping intervals

   Merge [3,5], [6,7], [8,10], and [4,8] into [3,10].

3. Step 3: Construct final list

   Keep [1,2] and [12,16] unchanged. Final list: [[1,2], [3,10], [12,16]].

4. Final Answer:

   [[1,2], [3,10], [12,16]] -> Option B

5. Quick Check:

   Merge overlapping intervals = [3,10] [OK]

Hint: Merge all intervals overlapping new interval into one [OK]

Common Mistakes:

• Not merging all overlapping intervals
• Inserting without merging
• Removing intervals incorrectly