Jobs

Interviews

Discussions

Number of Days Between Two Dates

Easy

Google

2 views

Topics:

Strings

Write a program to count the number of days between two dates.

The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.

Example 1:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

Example 2:

Input: date1 = "2020-01-15", date2 = "2019-12-31"
Output: 15

Constraints:

The given dates are valid dates between the years 1971 and 2100.

Number of Days Between Two Dates

Easy

Google

2 views

Topics:

Strings

Write a program to count the number of days between two dates.

The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.

Example 1:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

Example 2:

Input: date1 = "2020-01-15", date2 = "2019-12-31"
Output: 15

Constraints:

The given dates are valid dates between the years 1971 and 2100.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected date format for the input dates (e.g., YYYY-MM-DD, MM/DD/YYYY)?
What is the valid date range I should consider; are there minimum or maximum year values?
Are the input dates guaranteed to be valid dates, or should I handle cases where the date is invalid (e.g., February 30th)?
Should the result be the absolute difference, or should I return a positive or negative value depending on which date is earlier?
Is the start date always earlier than the end date, or should I handle cases where they are reversed?

Brute Force Solution

Approach

To find the number of days between two dates using a brute force method, we can simply count each day individually. We start at the earlier date and increment one day at a time until we reach the later date. The total count of these increments gives us the number of days between the two dates.

Here's how the algorithm would work step-by-step:

First, identify which of the two given dates is earlier and which is later.
Start counting from the earlier date.
Add one day to the earlier date.
Check if the incremented date is now equal to the later date.
If the incremented date is not the later date, increase the day count and repeat the process of adding one day to the earlier date.
Continue adding one day at a time and checking if the dates are equal until they are.
The final day count will be the number of days between the two dates.

Code Implementation

import datetime

def number_of_days_between_two_dates_brute_force(date_one, date_two):
    # Determine which date is earlier to start counting from
    if date_one > date_two:
        earlier_date = date_two
        later_date = date_one
    else:
        earlier_date = date_one
        later_date = date_two

    day_count = 0
    current_date = earlier_date

    # Increment the date until it equals the later date
    while current_date != later_date:
        current_date += datetime.timedelta(days=1)

        # Count the number of days we incremented
        day_count += 1

    return day_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates from the earlier date to the later date, incrementing one day at a time. The input size, 'n', represents the number of days between the two dates. The while loop executes once for each day between the two dates, incrementing the earlier date and the day counter until it reaches the later date. Therefore, the number of operations is directly proportional to 'n', resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The described algorithm involves incrementing the earlier date until it equals the later date, primarily using basic arithmetic operations. No auxiliary data structures like arrays, lists, or hash maps are created to store intermediate results. The algorithm only requires a few variables to store the dates and the day count, whose memory usage is constant regardless of the input date values. Thus, the space complexity is O(1).

Optimal Solution

Approach

The best way to find the number of days between two dates is to convert each date into a single number representing the days since a fixed starting point. Once both dates are numbers, simply subtract them to find the difference.

Here's how the algorithm would work step-by-step:

Pick a fixed date as a starting reference point. For example, you could imagine day 0 being January 1, year 0.
For the first given date, calculate the total number of days from your reference point up to that date. Account for the years, months, and days.
Remember to include leap years in your calculation to account for the extra day in February every four years.
Do the same thing for the second date: find the total number of days from the reference point up to that date.
Subtract the two total day counts from each other. The absolute value of the result is the number of days between the two dates.

Code Implementation

def days_between_dates(year1, month1, day1, year2, month2, day2):
    def is_leap_year(year):
        return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)

    def days_in_month(year, month):
        if month == 2:
            return 29 if is_leap_year(year) else 28
        elif month in [4, 6, 9, 11]:
            return 30
        else:
            return 31

    def days_from_origin(year, month, day):
        # We use year 0 as our fixed reference point.
        total_days = 0

        for current_year in range(0, year):
            total_days += 366 if is_leap_year(current_year) else 365

        # Add the days from the beginning of the year.
        for current_month in range(1, month):
            total_days += days_in_month(year, current_month)

        total_days += day
        return total_days

    # Calculate the total number of days from year 0 for each date.
    days1 = days_from_origin(year1, month1, day1)
    days2 = days_from_origin(year2, month2, day2)

    # Return the absolute difference between the two dates.
    return abs(days1 - days2)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The algorithm calculates the number of days between two dates by converting each date to a day count since a fixed reference point. This conversion involves a fixed number of arithmetic operations based on years, months, and days, independent of the magnitude of the date values. The subtraction of the two day counts is also a constant time operation. Therefore, the overall time complexity remains constant regardless of the input date values.

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it primarily uses a fixed number of integer variables to store the calculated total number of days for each date. The number of years, months, and days in the input dates does not affect the amount of extra memory required. Therefore, the space used remains constant regardless of the input size, making it constant space.

Edge Cases

Case	How to Handle
Null or empty date strings	Throw an IllegalArgumentException or return a predefined error code to indicate invalid input.
Identical dates	Return 0 as the number of days between the same date is zero.
Invalid date format (e.g., incorrect separator, out-of-range values)	Use try-catch blocks or a dedicated validation function to check the date format and values, throwing an exception or returning an error if invalid.
Date strings representing dates far in the past or future (potential integer overflow)	Use a 64-bit integer type or long type to store the number of days since an epoch to prevent potential overflow when calculating the difference.
Leap year handling (February 29)	Account for leap years correctly in the day calculation by implementing or using a built-in leap year check.
Dates spanning different centuries or millennia	The date calculation should handle different centuries correctly as the math needs to account for century leap year exceptions.
Date1 is later than Date2	Calculate the absolute difference to ensure a non-negative result, or explicitly handle the reverse order.
Dates on the edge of integer limits (e.g., dates that, when converted to days since epoch, are close to MAX_INT or MIN_INT)	Ensure that internal calculations using integer representations of dates do not overflow by using appropriate data types (e.g., long) and considering intermediate value ranges.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected date format for the input dates (e.g., YYYY-MM-DD, MM/DD/YYYY)?
What is the valid date range I should consider; are there minimum or maximum year values?
Are the input dates guaranteed to be valid dates, or should I handle cases where the date is invalid (e.g., February 30th)?
Should the result be the absolute difference, or should I return a positive or negative value depending on which date is earlier?
Is the start date always earlier than the end date, or should I handle cases where they are reversed?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, identify which of the two given dates is earlier and which is later.
Start counting from the earlier date.
Add one day to the earlier date.
Check if the incremented date is now equal to the later date.
If the incremented date is not the later date, increase the day count and repeat the process of adding one day to the earlier date.
Continue adding one day at a time and checking if the dates are equal until they are.
The final day count will be the number of days between the two dates.

Code Implementation

import datetime

def number_of_days_between_two_dates_brute_force(date_one, date_two):
    # Determine which date is earlier to start counting from
    if date_one > date_two:
        earlier_date = date_two
        later_date = date_one
    else:
        earlier_date = date_one
        later_date = date_two

    day_count = 0
    current_date = earlier_date

    # Increment the date until it equals the later date
    while current_date != later_date:
        current_date += datetime.timedelta(days=1)

        # Count the number of days we incremented
        day_count += 1

    return day_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Pick a fixed date as a starting reference point. For example, you could imagine day 0 being January 1, year 0.
For the first given date, calculate the total number of days from your reference point up to that date. Account for the years, months, and days.
Remember to include leap years in your calculation to account for the extra day in February every four years.
Do the same thing for the second date: find the total number of days from the reference point up to that date.
Subtract the two total day counts from each other. The absolute value of the result is the number of days between the two dates.

Code Implementation

def days_between_dates(year1, month1, day1, year2, month2, day2):
    def is_leap_year(year):
        return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)

    def days_in_month(year, month):
        if month == 2:
            return 29 if is_leap_year(year) else 28
        elif month in [4, 6, 9, 11]:
            return 30
        else:
            return 31

    def days_from_origin(year, month, day):
        # We use year 0 as our fixed reference point.
        total_days = 0

        for current_year in range(0, year):
            total_days += 366 if is_leap_year(current_year) else 365

        # Add the days from the beginning of the year.
        for current_month in range(1, month):
            total_days += days_in_month(year, current_month)

        total_days += day
        return total_days

    # Calculate the total number of days from year 0 for each date.
    days1 = days_from_origin(year1, month1, day1)
    days2 = days_from_origin(year2, month2, day2)

    # Return the absolute difference between the two dates.
    return abs(days1 - days2)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty date strings	Throw an IllegalArgumentException or return a predefined error code to indicate invalid input.
Identical dates	Return 0 as the number of days between the same date is zero.
Invalid date format (e.g., incorrect separator, out-of-range values)	Use try-catch blocks or a dedicated validation function to check the date format and values, throwing an exception or returning an error if invalid.
Date strings representing dates far in the past or future (potential integer overflow)	Use a 64-bit integer type or long type to store the number of days since an epoch to prevent potential overflow when calculating the difference.
Leap year handling (February 29)	Account for leap years correctly in the day calculation by implementing or using a built-in leap year check.
Dates spanning different centuries or millennia	The date calculation should handle different centuries correctly as the math needs to account for century leap year exceptions.
Date1 is later than Date2	Calculate the absolute difference to ensure a non-negative result, or explicitly handle the reverse order.
Dates on the edge of integer limits (e.g., dates that, when converted to days since epoch, are close to MAX_INT or MIN_INT)	Ensure that internal calculations using integer representations of dates do not overflow by using appropriate data types (e.g., long) and considering intermediate value ranges.