Problem Description

Given two dates as strings in the format YYYY-MM-DD, calculate the number of days between them.

The task is to find the absolute difference in days between any two given dates. For example, if you have dates like "2019-06-29" and "2019-06-30", the answer would be 1 day. The dates can be given in any order - the result should always be the positive difference between them.

The solution works by converting each date into the total number of days elapsed since a reference point (January 1, 1971 in this implementation). Once both dates are converted to their respective day counts from this reference point, the absolute difference between these counts gives us the number of days between the two dates.

The implementation handles leap years correctly - a year is a leap year if it's divisible by 4, except for years divisible by 100 (which are not leap years), unless they're also divisible by 400 (which makes them leap years again). This affects February, which has 29 days in leap years and 28 days otherwise.

The approach breaks down the problem into three helper functions:

• isLeapYear(year): Determines if a given year is a leap year
• daysInMonth(year, month): Returns the number of days in a specific month of a specific year
• calcDays(date): Calculates the total days from the reference date (1971-01-01) to the given date

By calculating the days from the reference point for both input dates and taking the absolute difference, we get the number of days between the two dates.

Intuition

When we need to find the difference between two dates, the direct approach of counting days month by month between them can become complicated, especially when the dates span multiple years or when we need to handle different month lengths and leap years.

A cleaner approach is to convert both dates to a common reference system. Think of it like measuring the distance between two cities - instead of calculating the direct path through various terrains, we can measure each city's distance from a common reference point (like the capital) and then find the difference.

For dates, we can pick any reference date (here we use January 1, 1971) and calculate how many days have passed from that reference point to each of our given dates. Once we have these two values, the difference between them gives us the number of days between the original dates.

Why does this work? If date1 is X days from our reference and date2 is Y days from our reference, then the distance between date1 and date2 is simply |X - Y| days. The absolute value ensures we always get a positive result regardless of which date comes first.

The key insight is that by converting dates to a linear scale (total days from a fixed point), we transform a complex date arithmetic problem into a simple subtraction problem. This avoids the need to handle edge cases like crossing month boundaries, year boundaries, or dealing with varying month lengths in our main logic - all these complexities are encapsulated in the conversion function that counts days from the reference point.

The choice of 1971 as the reference year is arbitrary - any year before our input dates would work. The algorithm systematically counts all days from the reference year to the target date by adding up complete years (accounting for leap years) and then adding the remaining months and days.

Learn more about Math patterns.

Solution Approach

The implementation consists of three helper functions that work together to calculate the days between two dates:

1. Checking for Leap Years

The isLeapYear(year) function determines if a year is a leap year using the standard rules:

• A year is a leap year if it's divisible by 4 (year % 4 == 0)
• However, if it's divisible by 100, it's not a leap year (year % 100 != 0)
• Unless it's also divisible by 400, then it is a leap year (year % 400 == 0)

This can be expressed as: year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)

2. Calculating Days in Each Month

The daysInMonth(year, month) function returns the number of days in a given month:

• It uses an array days where each index represents a month (index 0 for January, 1 for February, etc.)
• The standard days are: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
• For February (index 1), we add 1 if it's a leap year: 28 + int(isLeapYear(year))
• The function returns days[month - 1] since months are 1-indexed in the input

3. Converting Date to Days from Reference

The calcDays(date) function converts a date string to the total number of days since January 1, 1971:

• First, it parses the date string: year, month, day = map(int, date.split("-"))

• It accumulates days in three steps:

  a. Years: Loop from 1971 to the target year (exclusive) and add days for each complete year:

  for y in range(1971, year):
      days += 365 + int(isLeapYear(y))

  Each regular year contributes 365 days, leap years contribute 366.

  b. Months: Loop from January to the target month (exclusive) and add days for each complete month:

  for m in range(1, month):
      days += daysInMonth(year, m)

  c. Days: Simply add the day of the month: days += day

4. Final Calculation

The main function calculates the absolute difference:

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

This ensures the result is always positive, regardless of which date comes first chronologically.

The time complexity is O(Y + M) where Y is the difference in years from 1971 and M is the month number (up to 12). The space complexity is O(1) as we only use a fixed-size array and a few variables.

Example Walkthrough

Let's walk through calculating the days between "2019-06-29" and "2019-06-30".

Step 1: Calculate days from 1971-01-01 to 2019-06-29

For date1 = "2019-06-29":

• Parse: year=2019, month=6, day=29

Count complete years (1971 to 2018):

• Regular years: Most years contribute 365 days
• Leap years (1972, 1976, 1980, ..., 2016): Each contributes 366 days
• Years 1971-2018 = 48 years total
• Leap years in this range: 1972, 1976, 1980, 1984, 1988, 1992, 1996, 2000, 2004, 2008, 2012, 2016 (12 leap years)
• Total days from years: (48 - 12) × 365 + 12 × 366 = 36 × 365 + 12 × 366 = 13,140 + 4,392 = 17,532 days

Count complete months in 2019 (January to May):

• January: 31 days
• February: 28 days (2019 is not a leap year: 2019 % 4 = 3)
• March: 31 days
• April: 30 days
• May: 31 days
• Total: 31 + 28 + 31 + 30 + 31 = 151 days

Add the days in June: 29 days

Total for 2019-06-29: 17,532 + 151 + 29 = 17,712 days from 1971-01-01

Step 2: Calculate days from 1971-01-01 to 2019-06-30

For date2 = "2019-06-30":

• Parse: year=2019, month=6, day=30
• Same calculation for years: 17,532 days
• Same calculation for months (Jan-May): 151 days
• Days in June: 30 days

Total for 2019-06-30: 17,532 + 151 + 30 = 17,713 days from 1971-01-01

Step 3: Calculate the difference

Days between dates = |17,712 - 17,713| = |-1| = 1 day

The answer is 1 day, which matches our expectation since these are consecutive dates.

Solution Implementation

Time and Space Complexity

The time complexity is O(y + m), where y represents the number of years between the given date and the base year 1971, and m represents the month value of the given date (ranging from 1 to 12).

Breaking down the time complexity:

• The calcDays function is called twice (once for each date)
• For each call:
  • The first loop iterates from 1971 to the given year, which takes O(y) time where y = year - 1971
  • The second loop iterates from month 1 to the given month minus 1, which takes O(m) time where m is at most 12
  • The isLeapYear function is called O(y) times in the first loop and once in daysInMonth, each taking O(1) time
  • The daysInMonth function is called O(m) times, each taking O(1) time

Since the function is called for both dates, if we consider the maximum year difference as y, the overall time complexity is O(y + m).

The space complexity is O(1) as the algorithm uses only a fixed amount of extra space:

• The days array in daysInMonth has a fixed size of 12 elements
• All other variables (year, month, day, days counter) use constant space
• No recursive calls or data structures that grow with input size

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

Common Pitfalls

1. Incorrect Leap Year Calculation Logic

Pitfall: A common mistake is implementing the leap year logic incorrectly, particularly forgetting the century rule exceptions. Many developers write simplified conditions like:

# WRONG: Only checking divisibility by 4
return year % 4 == 0

# WRONG: Missing the 400 exception
return year % 4 == 0 and year % 100 != 0

Why it fails: Years like 1900 and 2100 are divisible by 4 but are NOT leap years (divisible by 100 but not by 400). Year 2000 IS a leap year (divisible by 400).

Solution: Use the complete leap year rule:

def is_leap_year(year: int) -> bool:
    return year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)

2. Off-by-One Errors in Month Indexing

Pitfall: Mixing up 0-based and 1-based indexing when accessing the days array:

# WRONG: Forgetting to subtract 1 from month
return days_per_month[month]  # month is 1-12, but array is 0-indexed

# WRONG: Using 0-based months in the loop
for m in range(0, month):  # This would include month 0 which doesn't exist

Solution: Be consistent with month representation - keep months as 1-12 in the logic and convert to 0-based only when accessing arrays:

def days_in_month(year: int, month: int) -> int:
    days_per_month = [31, 28 + int(is_leap_year(year)), 31, ...]
    return days_per_month[month - 1]  # Convert 1-based to 0-based

3. Integer Overflow with Different Reference Years

Pitfall: If you choose a very early reference year (like year 0 or 1), the accumulated days might cause integer overflow for modern dates:

# RISKY: Using year 1 as reference
for y in range(1, year):  # This accumulates ~730,000+ days for year 2024
    total_days += 365 + int(is_leap_year(y))

Solution: Use a more recent reference year (like 1971) or ensure your language handles large integers properly. Python handles arbitrary precision integers, but in languages like Java or C++, consider using long integers.

4. Forgetting the Absolute Value

Pitfall: Returning a negative number when date1 comes after date2:

# WRONG: May return negative values
return calculate_days(date1) - calculate_days(date2)

Solution: Always use absolute value to ensure positive results:

return abs(calculate_days_since_epoch(date1) - calculate_days_since_epoch(date2))

5. Inefficient Year Iteration for Large Date Ranges

Pitfall: When dates are far from the reference year, iterating through each year becomes inefficient:

# Inefficient for year 3000+
for y in range(1971, year):  # Could iterate 1000+ times
    total_days += 365 + int(is_leap_year(y))

Solution: For better performance with large date ranges, calculate leap years mathematically:

def count_leap_years(start_year: int, end_year: int) -> int:
    """Count leap years in range [start_year, end_year)"""
    def count_up_to(year):
        if year <= 0:
            return 0
        year -= 1  # We want years < year
        return year // 4 - year // 100 + year // 400
  
    return count_up_to(end_year) - count_up_to(start_year)

# Then calculate total days more efficiently
regular_years = (year - 1971) - leap_years_count
total_days = regular_years * 365 + leap_years_count * 366

6. Not Handling Edge Cases in Input Validation

Pitfall: Assuming input is always valid without checking:

# Risky: No validation
year, month, day = map(int, date.split("-"))

Solution: Add basic validation for production code:

def validate_date(date: str) -> tuple:
    parts = date.split("-")
    if len(parts) != 3:
        raise ValueError(f"Invalid date format: {date}")
  
    year, month, day = map(int, parts)
  
    if month < 1 or month > 12:
        raise ValueError(f"Invalid month: {month}")
  
    if day < 1 or day > days_in_month(year, month):
        raise ValueError(f"Invalid day: {day} for {year}-{month}")
  
    return year, month, day