2409. Count Days Spent Together - Solution

Q: 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.

Q: 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).

Q: 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.

The problem

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.

Python

def date_to_day_of_year(date):
    days_per_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    month, day = map(int, date.split('-'))
    return sum(days_per_month[:month-1]) + day


def count_days_together(arriveAlice, leaveAlice, arriveBob, leaveBob):
    arrive_alice = date_to_day_of_year(arriveAlice)
    leave_alice = date_to_day_of_year(leaveAlice)
    arrive_bob = date_to_day_of_year(arriveBob)
    leave_bob = date_to_day_of_year(leaveBob)

    start = max(arrive_alice, arrive_bob)
    end = min(leave_alice, leave_bob)

    return max(0, end - start + 1)

# Example usage:
arriveAlice = "08-15"
leaveAlice = "08-18"
arriveBob = "08-16"
leaveBob = "08-19"
print(count_days_together(arriveAlice, leaveAlice, arriveBob, leaveBob))

Java

public class Main {
    public static void main(String[] args) {
        String arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19";
        System.out.println(countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob));
    }

    public static int dateToDayOfYear(String date) {
        int[] daysPerMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int month = Integer.parseInt(date.substring(0, 2));
        int day = Integer.parseInt(date.substring(3, 5));
        int dayOfYear = 0;
        for (int i = 0; i < month - 1; i++) {
            dayOfYear += daysPerMonth[i];
        }
        return dayOfYear + day;
    }

    public static int countDaysTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {
        int arriveAl = dateToDayOfYear(arriveAlice);
        int leaveAl = dateToDayOfYear(leaveAlice);
        int arriveBo = dateToDayOfYear(arriveBob);
        int leaveBo = dateToDayOfYear(leaveBob);

        int start = Math.max(arriveAl, arriveBo);
        int end = Math.min(leaveAl, leaveBo);

        return (start <= end) ? (end - start + 1) : 0;
    }
}

C++

#include <iostream>
#include <string>

int daysInYear(std::string date) {
    int daysPerMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int month = std::stoi(date.substr(0, 2));
    int day = std::stoi(date.substr(3, 2));
    int dayOfYear = 0;
    for (int i = 0; i < month - 1; ++i) {
        dayOfYear += daysPerMonth[i];
    }
    return dayOfYear + day;
}

int countDaysTogether(std::string arriveAlice, std::string leaveAlice, std::string arriveBob, std::string leaveBob) {
    int arriveAl = daysInYear(arriveAlice);
    int leaveAl = daysInYear(leaveAlice);
    int arriveBo = daysInYear(arriveBob);
    int leaveBo = daysInYear(leaveBob);

    int start = std::max(arriveAl, arriveBo);
    int end = std::min(leaveAl, leaveBo);

    return (start <= end) ? (end - start + 1) : 0;
}

int main() {
    std::string arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19";
    std::cout << countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob) << std::endl;
    return 0;
}

JavaScript

function dateToDayOfYear(date) {
    const daysPerMonth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    let [month, day] = date.split('-').map(Number);
    let dayOfYear = 0;
    for (let i = 0; i < month - 1; i++) {
        dayOfYear += daysPerMonth[i];
    }
    return dayOfYear + day;
}

function countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob) {
    const arriveAliceDay = dateToDayOfYear(arriveAlice);
    const leaveAliceDay = dateToDayOfYear(leaveAlice);
    const arriveBobDay = dateToDayOfYear(arriveBob);
    const leaveBobDay = dateToDayOfYear(leaveBob);

    const start = Math.max(arriveAliceDay, arriveBobDay);
    const end = Math.min(leaveAliceDay, leaveBobDay);

    return Math.max(0, end - start + 1);
}

console.log(countDaysTogether("08-15", "08-18", "08-16", "08-19"));

#include <stdio.h>
#include <string.h>

int convertToDayOfYear(const char* date) {
    int daysPerMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int month, day;
    sscanf(date, "%d-%d", &month, &day);
    int dayOfYear = 0;
    for (int i = 0; i < month - 1; i++) {
        dayOfYear += daysPerMonth[i];
    }
    dayOfYear += day;
    return dayOfYear;
}

int countDaysTogether(char* arriveAlice, char* leaveAlice, char* arriveBob, char* leaveBob) {
    int arriveAl = convertToDayOfYear(arriveAlice);
    int leaveAl = convertToDayOfYear(leaveAlice);
    int arriveBo = convertToDayOfYear(arriveBob);
    int leaveBo = convertToDayOfYear(leaveBob);

    int start = (arriveAl > arriveBo) ? arriveAl : arriveBo;
    int end = (leaveAl < leaveBo) ? leaveAl : leaveBo;

    return (start <= end) ? (end - start + 1) : 0;
}

int main() {
    char arriveAlice[] = "08-15", leaveAlice[] = "08-18", arriveBob[] = "08-16", leaveBob[] = "08-19";
    printf("%d\n", countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob));
    return 0;
}

using System;

public class Program
{
    public static void Main()
    {
        string arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19";
        Console.WriteLine(CountDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob));
    }

    public static int DateToDayOfYear(string date)
    {
        int[] daysPerMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        var parts = date.Split('-');
        int month = int.Parse(parts[0]);
        int day = int.Parse(parts[1]);
        int dayOfYear = 0;
        for (int i = 0; i < month - 1; i++)
        {
            dayOfYear += daysPerMonth[i];
        }
        return dayOfYear + day;
    }

    public static int CountDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob)
    {
        int arriveAl = DateToDayOfYear(arriveAlice);
        int leaveAl = DateToDayOfYear(leaveAlice);
        int arriveBo = DateToDayOfYear(arriveBob);
        int leaveBo = DateToDayOfYear(leaveBob);

        int start = Math.Max(arriveAl, arriveBo);
        int end = Math.Min(leaveAl, leaveBo);

        return (start <= end) ? (end - start + 1) : 0;
    }
}

The Python solution employs list and string manipulation functions to convert date strings into a day of the year format. After conversion, it uses max and min functions to calculate the overlapping days effectively.

Complexity

Time Complexity: O(1) — Conversion and calculation operations are performed in constant time.
Space Complexity: O(1) — Only a fixed amount of additional space is used.

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.

Python

def count_days_together(arriveAlice, leaveAlice, arriveBob, leaveBob):
    days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

    def day_of_year(date):
        month, day = map(int, date.split('-'))
        return sum(days_in_month[:month-1]) + day

    start_alice, end_alice = map(day_of_year, (arriveAlice, leaveAlice))
    start_bob, end_bob = map(day_of_year, (arriveBob, leaveBob))

    return max(0, min(end_alice, end_bob) - max(start_alice, start_bob) + 1)

print(count_days_together("08-15", "08-18", "08-16", "08-19"))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19";
        System.out.println(countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob));
    }

    public static int countDaysTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {
        int[] daysPerMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int arriveAliceDay = calculateDays(arriveAlice, daysPerMonth);
        int leaveAliceDay = calculateDays(leaveAlice, daysPerMonth);
        int arriveBobDay = calculateDays(arriveBob, daysPerMonth);
        int leaveBobDay = calculateDays(leaveBob, daysPerMonth);

        int start = Math.max(arriveAliceDay, arriveBobDay);
        int end = Math.min(leaveAliceDay, leaveBobDay);

        return Math.max(0, end - start + 1);
    }

    private static int calculateDays(String date, int[] daysPerMonth) {
        int month = Integer.parseInt(date.substring(0, 2));
        int day = Integer.parseInt(date.substring(3, 5));
        int dayOfYear = day;
        for (int i = 0; i < month - 1; i++) {
            dayOfYear += daysPerMonth[i];
        }
        return dayOfYear;
    }
}

C++

#include <iostream>
#include <vector>
#include <string>

int calculateDays(std::string arrive, std::string leave) {
    std::vector<int> days_in_month = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int arriveMonth = std::stoi(arrive.substr(0, 2));
    int arriveDay = std::stoi(arrive.substr(3, 2));
    int leaveMonth = std::stoi(leave.substr(0, 2));
    int leaveDay = std::stoi(leave.substr(3, 2));
    
    int startDays = std::accumulate(days_in_month.begin(), days_in_month.begin() + arriveMonth - 1, 0) + arriveDay;
    int endDays = std::accumulate(days_in_month.begin(), days_in_month.begin() + leaveMonth - 1, 0) + leaveDay;
    
    return endDays - startDays + 1;
}

int countDaysTogether(std::string arriveAlice, std::string leaveAlice, std::string arriveBob, std::string leaveBob) {
    int startAlice = calculateDays(arriveAlice, leaveAlice);
    int startBob = calculateDays(arriveBob, leaveBob);

    return std::max(0, std::min(startAlice, startBob));
}

int main() {
    std::string arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19";
    std::cout << countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob) << std::endl;
    return 0;
}

JavaScript

function countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob) {
    const daysPerMonth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

    function calculateDays(date) {
        const [month, day] = date.split('-').map(Number);
        return daysPerMonth.slice(0, month - 1).reduce((acc, days) => acc + days, 0) + day;
    }

    const startAlice = calculateDays(arriveAlice);
    const endAlice = calculateDays(leaveAlice);
    const startBob = calculateDays(arriveBob);
    const endBob = calculateDays(leaveBob);

    const start = Math.max(startAlice, startBob);
    const end = Math.min(endAlice, endBob);

    return Math.max(0, end - start + 1);
}

console.log(countDaysTogether("08-15", "08-18", "08-16", "08-19"));

#include <stdio.h>
#include <string.h>

int countDaysTogether(char* arriveAlice, char* leaveAlice, char* arriveBob, char* leaveBob) {
    int year_days[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};
    int monthA, dayA, monthL, dayL, monthB, dayB, monthBL, dayBL;
    sscanf(arriveAlice, "%d-%d", &monthA, &dayA);
    sscanf(leaveAlice, "%d-%d", &monthL, &dayL);
    sscanf(arriveBob, "%d-%d", &monthB, &dayB);
    sscanf(leaveBob, "%d-%d", &monthBL, &dayBL);

    int startA = year_days[monthA - 1] + dayA;
    int endA = year_days[monthL - 1] + dayL;
    int startB = year_days[monthB - 1] + dayB;
    int endB = year_days[monthBL - 1] + dayBL;

    int start = (startA > startB) ? startA : startB;
    int end = (endA < endB) ? endA : endB;

    return (start <= end) ? (end - start + 1) : 0;
}

int main() {
    char arriveAlice[] = "08-15", leaveAlice[] = "08-18", arriveBob[] = "08-16", leaveBob[] = "08-19";
    printf("%d\n", countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob));
    return 0;
}

using System;

public class Program
{
    public static void Main()
    {
        string arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19";
        Console.WriteLine(CountDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob));
    }

    public static int CalculateDays(string date)
    {
        int[] daysPerMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        string[] parts = date.Split('-');
        int month = int.Parse(parts[0]);
        int day = int.Parse(parts[1]);

        int dayOfYear = 0;

        for (int i = 0; i < month - 1; i++)
        {
            dayOfYear += daysPerMonth[i];
        }

        return dayOfYear + day;
    }

    public static int CountDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob)
    {
        int arriveAliceDay = CalculateDays(arriveAlice);
        int leaveAliceDay = CalculateDays(leaveAlice);
        int arriveBobDay = CalculateDays(arriveBob);
        int leaveBobDay = CalculateDays(leaveBob);

        int start = Math.Max(arriveAliceDay, arriveBobDay);
        int end = Math.Min(leaveAliceDay, leaveBobDay);

        return (start <= end) ? (end - start + 1) : 0;
    }
}

This Python strategy uses the elegance of list comprehensions and summation, keeping in technique to account for days before the input month. By constructing a minimal day_of_year function, the code flows directly from input to result without transient calculations.

Complexity

Time Complexity: O(1) — Month and day arrays incur uniform costs irrespective of input variation.
Space Complexity: O(1) — Only bounded space is needed per function execution offset.

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.

func countDaysTogether(arriveAlice string, leaveAlice string, arriveBob string, leaveBob string) int {
	days := []int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
	f := func(s string) int {
		m, _ := strconv.Atoi(s[:2])
		d, _ := strconv.Atoi(s[3:])
		res := 0
		for i := 0; i < m-1; i++ {
			res += days[i]
		}
		res += d
		return res
	}
	a, b := arriveAlice, leaveBob
	if arriveAlice < arriveBob {
		a = arriveBob
	}
	if leaveAlice < leaveBob {
		b = leaveAlice
	}
	x, y := f(a), f(b)
	ans := y - x + 1
	if ans < 0 {
		return 0
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Date Conversion to Day of Year	Time Complexity: O(1) — Conversion and calculation operations are performed in constant time. Space Complexity: O(1) — Only a fixed amount of additional space is used.
Direct Comparison Using Date Manipulation	Time Complexity: O(1) — Month and day arrays incur uniform costs irrespective of input variation. Space Complexity: O(1) — Only bounded space is needed per function execution offset.
Simulation	–

Complexity analysis

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.

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.

Count Days Spent Together solution and explanation

The problem

Approach overview

Approach 1: Using Date Conversion to Day of Year

Approach 2: Direct Comparison Using Date Manipulation

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Days Spent Together solution and explanation

The problem

Approach overview

Approach 1: Using Date Conversion to Day of Year

Approach 2: Direct Comparison Using Date Manipulation

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems