LeetCode 1118 - Number of Days in a Month

The problem asks us to determine the number of days in a specific month of a given year. The inputs are two integers: year, which ranges from 1583 to 2100, and month, which ranges from 1 (January) to 12 (December).

leetcodeeasymath

LeetCode Problem 1118

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to determine the number of days in a specific month of a given year. The inputs are two integers: year, which ranges from 1583 to 2100, and month, which ranges from 1 (January) to 12 (December). The output is a single integer representing the total number of days in that month for that year.

The main complexity arises from February, which can have 28 or 29 days depending on whether the year is a leap year. A leap year occurs when the year is divisible by 4, except for years divisible by 100, unless they are also divisible by 400. This means 2000 is a leap year, 1900 is not, and 1992 is a leap year.

Important edge cases include February of leap years, February of non-leap years, and months with 30 or 31 days. The problem guarantees valid input, so we do not need to handle invalid months or years outside the given range.

Approaches

A brute-force approach would be to store the number of days for each month in a fixed array and adjust February dynamically depending on whether the year is a leap year. This approach is correct and very efficient, but the brute-force term might imply iterating over all days, which is unnecessary. The key insight is that the number of days in each month is deterministic and can be derived with simple conditional logic for February.

The optimal solution leverages a static array for the standard month lengths and applies the leap year calculation only for February. This approach is extremely efficient with constant time and space.

Approach Time Complexity Space Complexity Notes
Brute Force O(1) O(1) Use a lookup table for month lengths, check leap year for February
Optimal O(1) O(1) Same as brute force but with clear conditional logic for February

Algorithm Walkthrough

  1. Define an array of 12 integers representing the number of days in each month for a non-leap year. January has 31, February has 28, March has 31, and so on.
  2. Check if the given month is February.
  3. If it is February, determine if the year is a leap year using the rules: divisible by 4, not divisible by 100 unless divisible by 400.
  4. If it is a leap year, return 29. Otherwise, return 28.
  5. For all other months, return the corresponding value from the month days array.

Why it works: Every month has a fixed number of days except February, which depends on leap year rules. By storing the standard month lengths and adjusting February based on the well-defined leap year rules, this algorithm correctly computes the number of days for any valid input.

Python Solution

class Solution:
    def numberOfDays(self, year: int, month: int) -> int:
        month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        
        if month == 2:
            if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
                return 29
            else:
                return 28
        
        return month_days[month - 1]

This implementation first defines the days for each month in a non-leap year. It then checks for February and applies the leap year calculation. For all other months, it simply indexes into the pre-defined array. The indexing uses month - 1 because Python arrays are 0-indexed.

Go Solution

func numberOfDays(year int, month int) int {
    monthDays := [12]int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
    
    if month == 2 {
        if (year%4 == 0 && year%100 != 0) || (year%400 == 0) {
            return 29
        } else {
            return 28
        }
    }
    
    return monthDays[month-1]
}

In Go, we use a fixed-size array to store month days. Leap year checking is identical to the Python implementation. Array indexing is zero-based, so we access monthDays[month-1]. Go does not require type hints like Python, but the logic is otherwise the same.

Worked Examples

Example 1: year = 1992, month = 7

July has 31 days. It is not February, so we return monthDays[6] = 31.

Example 2: year = 2000, month = 2

February in a leap year. 2000 % 4 == 0, 2000 % 100 == 0, 2000 % 400 == 0. Leap year, return 29.

Example 3: year = 1900, month = 2

February in a non-leap year. 1900 % 4 == 0, 1900 % 100 == 0, 1900 % 400 != 0. Not a leap year, return 28.

Complexity Analysis

Measure Complexity Explanation
Time O(1) The algorithm performs a fixed number of operations regardless of input size
Space O(1) Only a fixed-size array of 12 integers is used

The complexity is minimal because the solution relies on constant-time checks and array lookup.

Test Cases

# Provided examples
assert Solution().numberOfDays(1992, 7) == 31  # July 1992
assert Solution().numberOfDays(2000, 2) == 29  # February 2000, leap year
assert Solution().numberOfDays(1900, 2) == 28  # February 1900, not a leap year

# Edge months
assert Solution().numberOfDays(2021, 1) == 31  # January
assert Solution().numberOfDays(2021, 4) == 30  # April
assert Solution().numberOfDays(2021, 12) == 31  # December

# Boundary years
assert Solution().numberOfDays(1583, 2) == 28  # earliest year in range, not a leap year
assert Solution().numberOfDays(2004, 2) == 29  # recent leap year
assert Solution().numberOfDays(2100, 2) == 28  # latest year, not a leap year
Test Why
July 1992 Regular month, standard days
February 2000 Leap year, 29 days
February 1900 Century year, not leap year, 28 days
January, April, December Check 31- and 30-day months
Years 1583, 2004, 2100 Test lower and upper bounds, leap year edge cases

Edge Cases

February in a leap year: This is a classic source of errors. If the leap year calculation is incorrect, February could incorrectly return 28 days. The implementation correctly applies the divisible by 4, not divisible by 100 unless divisible by 400 rule.

February in a century year that is not a leap year: Years like 1900 are divisible by 100 but not 400, so they are not leap years. A naive modulo 4 check would fail here. Our code explicitly accounts for this exception.

Month boundaries: Months with 30 and 31 days need correct indexing into the array. Using month - 1 for zero-based indexing ensures no off-by-one errors occur. This covers all months except February, which is handled separately.