Skip to main content
Talentd

Count Days Spent Together - Solution & Explanation

EasyMathString18 min read
Practice this problem

Problem Statement

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:

  • All dates are provided in the format "MM-DD".
  • Alice and Bob's arrival dates are earlier than or equal to their leaving dates.
  • The given dates are valid dates of a non-leap year.

Approach Overview

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.

Approach 1: Using Date Conversion to Day of Year

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Direct Comparison Using Date Manipulation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Simulation

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Date Conversion to Day of Year

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.

Direct Comparison Using Date Manipulation

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.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Date Conversion to Day of YearO(1)O(1)Best general solution. Simplifies date ranges into integers for quick overlap calculation.
Direct Comparison with Month TraversalO(1)O(1)Useful when you want to keep month/day structure without converting to a single index.

Video Solution

2409. Count Days Spent Together | Biweekly Contest 87 | LeetCode 2409 • Bro Coders • 1,796 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Count Days Spent Together easy or hard?
LeetCode classifies this problem as Easy. The challenge is recognizing that the task is simply an interval overlap problem once dates are converted into comparable numeric values.
How to solve Count Days Spent Together in O(1)?
Parse each MM-DD string, convert it to a day-of-year value using a prefix sum array of month lengths, then compute the intersection of the two ranges. The overlapping segment length is max(0, min(leaveA, leaveB) - max(arriveA, arriveB) + 1). Since all operations involve fixed-size arrays and arithmetic, the complexity stays O(1).
What is the best approach for Count Days Spent Together?
The most common solution converts each date into its day-of-year index and then calculates the intersection of two ranges. After conversion, compute start = max(arrival dates) and end = min(leave dates). If end >= start, the overlapping days equal end - start + 1. This runs in O(1) time and O(1) space.
Is Count Days Spent Together asked at Google/Amazon/Meta?
Problems involving date normalization and interval overlap frequently appear in interviews at large tech companies. Variations of interval intersection and calendar computations are common screening questions because they test edge cases and clean arithmetic reasoning.
What data structure is used in Count Days Spent Together?
The solution typically uses a small array storing the number of days in each month. This array helps convert dates into day-of-year values quickly. Aside from that, the problem mainly relies on basic math and string parsing.
What is the time complexity of Count Days Spent Together?
Both common solutions run in O(1) time and O(1) space because the calendar size is fixed. Date parsing and arithmetic operations take constant time, and the number of months in a year never changes.
Count Days Spent Together Python or Java solution approach?
In Python or Java, split the MM-DD string to extract month and day, convert it to a day-of-year value using a prefix month array, then compute the overlap with max and min operations. The logic remains identical across languages and runs in constant time.

Ready to solve this problem?

Practice Count Days Spent Together with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Operations to Convert Time

Next

Number of Days Between Two Dates