algoadvance

Leetcode 1360. Number of Days Between Two Dates

Problem Statement

Given two dates date1 and date2, each in the format YYYY-MM-DD, return the number of days between the two dates. The dates are guaranteed to be valid dates and there will not be any time zone difference in the date values.

Clarifying Questions

  1. Input Format: Each date will be in the form YYYY-MM-DD.
  2. Output Format: Return an integer representing the absolute difference in days.
  3. Edge Cases: Ensure to handle leap years correctly. The difference should be always non-negative.

Strategy

  1. Date Conversion: Convert both date strings into a date object or broken-down components (year, month, day).
  2. Days Calculation:
    • Calculate the total number of days from year 0 to each date.
    • Find the absolute difference between these two calculations.
  3. Helper Functions:
    • A function to check if a year is a leap year.
    • A function to convert a date to the number of days from year 0.

Code Implementation

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

// Check if a given year is leap year
bool isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

// Get the number of days in a month
int daysInMonth(int year, int month) {
    static const int daysInMonths[12] = {
        31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
    };
    if (month == 2 && isLeapYear(year)) {
        return 29;
    }
    return daysInMonths[month - 1];
}

// Convert the date string to number of days from year 0
int dateToDays(const string& date) {
    int year = stoi(date.substr(0, 4));
    int month = stoi(date.substr(5, 2));
    int day = stoi(date.substr(8, 2));

    int days = day;
    // Adding days for the months in the current year
    for (int m = 1; m < month; ++m) {
        days += daysInMonth(year, m);
    }
    // Adding days for the years before the current year
    for (int y = 0; y < year; ++y) {
        days += isLeapYear(y) ? 366 : 365;
    }

    return days;
}

// Main function to calculate the number of days between two dates
int daysBetweenDates(const string& date1, const string& date2) {
    int days1 = dateToDays(date1);
    int days2 = dateToDays(date2);
    return abs(days1 - days2);
}

int main() {
    string date1 = "2020-01-15";
    string date2 = "2019-12-31";
    cout << "Number of days between " << date1 << " and " << date2 << ": " << daysBetweenDates(date1, date2) << endl;

    return 0;
}

Time Complexity

The time complexity of this solution is O(1) since it involves a fixed number of operations regardless of the specific input dates. Specifically:

The operations involve:

Thus, the algorithm is very efficient for this problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI