In this article of my series Advent of Code 2025, where I discuss my solutions to daily puzzle, and hope to get some amazing feedback from you guys about my solutions(or just anything), I discuss today’s puzzle. As usual this goes without saying that DON’T READ AHAED, IT CONTAINS SPOILERs.

Introduction

Today’s puzzle followed from yesterday’s forklift operations, the forklifts were free, and we used them to break though the wall. And know what, the elves found that they had a cafeteria all along. But you hear “At this rate, we won't have any time left to put the wreaths up in the dining hall!” coming from the kitchen. You go in to investigate. "If only we hadn't switched to the new inventory management system right before Christmas!" another Elf exclaims. You ask what's going on.

The elves can’t figure out which ingredients are fresh and which are spoiled. Good person that you are you thought of helping them. You asked them how does it work, they give you their entire database’s copy and that’s the puzzle input today

Input Format

The database operates on ingredient IDs. It consists of a list of fresh ingredient ID ranges, a blank line, and a list of available ingredient IDs.

The fresh ID ranges are inclusive: the range 3-5 means that ingredient IDs 3, 4, and 5 are all fresh. The ranges can also overlap;(important point) an ingredient ID is fresh if it is in any range.

Puzzle 1

We have to find the number of ingredients which are fresh. This involves a simple membership check in each of the ranges. I know that it ain’t efficient as many intervals overlap and some searched are just useless, but I won’t do that here as it a necessity in the second puzzle and I will suggest implementations while discussing puzzle 2(and how this one could be improved)

In the given example above only 3 are fresh (5, 11 and 17)

Implementation

Input

I used a std::vector<pair> to represent the list of ranges and a std::set to represent the set of ingredients IDs.

vector<pair<unsigned long long, unsigned long long>> ranges;
set<unsigned long long> iids;
string line;
while (getline(cin, line)) {
  if (line.empty()) {
    break;
  }
  auto dash = line.find('-');
  auto a = stoull(line.substr(0, dash));
  auto b = stoull(line.substr(dash + 1));
  ranges.push_back({a, b});
}
while (getline(cin, line)) {
  if (line.empty()) {
    break;
  }
  iids.insert(stoull(line));
}

Solution

• Just check for each ingredient if it lies in any range.

int ans = 0;
for (const int iid : iids) {
    for (const auto [a, b] : ranges) {
        if (a <= iid <= b)
            ans += 1;
    }
}
cout << ans << endl;

Complexity Analysis

Input

Let the number of ranges is $R$, number of ingredients IDs be $I$ and maximum line length(maximum number of characters / digits per line) be $L$

Reading Ranges

Per line:

• getline → $O(L)$

• line.find('-') → $O(L)$

• line.substr(0, dash) and line.substr(dash + 1) → each $O(L)$ (they allocate and copy)

• stoull(...) on those substrings → \(O(\text{#digits}) ⊆ O(L)\)

• ranges.push_back → amortized $O(1)$

Total: \(O(R\cdot4L)\)

Reading Ingredients IDs

Per line:

• getline → $O(L)$

• stoull(line) → $O(L)$

• iids.insert(...) for std::set → \(O(\log \text{|iid|})\)

Total insertion cost \(\log1 + \log2 + \dots \log(I - 1) = \log((I -1)!) \leq \log(I!) \in O(I\log I)\) (Because \(x! \leq x^x\))

Total: \(O(I\cdot 2L + I \log I)\)

Combined

Total cost: \(O(R \cdot 4L + I\cdot 2L + I \log I)\), or simply \(O(2L\cdot (2R + I) + I \log I)\)

Assuming $L$(line length) is bounded and small

Improvements

Instead of a ordered set(std::set), if we used a Hash Set(std::unordered_set, we would get a average time of $O(1)$ while insertion and hence, total time complexity: \(O(2L\cdot (2R + I) + I)\)

Solution

Double Loop, therefore: \(O(I\cdot R)\)

Final

Total: \(O(2L\cdot (2R + I) + I + I \cdot R)\)

Also space: \(O(R + I)\)

Puzzle 2

The Elves would like to know all of the IDs that the fresh ingredient ID ranges consider to be fresh.(Just the count to be honest)

For a given range $[a, b]$ there are total \(b - a + 1\) elements in the range, but we can’t add this values for over every freaking range, as they are overlapping, so we have to remove this characteristic, and I will try my best to explain it here, but this problem is based on Leetcode - 56 - Merge Intervals, and there are some great people who have explained the solution, you can always look at their solution or even the official editorial.

Intuition and Logic

Before diving into the exact steps, let me build the intuition of the solution. Let me ask you which of the intervals can/should/need to be merged to remove overlappicity(if that’s a word) and which intervals should not interact with each other in this process of merging. Let me make a diagram for you to understand.

Just think for a while and think which of these should be merged into one intervals, and which one would be left as it is.

Intervals 1, 2 and 3 will be merged and Interval 4 will be left as it is. What was the thing that decided which intervals will be merged? And what thing decided the range of these newly merged intervals?

Let me answer the first question, and I think the answer to the second question will be clear? The thing that decides is the starting point of interval. For two intervals, they’ll be merged if and only if either intervals’ start lie in the other. And the starting point of this newly formed interval will be the minimum of these intervals’ starting points. So if I start with the interval which starts at the earliest, and process each interval in order of their starting point, all the intervals that need to be merged would come next to each other. And the thing that decides the new endpoint(or range) of these intervals is — the ending points. Maximum of these will be the new endpoint.

So the first step should be to sort these intervals, and starting with first interval, whenever we encounter each interval, we first check if the start of this interval lies in the list of merged intervals’(initially empty) last entry(which is also an interval). If not, then insert to the list, as this is the new un-overlapping interval, this will be the new last entry. If it does overlap, update the list’s last entry’s end according to this.

Solution

• Sort the intervals according to their starting points

• Process each interval

• If the new list is empty or this interval does not overlap with list’s last interval, insert this interval

• If it does overlap, update the list’s last interval’s endpoint

vector<pair<unsigned long long, unsigned long long>>
merge(vector<pair<unsigned long long, unsigned long long>> &intervals) {

  sort(intervals.begin(), intervals.end());

  vector<pair<unsigned long long, unsigned long long>> merged;

  for (const auto &interval : intervals) {
    // if the list of merged intervals is empty or if the current
    // interval does not overlap with the previous, simply append it.
    if (merged.empty() || merged.back().second < interval.first) {
      merged.push_back(interval);
    }
    // otherwise, there is overlap, so we merge the current and previous
    // intervals.
    else {
      merged.back().second = max(merged.back().second, interval.second);
    }
  }
  return merged;
}

Implementation

We just use this function, and since these new intervals are independent and non overlapping, we can just individually count each of these intervals’ count and add them up

unsigned long long ans = 0;
auto final_interval = merge(ranges);
for (const auto v : final_interval) ans += v.second - v.first + 1;
cout << ans << endl;

Complexity Analysis

Merge Operation

• Time Complexity: Sorting + Merging → \(O(R \log R + R)\)

• Space Complexity: Sorting + Merging → $O(2R)$(One for sorting and another as the merged intervals will be stored in a separate list)

Final Count calculation

• Time complexity: $O(R)$

Total

• Time complexity: \(O(2R + R\log R)\)

• Space Complexity: $O(2R)$

Improvements to Solution of Puzzle 1

• Since the new list of intervals is sorted, we can do a binary search, to check if ingredient id is in the valid range.

int ans = 0;
for (auto iid : iids) {
    int lo = 0, hi = merged.size() - 1;

    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        auto [a, b] = merged[mid];
        if (iid < a)
            hi = mid - 1;
        else if (iid > b)
            lo = mid + 1;
        else {
            ans++;
            break;
        }
    }
}

• Improved final time complexity: \(O(2L\cdot (2R + I) + I + I \cdot \log R)\)

Conclusion

This one looked chaotic at first glance, but the moment I recognized the interval pattern, it turned into a very comfortable problem. Days like these are fun because they use real interview-style thinking without unnecessary fluff

Signing off