Problem Description

Given a string date representing a date in the format "YYYY-MM-DD", return the day number of the year for that date. The day number is the count of days from January 1st to the given date, inclusive. For example, January 1st is day 1, February 1st is day 32, and so on.

• The input date will always be a valid date in the Gregorian calendar.
• Leap years should be handled correctly: February has 29 days in a leap year and 28 days otherwise.
• The output should be an integer representing the day of the year.

Thought Process

To solve this problem, we need to find out how many days have passed since the start of the year up to the given date. The most straightforward approach is to:

• Extract the year, month, and day from the input string.
• Sum up the days in all the months before the given month.
• Add the day of the current month.
• Take care to handle leap years, since February has an extra day in those years.

A brute-force approach would involve iterating through each month and adding up the days, but we can optimize this by using a precomputed list of days in each month and a simple check for leap years.

Solution Approach

Let's break down the steps to implement the solution:

1. Parse the input: Split the date string into year, month, and day as integers.
2. Precompute month days: Use an array or list to store the number of days in each month for a non-leap year.
3. Handle leap years: Check if the year is a leap year using the following rule:
   • A year is a leap year if it is divisible by 4, and (not divisible by 100 or divisible by 400).
   If it is a leap year, add 1 to February (the second month).
4. Sum up days: Add all days from months before the given month, then add the day of the current month.
5. Return the result: The total is the day of the year for the given date.

This approach is efficient because it avoids unnecessary iterations and leverages precomputed data for fast calculation.

Example Walkthrough

Let's walk through the example date = "2019-02-10":

• Extracted: year = 2019, month = 2, day = 10.
• 2019 is not a leap year (2019 % 4 != 0).
• Days in each month (non-leap): [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
• Sum days before February: January has 31 days.
• Add current day: 31 (January) + 10 (February 10th) = 41.

So, "2019-02-10" is the 41st day of the year.

Time and Space Complexity

Brute-force approach: If you loop through each day from January 1st to the given date, the time complexity would be O(N) where N is the day number, and space complexity is O(1).

Optimized approach: Using a precomputed list of month days, parsing, and summing is all O(1) time and O(1) space. This is because the number of months is fixed (12), and all operations are simple arithmetic.

Summary

The key to this problem is recognizing that you can efficiently calculate the day of the year by summing the days in the months before the given date and handling leap years with a simple check. By precomputing the days in each month and adjusting February for leap years, the solution remains fast and easy to understand.

Code Implementation

class Solution:
    def dayOfYear(self, date: str) -> int:
        year, month, day = map(int, date.split('-'))
        # Days in each month for non-leap year
        month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        # Check for leap year
        if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
            month_days[1] = 29
        return sum(month_days[:month-1]) + day
      

class Solution {
public:
    int dayOfYear(string date) {
        int year = stoi(date.substr(0, 4));
        int month = stoi(date.substr(5, 2));
        int day = stoi(date.substr(8, 2));
        vector<int> month_days = {31,28,31,30,31,30,31,31,30,31,30,31};
        // Leap year check
        if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
            month_days[1] = 29;
        }
        int total = day;
        for (int i = 0; i < month - 1; ++i) {
            total += month_days[i];
        }
        return total;
    }
};
      

class Solution {
    public int dayOfYear(String date) {
        int year = Integer.parseInt(date.substring(0, 4));
        int month = Integer.parseInt(date.substring(5, 7));
        int day = Integer.parseInt(date.substring(8, 10));
        int[] monthDays = {31,28,31,30,31,30,31,31,30,31,30,31};
        if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
            monthDays[1] = 29;
        }
        int total = day;
        for (int i = 0; i < month - 1; ++i) {
            total += monthDays[i];
        }
        return total;
    }
}
      

var dayOfYear = function(date) {
    const [year, month, day] = date.split('-').map(Number);
    const monthDays = [31,28,31,30,31,30,31,31,30,31,30,31];
    // Leap year check
    if ((year % 4 === 0 && year % 100 !== 0) || (year % 400 === 0)) {
        monthDays[1] = 29;
    }
    let total = day;
    for (let i = 0; i < month - 1; ++i) {
        total += monthDays[i];
    }
    return total;
};