Problem Description

Alice and Bob are planning separate trips to Rome. You need to calculate how many days they will both be in the city at the same time.

You are given four date strings:

• arriveAlice: The date Alice arrives in Rome
• leaveAlice: The date Alice leaves Rome
• arriveBob: The date Bob arrives in Rome
• leaveBob: The date Bob leaves Rome

Each date is formatted as "MM-DD" (a 5-character string where MM is the month and DD is the day). Both the arrival and departure dates are inclusive, meaning if someone arrives on "03-15" and leaves on "03-17", they are in Rome for 3 days (15th, 16th, and 17th).

Your task is to find the total number of days when both Alice and Bob are in Rome together. If their stays don't overlap at all, return 0.

The problem guarantees:

• All dates are in the same calendar year
• The year is not a leap year (February has 28 days)
• The days per month follow: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

For example, if Alice is in Rome from "08-15" to "08-18" and Bob is in Rome from "08-16" to "08-19", they overlap for 3 days (16th, 17th, and 18th).

The solution approach converts each date to the day number of the year (1-365), finds the overlapping period by taking the later arrival date and earlier departure date, then calculates the difference. If the result is negative (no overlap), it returns 0.

Intuition

To find the overlap between two time periods, we need to think about when an overlap actually occurs. Two periods overlap when one starts before the other ends, and vice versa. The overlapping period, if it exists, starts at the later of the two arrival dates and ends at the earlier of the two departure dates.

Working with dates in "MM-DD" format is cumbersome for calculations. A key insight is to convert dates to a single number - the day of the year. For instance, "01-01" becomes day 1, "01-31" becomes day 31, and "02-01" becomes day 32. This transformation allows us to use simple arithmetic to find the overlap.

Once we have the dates as day numbers:

• The overlap starts on day max(arriveAlice_day, arriveBob_day)
• The overlap ends on day min(leaveAlice_day, leaveBob_day)
• The number of overlapping days is end - start + 1 (we add 1 because both endpoints are inclusive)

If the calculated end day is before the start day, it means there's no overlap, so we return 0.

The conversion formula for a date "MM-DD" to day of year is: sum up all the days in the months before month MM, then add DD. For example, "03-05" (March 5th) would be 31 (January) + 28 (February) + 5 = 64, making it the 64th day of the year.

This approach elegantly handles all edge cases - whether one person's entire stay is within the other's, partial overlaps, or no overlap at all - through the simple max(end - start + 1, 0) calculation.

Learn more about Math patterns.

Solution Approach

The implementation follows a straightforward approach of converting dates to day-of-year numbers and finding the overlap:

Step 1: Find the overlap period boundaries

• a = max(arriveAlice, arriveBob): Gets the later arrival date (start of potential overlap)
• b = min(leaveAlice, leaveBob): Gets the earlier departure date (end of potential overlap)

Since the date strings are in "MM-DD" format, string comparison works correctly here. For example, "08-15" > "08-10" and "09-01" > "08-31".

Step 2: Define days per month

• days = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31): A tuple storing the number of days in each month (0-indexed)

Step 3: Convert dates to day-of-year numbers

• For the start date a:

  • int(a[:2]) extracts the month (first 2 characters)
  • sum(days[:int(a[:2]) - 1]) sums all days in months before this month
  • int(a[3:]) extracts the day (characters after the hyphen)
  • x = sum(days[:int(a[:2]) - 1]) + int(a[3:]) gives the day number of the year

• Similarly for end date b:

  • y = sum(days[:int(b[:2]) - 1]) + int(b[3:])

For example, if a = "03-05":

• Month = 3, Day = 5
• Days before March = sum(days[:2]) = 31 + 28 = 59
• Day of year = 59 + 5 = 64

Step 4: Calculate overlapping days

• max(y - x + 1, 0):
  • If y >= x, there's an overlap of y - x + 1 days (inclusive counting)
  • If y < x, there's no overlap, so return 0

The max(..., 0) ensures we never return a negative number when there's no overlap between Alice and Bob's stays.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example:

• Alice arrives: "08-15" and leaves: "08-18"
• Bob arrives: "08-16" and leaves: "08-19"

Step 1: Find overlap boundaries

• Start of overlap: a = max("08-15", "08-16") = "08-16" (Bob arrives later)
• End of overlap: b = min("08-18", "08-19") = "08-18" (Alice leaves earlier)

Step 2: Set up days per month

• days = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

Step 3: Convert to day-of-year numbers

For start date "08-16":

• Month = 8, Day = 16
• Days in months before August: sum(days[:7]) = 31 + 28 + 31 + 30 + 31 + 30 + 31 = 212
• Day of year: x = 212 + 16 = 228

For end date "08-18":

• Month = 8, Day = 18
• Days in months before August: sum(days[:7]) = 212 (same as above)
• Day of year: y = 212 + 18 = 230

Step 4: Calculate overlap

• Overlapping days: max(230 - 228 + 1, 0) = max(3, 0) = 3

The result is 3 days, which matches our expectation: they're both in Rome on August 16th, 17th, and 18th.

Edge Case Example - No Overlap: If Alice leaves "08-15" and Bob arrives "08-16":

• Start: a = "08-16" → day 228
• End: b = "08-15" → day 227
• Overlap: max(227 - 228 + 1, 0) = max(0, 0) = 0

The algorithm correctly returns 0 when there's no overlap.

Solution Implementation

Time and Space Complexity

The time complexity is O(C), where C is a constant. This is because:

• Parsing the month and day from the date strings takes O(1) time
• The sum() function is called twice on slices of the days tuple, but since there are at most 12 months, each sum operation takes at most O(12) = O(1) time
• The max() and min() operations on strings are O(1) since date strings have fixed length
• All other operations (integer conversions, arithmetic) are O(1)

The space complexity is O(C), where C is a constant. This is because:

• The days tuple stores exactly 12 integers, requiring O(12) = O(1) space
• Variables a, b, x, and y each store a single value, requiring O(1) space
• No data structures that grow with input size are used

Since all operations and storage requirements are bounded by constants independent of input size, both complexities are O(C).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Overlap Calculation - Off-by-One Error

The most common mistake is forgetting to add 1 when calculating the number of overlapping days. Since both arrival and departure dates are inclusive, the formula should be end - start + 1, not just end - start.

Incorrect Implementation:

# Wrong - missing the +1
return max(end_day_of_year - start_day_of_year, 0)

Why it's wrong: If Alice and Bob are both in Rome on the same single day (e.g., both on day 100), the calculation would give 100 - 100 = 0 days, when it should be 1 day.

Correct Implementation:

# Correct - includes both endpoints
return max(end_day_of_year - start_day_of_year + 1, 0)

2. Incorrect Month Indexing When Calculating Day of Year

Another frequent error is mishandling the month index when summing days. Since months are 1-indexed (January = 1) but the days_in_month tuple is 0-indexed, you need to subtract 1 from the month number.

Incorrect Implementation:

# Wrong - doesn't account for 0-based indexing
start_day_of_year = sum(days_in_month[:start_month]) + start_day

Why it's wrong: For March 5th (month = 3), this would sum days for January, February, AND March (indices 0, 1, 2), adding an extra 31 days.

Correct Implementation:

# Correct - properly handles the indexing
start_day_of_year = sum(days_in_month[:start_month - 1]) + start_day

3. String Parsing Errors

Be careful with string slicing indices. The date format is "MM-DD" with the hyphen at index 2.

Incorrect Implementation:

# Wrong indices for day extraction
start_day = int(overlap_start[2:])  # Would include the hyphen

Correct Implementation:

# Correct - skips the hyphen at index 2
start_day = int(overlap_start[3:])  # Gets characters from index 3 onward

Complete Corrected Solution:

class Solution:
    def countDaysTogether(
        self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str
    ) -> int:
        # Find overlap boundaries
        overlap_start = max(arriveAlice, arriveBob)
        overlap_end = min(leaveAlice, leaveBob)
      
        # Days per month (non-leap year)
        days_in_month = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
      
        # Convert to day of year (remember: month-1 for 0-based indexing)
        start_day_of_year = sum(days_in_month[:int(overlap_start[:2]) - 1]) + int(overlap_start[3:])
        end_day_of_year = sum(days_in_month[:int(overlap_end[:2]) - 1]) + int(overlap_end[3:])
      
        # Calculate overlap (remember: +1 for inclusive counting)
        return max(end_day_of_year - start_day_of_year + 1, 0)