LeetCode 2409 - Count Days Spent Together

The problem asks us to calculate the number of days Alice and Bob spend together in Rome based on their respective arrival and departure dates. Each date is represented as a string in the format "MM-DD".

leetcodeeasymathstring

LeetCode Problem 2409

Difficulty: 🟢 Easy
Topics: Math, String

Solution

Problem Understanding

The problem asks us to calculate the number of days Alice and Bob spend together in Rome based on their respective arrival and departure dates. Each date is represented as a string in the format "MM-DD". The input consists of four strings: arriveAlice, leaveAlice, arriveBob, and leaveBob. The output should be the total number of overlapping days where both Alice and Bob are in Rome.

In simpler terms, the problem is about finding the intersection of two date ranges within a single non-leap year. If the ranges overlap, we count the number of overlapping days; if they do not overlap, the result is zero.

Constraints ensure that all dates are valid, occur in the same year, and Alice and Bob’s arrival dates are always before or equal to their leaving dates. This guarantees that we do not need to handle invalid ranges or leap years. Important edge cases include scenarios where their visits do not overlap, touch at exactly one day, or one visit is completely contained within the other.

Approaches

The brute-force approach would involve converting each date range into a list of all days of the year each person is present and then counting the common days. While this approach works, it is unnecessary because we do not need to iterate through every day explicitly.

The optimal approach leverages the fact that the overlap between two intervals can be determined using the maximum start date and the minimum end date. If the calculated start date is later than the end date, there is no overlap. Otherwise, the number of days together is simply the difference between the end and start dates plus one (because both endpoints are inclusive). To simplify the calculation, we convert dates into day-of-year integers using a cumulative sum of days per month.

Approach Time Complexity Space Complexity Notes
Brute Force O(N) O(N) Generate all days in both ranges and count intersections
Optimal O(1) O(1) Convert dates to day-of-year and compute overlap mathematically

Algorithm Walkthrough

  1. Define an array days_in_month representing the number of days in each month of a non-leap year. This will be [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31].
  2. Create a helper function day_of_year(date: str) that converts a "MM-DD" string into the corresponding day of the year. Split the string into month and day, sum the days of all preceding months, and add the day of the current month.
  3. Convert all four input dates into day-of-year integers using the helper function.
  4. Determine the overlapping range by taking the maximum of the two start dates and the minimum of the two end dates.
  5. If the overlapping start is later than the overlapping end, return 0 since there is no overlap.
  6. Otherwise, return overlap_end - overlap_start + 1 to count all inclusive overlapping days.

Why it works: By converting dates to day-of-year integers, we reduce the problem to finding the intersection of two numerical ranges. The invariant is that any overlapping range will have a start less than or equal to the end. This guarantees correctness.

Python Solution

class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        
        def day_of_year(date: str) -> int:
            month, day = map(int, date.split('-'))
            return sum(days_in_month[:month-1]) + day
        
        start_alice = day_of_year(arriveAlice)
        end_alice = day_of_year(leaveAlice)
        start_bob = day_of_year(arriveBob)
        end_bob = day_of_year(leaveBob)
        
        overlap_start = max(start_alice, start_bob)
        overlap_end = min(end_alice, end_bob)
        
        return max(0, overlap_end - overlap_start + 1)

The Python code first converts each date to its day-of-year representation. It then computes the overlapping range between Alice's and Bob's stays. The max(0, ...) ensures that if there is no overlap, we correctly return zero.

Go Solution

func countDaysTogether(arriveAlice string, leaveAlice string, arriveBob string, leaveBob string) int {
    daysInMonth := []int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}

    dayOfYear := func(date string) int {
        var month, day int
        fmt.Sscanf(date, "%02d-%02d", &month, &day)
        dayOfYear := day
        for i := 0; i < month-1; i++ {
            dayOfYear += daysInMonth[i]
        }
        return dayOfYear
    }

    startAlice := dayOfYear(arriveAlice)
    endAlice := dayOfYear(leaveAlice)
    startBob := dayOfYear(arriveBob)
    endBob := dayOfYear(leaveBob)

    overlapStart := max(startAlice, startBob)
    overlapEnd := min(endAlice, endBob)

    if overlapStart > overlapEnd {
        return 0
    }
    return overlapEnd - overlapStart + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

In Go, the dayOfYear function uses fmt.Sscanf to parse the date string, and helper functions max and min compute the overlapping range. The logic mirrors Python closely.

Worked Examples

Example 1: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"

Step-by-step:

  1. Convert dates to day-of-year: Alice [227, 230], Bob [228, 232].
  2. Overlap start = max(227, 228) = 228, overlap end = min(230, 232) = 230.
  3. Days together = 230 - 228 + 1 = 3.

Example 2: arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"

  1. Convert dates: Alice [274, 304], Bob [305, 365].
  2. Overlap start = max(274, 305) = 305, overlap end = min(304, 365) = 304.
  3. Overlap start > overlap end, return 0.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Conversion of dates to day-of-year and overlap calculation are constant time operations.
Space O(1) Only a fixed array and a few integers are used.

The approach is extremely efficient since it avoids any iteration through days and only relies on simple arithmetic.

Test Cases

# Provided examples
assert Solution().countDaysTogether("08-15", "08-18", "08-16", "08-19") == 3  # overlap 3 days
assert Solution().countDaysTogether("10-01", "10-31", "11-01", "12-31") == 0  # no overlap

# Edge cases
assert Solution().countDaysTogether("01-01", "12-31", "01-01", "12-31") == 365  # full year overlap
assert Solution().countDaysTogether("02-28", "03-01", "03-01", "03-01") == 1  # overlap at a single day
assert Solution().countDaysTogether("06-15", "06-15", "06-15", "06-15") == 1  # single day overlap
assert Solution().countDaysTogether("07-01", "07-10", "07-05", "07-05") == 1  # small overlap inside larger range
assert Solution().countDaysTogether("08-01", "08-10", "08-11", "08-20") == 0  # consecutive but no overlap
Test Why
Full year overlap Validates large overlapping ranges
Single day overlap Edge case where ranges overlap at exactly one day
No overlap Checks that the function correctly returns 0
Partial overlap inside larger range Tests that partial overlaps are correctly computed

Edge Cases

The first important edge case is when Alice and Bob’s stays overlap by exactly one day. This tests the inclusive nature of the range and ensures that the algorithm correctly counts the single overlapping day. The second case is when there is no overlap at all; this ensures that the max(0, ...) logic works correctly. The third edge case is when one range is entirely within the other, which ensures that the algorithm can handle nested intervals correctly and computes the exact number of overlapping days without missing any. All