Count Days Spent Together

Easy

#2193Time: O(N), where N is the number of days in a year (365). The conversion of dates is constant time. The main work involves three loops: one to mark Alice's days, one for Bob's, and one to find common days. In the worst case, these loops run up to N times. Since N is a fixed constant (365), the complexity is technically O(1), but it's less efficient than a direct mathematical calculation.Space: O(N), where N is the number of days in a year. We use two boolean arrays of size 366 to store the presence of Alice and Bob for each day of the year.

Patterns

Math

Data structures

String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the calendar year and marks the days each person is in Rome. We can use two boolean arrays, one for Alice and one for Bob, of size 366 (to represent days 1 to 365). We first convert the given 'MM-DD' date strings into the corresponding day of the year. Then, we iterate through the date ranges for both Alice and Bob, marking the corresponding days as true in their respective arrays. Finally, we iterate through the arrays one more time to count the number of days where both Alice and Bob are present (i.e., both arrays have true at the same index).

Algorithm

Define an array daysInMonth to store the number of days in each month for a non-leap year: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31].
Create a helper function, getDayOfYear(String date), that takes a date string 'MM-DD' and converts it to an integer representing the day of the year (from 1 to 365). This function will parse the month and day, and use the daysInMonth array to calculate the total number of days.
In the main function, convert all four input date strings (arriveAlice, leaveAlice, arriveBob, leaveBob) into their day-of-the-year integer representations using the helper function.
Initialize two boolean arrays, alicePresence and bobPresence, of size 366, with all values as false.
Iterate from Alice's arrival day to her leave day, setting alicePresence[day] = true for each day.
Do the same for Bob, setting bobPresence[day] = true for each day he is in Rome.
Initialize a counter commonDays to 0.
Iterate from day 1 to 365. If alicePresence[day] and bobPresence[day] are both true, increment commonDays.
Return commonDays.

Walkthrough

1class Solution {2    public int countDaysSpentTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {3        int[] daysInMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};4        // Create a prefix sum array for quick lookup5        for (int i = 1; i < daysInMonth.length; i++) {6            daysInMonth[i] += daysInMonth[i-1];7        }8 9        int arriveAliceDay = getDayOfYear(arriveAlice, daysInMonth);10        int leaveAliceDay = getDayOfYear(leaveAlice, daysInMonth);11        int arriveBobDay = getDayOfYear(arriveBob, daysInMonth);12        int leaveBobDay = getDayOfYear(leaveBob, daysInMonth);13 14        boolean[] alicePresence = new boolean[366];15        boolean[] bobPresence = new boolean[366];16 17        for (int i = arriveAliceDay; i <= leaveAliceDay; i++) {18            alicePresence[i] = true;19        }20        for (int i = arriveBobDay; i <= leaveBobDay; i++) {21            bobPresence[i] = true;22        }23 24        int commonDays = 0;25        for (int i = 1; i <= 365; i++) {26            if (alicePresence[i] && bobPresence[i]) {27                commonDays++;28            }29        }30        return commonDays;31    }32 33    private int getDayOfYear(String date, int[] prefixSum) {34        int month = Integer.parseInt(date.substring(0, 2));35        int day = Integer.parseInt(date.substring(3, 5));36        return prefixSum[month - 1] + day;37    }38}

Complexity

Time

O(N), where N is the number of days in a year (365). The conversion of dates is constant time. The main work involves three loops: one to mark Alice's days, one for Bob's, and one to find common days. In the worst case, these loops run up to N times. Since N is a fixed constant (365), the complexity is technically O(1), but it's less efficient than a direct mathematical calculation.

Space

O(N), where N is the number of days in a year. We use two boolean arrays of size 366 to store the presence of Alice and Bob for each day of the year.

Trade-offs

Pros

The logic is straightforward and easy to follow, as it directly models the problem statement.
It's a robust approach that can be easily adapted if the rules for presence become more complex (e.g., non-contiguous days).

Cons

Uses more memory than necessary by creating two large arrays.
The time complexity is proportional to the number of days in the year, which is inefficient compared to a direct calculation.

A more efficient approach is to treat the problem as finding the length of the intersection of two intervals on a number line. First, we convert all dates into a single, comparable unit: the day of the year (an integer from 1 to 365). Alice's stay is an interval [startA, endA] and Bob's is [startB, endB]. The period they spend together is the intersection of these two intervals. The start of this intersection is the latest of the two arrival dates, and the end is the earliest of the two departure dates. If the calculated start of the overlap is after the end, it means there is no overlap.

Algorithm

Define a helper function or use a precomputed array to convert 'MM-DD' date strings into the day of the year (an integer from 1 to 365). A common way is to use a prefix sum array of the number of days in each month.
Convert the four input dates into four integers: aliceArrivalDay, aliceLeaveDay, bobArrivalDay, bobLeaveDay.
Determine the start of the overlapping period by finding the maximum of the two arrival days: startOfOverlap = Math.max(aliceArrivalDay, bobArrivalDay).
Determine the end of the overlapping period by finding the minimum of the two leave days: endOfOverlap = Math.min(aliceLeaveDay, bobLeaveDay).
Calculate the duration of the overlap. The number of days is endOfOverlap - startOfOverlap + 1.
If startOfOverlap is greater than endOfOverlap, the intervals do not overlap, and the number of common days is 0. This can be handled by taking Math.max(0, duration).
Return the calculated number of days.

Walkthrough

1class Solution {2    public int countDaysSpentTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {3        int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};4        // Create a prefix sum array for quick lookup5        for (int i = 1; i < days.length; i++) {6            days[i] += days[i-1];7        }8 9        int arriveAliceDay = getDayOfYear(arriveAlice, days);10        int leaveAliceDay = getDayOfYear(leaveAlice, days);11        int arriveBobDay = getDayOfYear(arriveBob, days);12        int leaveBobDay = getDayOfYear(leaveBob, days);13 14        int latestArrival = Math.max(arriveAliceDay, arriveBobDay);15        int earliestLeave = Math.min(leaveAliceDay, leaveBobDay);16 17        int overlap = earliestLeave - latestArrival + 1;18 19        return Math.max(0, overlap);20    }21 22    private int getDayOfYear(String date, int[] prefixSum) {23        int month = Integer.parseInt(date.substring(0, 2));24        int day = Integer.parseInt(date.substring(3, 5));25        return prefixSum[month - 1] + day;26    }27}

Complexity

Time

O(1). The process involves a fixed number of operations: four date conversions (each constant time), two comparisons (`Math.max`, `Math.min`), and one subtraction. The complexity does not depend on the length of the date intervals.

Space

O(1). We only need a few variables to store the calculated day numbers. The array to store the number of days in months has a fixed size (13), which is constant space.

Trade-offs

Pros

Extremely efficient in both time and space.
The solution is concise and based on a simple mathematical principle.

Cons

Requires recognizing the problem as an interval intersection problem, which might be slightly less intuitive than direct simulation.

Solutions

Solution

1class Solution {2private3  int[] days = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};4public5  int countDaysTogether(String arriveAlice, String leaveAlice, String arriveBob,6                        String leaveBob) {7    String a = arriveAlice.compareTo(arriveBob) < 0 ? arriveBob : arriveAlice;8    String b = leaveAlice.compareTo(leaveBob) < 0 ? leaveAlice : leaveBob;9    int x = f(a), y = f(b);10    return Math.max(y - x + 1, 0);11  }12private13  int f(String s) {14    int i = Integer.parseInt(s.substring(0, 2)) - 1;15    int res = 0;16    for (int j = 0; j < i; ++j) {17      res += days[j];18    }19    res += Integer.parseInt(s.substring(3));20    return res;21  }22}

1class Solution:2    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int: a = max(arriveAlice, arriveBob) b = min(leaveAlice, leaveBob) days = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31) x = sum(days[: int(a[: 2]) - 1]) + int(a[3:]) y = sum(days[: int(b[: 2]) - 1]) + int(b[3:]) return max(y - x + 1, 0)

1class Solution {2public:3  vector<int> days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};4  int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob,5                        string leaveBob) {6    string a = arriveAlice < arriveBob ? arriveBob : arriveAlice;7    string b = leaveAlice < leaveBob ? leaveAlice : leaveBob;8    int x = f(a), y = f(b);9    return max(0, y - x + 1);10  }11  int f(string s) {12    int m, d;13    sscanf(s.c_str(), "%d-%d", &m, &d);14    int res = 0;15    for (int i = 0; i < m - 1; ++i) {16      res += days[i];17    }18    res += d;19    return res;20  }21};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem