LeetCode 1154 - Day of the Year

The problem asks us to compute the ordinal day number of a year given a date in the format YYYY-MM-DD. For example, January 1st is always day 1, January 2nd is day 2, and December 31st is either day 365 or 366 depending on whether the year is a leap year.

leetcodeeasymathstring

LeetCode Problem 1154

Difficulty: 🟢 Easy
Topics: Math, String

Solution

Problem Understanding

The problem asks us to compute the ordinal day number of a year given a date in the format YYYY-MM-DD. For example, January 1st is always day 1, January 2nd is day 2, and December 31st is either day 365 or 366 depending on whether the year is a leap year. The input is a string that strictly follows the YYYY-MM-DD format, and it represents a valid Gregorian calendar date between January 1st, 1900 and December 31st, 2019. The output is a single integer representing the day of the year for that date.

The constraints guarantee that the input is valid, so we do not need to handle invalid dates or malformed strings. Important edge cases include dates on the boundary of months, particularly February 28th and 29th in leap years, and December 31st, which is the last day of the year.

Approaches

The brute-force approach would be to iterate from January 1st to the given date, counting each day. While this would give the correct result, it is unnecessary because the number of days in each month is fixed (except February in leap years). This approach has linear time complexity relative to the day of the year, which is inefficient compared to a direct calculation.

The optimal approach leverages two insights: first, we can precompute the cumulative number of days at the start of each month; second, we need to account for leap years, which add an extra day to February. With these two pieces of information, we can directly compute the day number by adding the day of the month to the cumulative days of preceding months and adjusting for leap years if necessary.

Approach Time Complexity Space Complexity Notes
Brute Force O(N) O(1) Count days from January 1 to the given date
Optimal O(1) O(1) Use precomputed month offsets and leap year adjustment

Algorithm Walkthrough

  1. Parse the input date string to extract the year, month, and day as integers. This allows us to perform arithmetic and comparisons on the components.
  2. Create a list of cumulative days at the start of each month for a non-leap year: [0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334]. This represents the total number of days before the first day of each month.
  3. Calculate whether the year is a leap year. A year is a leap year if it is divisible by 4, except if it is divisible by 100, unless it is also divisible by 400.
  4. Compute the day number by adding the day of the month to the cumulative number of days before the current month.
  5. If the date is after February in a leap year, increment the day number by 1 to account for February 29th.
  6. Return the final day number.

Why it works: By using cumulative days and adjusting for leap years, we guarantee the correct count of days from the start of the year. The algorithm uses only arithmetic operations and a small lookup table, so it is both correct and efficient.

Python Solution

class Solution:
    def dayOfYear(self, date: str) -> int:
        year, month, day = map(int, date.split('-'))
        days_before_month = [0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334]
        
        day_of_year = days_before_month[month - 1] + day
        
        # Check for leap year
        if month > 2 and ((year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)):
            day_of_year += 1
        
        return day_of_year

The Python implementation follows the algorithm exactly. We first split the date string into integers for the year, month, and day. Using a precomputed list of cumulative days before each month, we compute a preliminary day number. We then check if the year is a leap year and if the month is after February, adding one day if necessary. Finally, we return the computed day number.

Go Solution

func dayOfYear(date string) int {
    var year, month, day int
    fmt.Sscanf(date, "%d-%d-%d", &year, &month, &day)
    
    daysBeforeMonth := [12]int{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}
    dayOfYear := daysBeforeMonth[month-1] + day
    
    isLeap := (year%4 == 0 && year%100 != 0) || (year%400 == 0)
    if month > 2 && isLeap {
        dayOfYear++
    }
    
    return dayOfYear
}

In Go, we use fmt.Sscanf to parse the date string into integers. We use a fixed-size array for cumulative days, similar to Python. Leap year handling is identical, and the result is returned as an integer. Go requires explicit array types and avoids dynamic lists for small fixed data, which is why we use an array instead of a slice.

Worked Examples

Example 1: date = "2019-01-09"

Step year month day dayOfYear Comment
Parse 2019 1 9 - Extract components
Precompute - - - 0 + 9 = 9 January has no prior days
Leap check 2019 is not leap - - 9 No adjustment needed
Return - - - 9 Correct

Example 2: date = "2019-02-10"

Step year month day dayOfYear Comment
Parse 2019 2 10 - Extract components
Precompute - - - 31 + 10 = 41 Cumulative days before February + day
Leap check 2019 is not leap - - 41 No adjustment needed
Return - - - 41 Correct

Complexity Analysis

Measure Complexity Explanation
Time O(1) Parsing the string and accessing array indices are constant-time operations
Space O(1) Only a fixed-size array of 12 elements is used, independent of input

This solution is highly efficient because it uses simple arithmetic and precomputed values. There are no loops or recursive calls, so it runs in constant time and space.

Test Cases

# Provided examples
assert Solution().dayOfYear("2019-01-09") == 9  # Early January
assert Solution().dayOfYear("2019-02-10") == 41 # February, non-leap year

# Leap year checks
assert Solution().dayOfYear("2020-03-01") == 61 # After Feb in leap year
assert Solution().dayOfYear("2020-02-29") == 60 # Leap day

# End of year checks
assert Solution().dayOfYear("2019-12-31") == 365 # Non-leap year
assert Solution().dayOfYear("2020-12-31") == 366 # Leap year

# Beginning of year
assert Solution().dayOfYear("1900-01-01") == 1  # Edge case: start of year
assert Solution().dayOfYear("2019-01-01") == 1  # Another start of year

# Month boundary checks
assert Solution().dayOfYear("2019-03-01") == 60  # Non-leap year March 1
assert Solution().dayOfYear("2020-03-01") == 61  # Leap year March 1
Test Why
"2019-01-09" Early January, small day number
"2019-02-10" February in non-leap year
"2020-03-01" Leap year after February
"2020-02-29" Leap day itself
"2019-12-31" Last day of non-leap year
"2020-12-31" Last day of leap year
"1900-01-01" Earliest possible date
"2019-01-01" Start of year check
"2019-03-01" / "2020-03-01" Month boundary, check leap day inclusion

Edge Cases

One important edge case is February 29th in a leap year. If the leap year logic is incorrect, the day number for dates after February will be off by one. Our implementation checks if the year is leap and if the month is greater than 2 before adding an extra day, ensuring correctness.

Another edge case is January 1st. A naive cumulative sum approach could accidentally add days before January, producing a value of zero or negative. By using a precomputed list starting with zero and adding the day, we ensure January