Alice and Bob are traveling to Rome for separate business meetings.
You are given 4 strings arriveAlice, leaveAlice, arriveBob, and leaveBob. Alice will be in the city from the dates arriveAlice to leaveAlice (inclusive), while Bob will be in the city from the dates arriveBob to leaveBob (inclusive). Each will be a 5-character string in the format "MM-DD", corresponding to the month and day of the date.
Return the total number of days that Alice and Bob are in Rome together.
You can assume that all dates occur in the same calendar year, which is not a leap year. Note that the number of days per month can be represented as: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31].
Example 1:
Input: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19" Output: 3 Explanation: Alice will be in Rome from August 15 to August 18. Bob will be in Rome from August 16 to August 19. They are both in Rome together on August 16th, 17th, and 18th, so the answer is 3.
Example 2:
Input: arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31" Output: 0 Explanation: There is no day when Alice and Bob are in Rome together, so we return 0.
Constraints:
"MM-DD".Problem Overview: You receive four dates: Alice's arrival and leave dates, and Bob's arrival and leave dates. Each date is formatted as MM-DD. The goal is to count how many days both people are present at the same time during the same year.
The core observation: the problem reduces to finding the overlap between two date ranges. Once each date is converted to a comparable numeric value, the overlapping segment length becomes easy to compute using max(start) and min(end).
Approach 1: Convert Date to Day of Year (O(1) time, O(1) space)
Convert every MM-DD string into a single integer representing its position in the year (day-of-year). Use a prefix array containing the number of days before each month. Parse the month and day from the string, then compute dayOfYear = prefix[month-1] + day. After converting Alice and Bob's arrival and leave dates, compute the overlap using start = max(aliceArrive, bobArrive) and end = min(aliceLeave, bobLeave). If end < start, there is no overlap; otherwise the answer is end - start + 1. This approach is clean and constant time because the year length is fixed. It primarily uses simple arithmetic from math and straightforward string parsing.
Approach 2: Direct Date Comparison with Month Traversal (O(1) time, O(1) space)
Instead of converting the entire date to a numeric day-of-year value, compare dates using their month and day components. Parse each date into (month, day). To compute the overlap, determine the later arrival date and the earlier leaving date using month-first comparison, then day comparison if months match. Once the range is known, count the days between them by iterating through the months and summing their lengths. A static array storing month lengths simplifies this calculation. This approach works without explicitly flattening the calendar into a single number and demonstrates careful handling of date boundaries using basic math logic and string parsing.
Recommended for interviews: The day-of-year conversion approach is what most interviewers expect. It shows you can normalize a problem into a simpler numeric domain and compute range intersections cleanly. The direct comparison method still works and demonstrates understanding of calendar structure, but the conversion approach is shorter, less error-prone, and easier to reason about under time pressure.
This approach involves converting the given dates into the day of year format for easier manipulation. Each date can be mapped to a specific day between 1 and 365 (or 366 in a leap year). By converting the dates to numbers, we can calculate the intersection of Alice's and Bob's date ranges, and count their overlapping days together in Rome.
In the C solution, we first convert each date into a 'day of the year' using the helper function convertToDayOfYear. This function calculates the day number by iterating through the months and summing the days. We then determine the overlapping days using the maximum arrival date and minimum leave date between Alice and Bob. If the calculated start date is before the end date, we calculate the total overlap in days.
Time Complexity: O(1) — We perform constant time calculations for each date.
Space Complexity: O(1) — We require a fixed amount of space for calculations.
This approach involves direct string comparison and manipulation within the logic to ascertain overlap in Alice's and Bob's itineraries. This avoids intermediate step conversions, relying instead on direct date calculations.
This C example avoids changing date strings to integer representations directly. By applying indices to calculate cumulative day totals through the year (abbreviated from months to days), it interprets the timeline without cumbersome restructuring, computing overlaps directly within validation logic.
Time Complexity: O(1) — Directly processes each date independently with immediate memory fetches.
Space Complexity: O(1) — Sets up month-based year-day lookups without intermediary structures.
We convert the dates into days, and then calculate the number of days both people are in Rome.
The time complexity is O(C), and the space complexity is O(C). Here, C is a constant.
| Approach | Complexity |
|---|---|
| Using Date Conversion to Day of Year | Time Complexity: O(1) — We perform constant time calculations for each date. |
| Direct Comparison Using Date Manipulation | Time Complexity: O(1) — Directly processes each date independently with immediate memory fetches. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Date Conversion to Day of Year | O(1) | O(1) | Best general solution. Simplifies date ranges into integers for quick overlap calculation. |
| Direct Comparison with Month Traversal | O(1) | O(1) | Useful when you want to keep month/day structure without converting to a single index. |
2409. Count Days Spent Together | Biweekly Contest 87 | LeetCode 2409 • Bro Coders • 1,767 views views
Watch 7 more video solutions →Practice Count Days Spent Together with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor