Insert Interval – Clean Python Solution with Intuition (LeetCode 57)

Insert Interval (LeetCode 57)

The Insert Interval problem looks simple at first glance, but it tests how well you understand interval overlapping and edge cases.

The goal is to insert a new interval into a list of already sorted, non-overlapping intervals and merge where necessary — all while maintaining the sorted order.

---

🧠 Key Observations

• The intervals are already sorted by start time.
• There are only three possible cases while traversing intervals.
• We can process everything in a single pass.

---

📌 Three Possible Cases

1. Current interval is completely after newInterval
   → Insert newInterval and append the rest.
2. Current interval is completely before newInterval
   → Just add it to the result.
3. Overlapping intervals
   → Merge by expanding newInterval.

---

🧪 Example

Intervals = [[1,3],[6,9]]
New Interval = [2,5]

Output = [[1,5],[6,9]]

---

💡 Python Implementation

class Solution:
    def insert(self, intervals, newInterval):
        result = []

        for index, i in enumerate(intervals):
            if i[0] > newInterval[1]:
                result.append(newInterval)
                return result + intervals[index:]
            elif i[1] < newInterval[0]:
                result.append(i)
            else:
                newInterval = [
                    min(i[0], newInterval[0]),
                    max(i[1], newInterval[1])
                ]

        result.append(newInterval)
        return result

---

⏱ Time & Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(n) (for result array)

---

🔗 GitHub Source Code

You can find the complete solution on GitHub:

👉 View Solution on GitHub

---

🚀 Final Thoughts

This problem is a great example of how breaking logic into clear cases can lead to a clean and efficient solution.

If you understand this approach, you'll notice the same idea appearing in many other interval-based problems.