1360. Number of Days Between Two Dates

EasyMathString
Leetcode Link

Problem Description

The task is to write a program that calculates the number of days between two given dates. The dates are provided in the string format 'YYYY-MM-DD', indicating the year, month, and day. The main challenge is to correctly handle the variations in the number of days in each month, leap years, and the possibility that the dates span multiple years. The solution requires attention to the rules that govern the Gregorian calendar, which include correct number of days in each month, leap year calculations, and the accumulation of days across multiple months and years.

Intuition

The intuition behind the provided solution lies in breaking down the task into smaller parts that are easier to manage:

  1. Understand leap years: Leap years need special attention because they have an extra day in February (29 days instead of 28). The solution includes a function isLeapYear to check if a given year is a leap year. The rule for determining a leap year is that it should be divisible by 4 but not by 100 unless it is also divisible by 400.

  2. Count days per month: The solution defines daysInMonth to handle the variation in the number of days per month, adjusting for leap years. An array holds the number of days in each month, with February being conditionally set to 28 or 29 days based on whether the year is a leap year.

  3. Calculate days since a reference date: To calculate the total number of days of a date, calcDays processes each date independently, starting from a reference year (1971 in this implementation). It accumulates total days year by year and month by month up to the given date. Days in full years are counted by adding 365 for each year plus an additional day for each leap year. Days in months are counted by accumulating the days for each month leading up to the given month in the specified year.

  4. Compute the absolute difference: Finally, the difference in days between the two dates is found by calculating the total days for each date since the reference date and subtracting the smaller one from the larger one to ensure a positive result. The abs function is used to return the absolute value of this difference.

This approach systematically adds up all the days from the reference date to each of the specified dates, and the difference between these sums represents the number of days between the dates.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Solution Approach

The implementation follows a straightforward algorithmic approach without using complex data structures or patterns. It focuses on accurately counting the days by considering each component of the date (year, month, day) one by one.

Here’s a step-by-step breakdown of the algorithm:

  1. Leap Year Check: The function isLeapYear(year: int) -> bool determines whether a given year is a leap year. This is used to add an extra day for leap years when counting days.

    1return year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)

  2. Days in Month Calculation: daysInMonth(year: int, month: int) -> int calculates the number of days in a given month for a specific year. It uses an array where each index corresponds to a month, with February’s days conditionally set to 29 if it is a leap year:

    1days = [31, 28 + int(isLeapYear(year)), 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
2return days[month - 1]

  3. Total Days Calculator: calcDays(date: str) -> int converts a YYYY-MM-DD format date into the total number of days elapsed since a reference date, which in this code is January 1, 1971. It does this by first summing up all the days for the full years that have passed and then adding the days for the full months that have passed in the current year:

    1year, month, day = map(int, date.split("-"))
2days = 0
3for y in range(1971, year):
4    days += 365 + int(isLeapYear(y))
5for m in range(1, month):
6    days += daysInMonth(year, m)
7days += day
8return days

  4. Calculation of the Difference Between Dates: The days between the two dates are calculated by finding the absolute difference between the total days from the reference date to each input date:

    1return abs(calcDays(date1) - calcDays(date2))

As you can see, the algorithm uses a combination of iteration and basic arithmetic operations to accurately calculate the total number of days between two dates. The problem can also be solved using Python's built-in datetime module, but this approach shows how it can be done manually, which could be beneficial in understanding how date calculations work or in environments where built-in date operations are not available.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's consider two dates for this example: 2023-01-12 and 2023-03-04. Our task is to find the number of days between these dates using the steps outlined in the solution approach.

  1. Leap Year Check: We first check if the years for both dates are leap years. Since we're only considering dates within 2023 for this example, this step is simple:

    1isLeapYear(2023) # returns False, because 2023 is not divisible by 4

    Since 2023 is not a leap year, February will have 28 days.

  2. Days in Month Calculation: We then calculate the number of days in each month up to the month before the given date for the year 2023:

    1daysInMonth(2023, 1) # returns 31 days for January
2daysInMonth(2023, 2) # returns 28 days for February, as it's not a leap year

    January has 31 days, and February, being in a non-leap year, has 28 days.

  3. Total Days Calculator: Now, let's convert each date to the total number of days elapsed since the reference date of January 1, 1971:

    1calcDays("2023-01-12") # we sum the days from 1971 to 2022, plus days in Jan 2023, and then add 12
2calcDays("2023-03-04") # we sum the days from 1971 to 2022, plus days in Jan and Feb 2023, and then add 4

    Without going through all the calculations step by step, let's assume the function calcDays returns the total days correctly according to the algorithm.

  4. Calculation of the Difference Between Dates: Finally, to find the difference in days between the two dates, we subtract the total days for 2023-01-12 from the total days for 2023-03-04 and take the absolute value:

    1abs(calcDays("2023-03-04") - calcDays("2023-01-12"))

    Suppose calcDays("2023-01-12") returns 19044 and calcDays("2023-03-04") returns 19095, then our calculation will be:

    1abs(19095 - 19044) # which gives us 51 days

    Based on our steps, there are 51 days between 2023-01-12 and 2023-03-04.

Through this small example, we illustrated how each step of the solution contributes to the final count of the days between two dates without relying on any external date-related libraries.

Solution Implementation

1class Solution:
2    def days_between_dates(self, date1: str, date2: str) -> int:
3        """Calculate the number of days between two dates."""
4      
5        def is_leap_year(year: int) -> bool:
6            """Check if a year is a leap year."""
7            return year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)
8      
9        def days_in_month(year: int, month: int) -> int:
10            """Calculate the number of days in a month for a given year."""
11            # Days in each month. For February in a leap year, add an extra day.
12            days_per_month = [
13                31,
14                28 + int(is_leap_year(year)),
15                31,
16                30,
17                31,
18                30,
19                31,
20                31,
21                30,
22                31,
23                30,
24                31,
25            ]
26            # Return the number of days in the specified month.
27            return days_per_month[month - 1]
28
29        def calculate_days(date: str) -> int:
30            """Calculate the total number of days from a fixed date to the given date."""
31            # Extract year, month, and day as integers from the date string.
32            year, month, day = map(int, date.split("-"))
33          
34            # Initialize the days counter.
35            days = 0
36          
37            # Count days for the full years up to the given year.
38            for y in range(1971, year):
39                days += 365 + int(is_leap_year(y))
40          
41            # Count days for the full months in the given year.
42            for m in range(1, month):
43                days += days_in_month(year, m)
44          
45            # Add the days in the given month.
46            days += day
47            return days
48
49        # Calculate the total days for each date and return their absolute difference.
50        return abs(calculate_days(date1) - calculate_days(date2))
51
1class Solution {
2    // Computes the number of days between two given dates
3    public int daysBetweenDates(String date1, String date2) {
4        // The absolute difference between the day counts gives the number of days between the two dates
5        return Math.abs(calculateDays(date1) - calculateDays(date2));
6    }
7
8    // Determines if a given year is a leap year
9    private boolean isLeapYear(int year) {
10        // A year is a leap year if it's divisible by 4 but not by 100, or it's divisible by 400
11        return (year % 4 == 0) && ((year % 100 != 0) || (year % 400 == 0));
12    }
13
14    // Returns the number of days in a given month for a given year
15    private int daysInMonth(int year, int month) {
16        // An array storing the number of days in each month
17        int[] daysPerMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
18        // Adjust February for leap years
19        daysPerMonth[1] += isLeapYear(year) ? 1 : 0;
20        // Return the number of days in the specified month
21        return daysPerMonth[month - 1];
22    }
23
24    // Calculates the total number of days from a fixed date (1971-01-01) to the given date
25    private int calculateDays(String date) {
26        // Parse the input date string to extract year, month, and day
27        int year = Integer.parseInt(date.substring(0, 4));
28        int month = Integer.parseInt(date.substring(5, 7));
29        int day = Integer.parseInt(date.substring(8));
30        int totalDays = 0;
31        // Add days for each year from the base year (1971) to the given year
32        for (int y = 1971; y < year; ++y) {
33            totalDays += isLeapYear(y) ? 366 : 365;
34        }
35        // Add days for each month from January to the month before the given month in the given year
36        for (int m = 1; m < month; ++m) {
37            totalDays += daysInMonth(year, m);
38        }
39        // Add days in the given month
40        totalDays += day;
41        // Return the total day count
42        return totalDays;
43    }
44}
45
1class Solution {
2public:
3    // Calculate the number of days between two dates
4    int daysBetweenDates(string date1, string date2) {
5        // Calculate the absolute difference between the days counts of both dates
6        return abs(calculateDays(date1) - calculateDays(date2));
7    }
8
9private:
10    // Helper function to determine if a given year is a leap year
11    bool isLeapYear(int year) {
12        // A leap year is divisible by 4, but not by 100 unless it is also divisible by 400
13        return (year % 4 == 0) && ((year % 100 != 0) || (year % 400 == 0));
14    }
15
16    // Helper function to get the number of days in a given month of a particular year
17    int daysInMonth(int year, int month) {
18        // Days in each month for a non-leap year
19        int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
20        // Adjust for leap year by adding one day to February
21        days[1] += isLeapYear(year);
22        return days[month - 1];
23    }
24
25    // Helper function to calculate the total number of days from a fixed date to the given date
26    int calculateDays(string date) {
27        // Parse the year, month, and day from the input string
28        int year = stoi(date.substr(0, 4));
29        int month = stoi(date.substr(5, 2));
30        int day = stoi(date.substr(8, 2));
31
32        // Count the days from the base date (1971-01-01) to the given date
33        int totalDays = 0;
34        for (int currentYear = 1971; currentYear < year; ++currentYear) {
35            // Add 365 days for each year plus one more if it's a leap year
36            totalDays += 365 + isLeapYear(currentYear);
37        }
38        for (int currentMonth = 1; currentMonth < month; ++currentMonth) {
39            // Add the days of each month in the given year
40            totalDays += daysInMonth(year, currentMonth);
41        }
42        // Add the days of the given month
43        totalDays += day;
44
45        return totalDays;
46    }
47};
48
1// Determines the number of days between two dates
2function daysBetweenDates(date1: string, date2: string): number {
3    // Calculate the absolute difference in days using the helper function 'calcDays'
4    return Math.abs(calcDays(date1) - calcDays(date2));
5}
6
7// Checks if a given year is a leap year
8function isLeapYear(year: number): boolean {
9    // Leap year if divisible by 4 and not by 100 unless also divisible by 400
10    return year % 4 === 0 && (year % 100 !== 0 || year % 400 === 0);
11}
12
13// Returns the number of days in a given month of a given year
14function daysOfMonth(year: number, month: number): number {
15    // An array representing the number of days in each month
16    const daysPerMonth = [
17        31,                             // January
18        isLeapYear(year) ? 29 : 28,     // February - conditional on leap year
19        31,                             // March
20        30,                             // April
21        31,                             // May
22        30,                             // June
23        31,                             // July
24        31,                             // August
25        30,                             // September
26        31,                             // October
27        30,                             // November
28        31                              // December
29    ];
30    // Return the number of days in the specified month
31    return daysPerMonth[month - 1];
32}
33
34// Calculates the total number of days from a fixed date (1971-01-01) to the given 'date'
35function calcDays(date: string): number {
36    let totalDays = 0;
37    // Parse the date string into year, month, and day components
38    const [year, month, day] = date.split('-').map(Number);
39
40    // Sum up all the days for the full years since the fixed date
41    for (let currentYear = 1971; currentYear < year; ++currentYear) {
42        totalDays += isLeapYear(currentYear) ? 366 : 365;
43    }
44    // Add the days for the months passed in the final year
45    for (let currentMonth = 1; currentMonth < month; ++currentMonth) {
46        totalDays += daysOfMonth(year, currentMonth);
47    }
48    // Finally, add the days passed in the final month, subtracting 1 to account for the start day
49    totalDays += day - 1;
50
51    // Return the total number of days
52    return totalDays;
53}
54
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the maximum element can be found in:

Time and Space Complexity

The given Python code calculates the number of days between two dates. We'll analyze the time complexity and space complexity separately.

Time Complexity:

  1. The isLeapYear function is O(1), as it consists of only arithmetic operations.
  2. The daysInMonth function is O(1) since it simply returns a value from a predefined list after calculating the leap year condition.
  3. The calcDays function is the main function that determines time complexity:
    • It involves two for-loops:
      • The first loop runs from 1971 to the given year (excluding). If the given year Y, this first loop runs in O(Y−1971).
      • The second loop runs from 1 to the given month (excluding). Since the number of months is constant, this second loop runs in O(1).
    • The rest of the operations in calcDays are constant time calculations.
    • Assuming Y1 and Y2 are the respective years in date1 and date2, the total time complexity for invoking calcDays for both dates is O(Y1-1971 + Y2-1971).
  4. The daysBetweenDates function calls calcDays twice and calculates the absolute difference between the returned values, which is an O(1) operation.
  5. Combining all the above, the overall time complexity is O(Y1-1971 + Y2-1971).

Space Complexity:

  1. The space used by the algorithm is constant since only a fixed amount of extra space is needed for the variables and arrays regardless of the input:
    • The days array in daysInMonth, which has constant size of 12.
    • The integer variables used throughout the functions for calculations.
  2. There is no variable space allocation that depends on the size of the input, so the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫