LeetCode 1185 - Day of the Week

This problem asks us to determine which day of the week corresponds to a given calendar date. The input consists of three integers: - day, representing the day within the month - month, representing the month number from 1 to 12 - year, representing the year We must return the…

leetcodeeasymath

LeetCode Problem 1185

Difficulty: 🟢 Easy
Topics: Math

Solution

LeetCode 1185 - Day of the Week

Problem Understanding

This problem asks us to determine which day of the week corresponds to a given calendar date.

The input consists of three integers:

  • day, representing the day within the month
  • month, representing the month number from 1 to 12
  • year, representing the year

We must return the correct weekday name as a string. The possible outputs are:

  • "Sunday"
  • "Monday"
  • "Tuesday"
  • "Wednesday"
  • "Thursday"
  • "Friday"
  • "Saturday"

The problem provides an important reference point:

January 1, 1971 was a Friday.

This reference date allows us to compute the weekday for any later date by counting how many days have passed since that known starting point.

The constraints are relatively small:

  • Dates are guaranteed to be valid
  • Years range from 1971 to 2100

Since the date range is limited to about 130 years, performance is not a major concern. Even a solution that iterates through days one by one would still run quickly enough. However, we can still design a clean and efficient mathematical solution.

Several edge cases are important:

  • Leap years must be handled correctly
  • February changes from 28 to 29 days in leap years
  • Dates at the beginning or end of a year can expose off by one errors
  • Century years need correct leap year handling, though within this range only year 2000 matters
  • The reference date itself, January 1, 1971, should map directly to Friday

The problem guarantees all dates are valid, so we do not need to perform input validation.

Approaches

Brute Force Approach

A straightforward solution is to simulate the calendar day by day starting from January 1, 1971.

We know that January 1, 1971 was a Friday. We can repeatedly advance one day at a time until we reach the target date. Each time we move forward one day, we also move forward one weekday index.

To implement this approach, we would:

  1. Start at (1, 1, 1971)
  2. Keep incrementing the date
  3. Track the weekday index modulo 7
  4. Stop once we reach the target date

This works because weekdays repeat every 7 days, and advancing one calendar day always advances the weekday by exactly one.

Although correct, this approach is inefficient conceptually because it simulates every intermediate date individually. For large ranges, that becomes unnecessarily expensive.

Optimal Mathematical Counting Approach

Instead of simulating every date transition, we can count the total number of days between the reference date and the target date.

The key observation is:

  • Every normal year contributes 365 days
  • Leap years contribute 366 days
  • Each month contributes a known number of days

If we compute the total number of elapsed days since January 1, 1971, then:

  • 0 days elapsed means Friday
  • 1 day elapsed means Saturday
  • 2 days elapsed means Sunday
  • and so on

Since weekdays repeat every 7 days, we only need:

total_days % 7

This converts the absolute day count into the weekday index.

The algorithm becomes:

  1. Count all full years before the target year
  2. Count all full months before the target month
  3. Add the current day offset
  4. Use modulo arithmetic to determine the weekday

This solution is simple, efficient, and easy to reason about.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(number of days) O(1) Simulates every day from 1971 to target date
Optimal O(years + months) O(1) Counts total elapsed days mathematically

Algorithm Walkthrough

Step 1: Store weekday names

We create an array of weekday names in order:

["Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday"]

Index 0 corresponds to January 1, 1971.

Step 2: Define month lengths

We store the number of days in each month for a normal year:

[31,28,31,30,31,30,31,31,30,31,30,31]

February may later become 29 days in leap years.

Step 3: Create a leap year helper

A year is a leap year if:

  • It is divisible by 400, or
  • It is divisible by 4 but not divisible by 100

This follows the Gregorian calendar rules.

The helper function allows us to correctly count February days.

Step 4: Count days contributed by full years

We iterate from 1971 up to year - 1.

For each year:

  • Add 365
  • Add one more day if it is a leap year

At the end of this step, we know how many days passed before the target year began.

Step 5: Count days contributed by full months

We iterate through all months before the target month.

For each month:

  • Add the corresponding number of days
  • If the month is February in a leap year, add one extra day

Now we know how many days passed before the target month began.

Step 6: Add current month days

We add:

day - 1

We subtract one because the current day itself should not fully advance the weekday count.

For example:

  • January 1 should contribute zero additional elapsed days
  • January 2 should contribute one elapsed day

Step 7: Compute weekday

We compute:

weekday_index = total_days % 7

Then return:

weekdays[weekday_index]

Why it works

The algorithm works because every calendar day advances the weekday by exactly one position. By counting the exact number of elapsed days from a known reference date, we can determine the weekday using modulo 7 arithmetic.

The leap year calculation guarantees that February contributes the correct number of days. Since we count all full years, all full months, and the offset within the current month, the computed total accurately represents the number of days elapsed since January 1, 1971.

Python Solution

class Solution:
    def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        weekdays = [
            "Friday",
            "Saturday",
            "Sunday",
            "Monday",
            "Tuesday",
            "Wednesday",
            "Thursday"
        ]

        month_days = [31, 28, 31, 30, 31, 30,
                      31, 31, 30, 31, 30, 31]

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

        total_days = 0

        # Add days for complete years
        for current_year in range(1971, year):
            total_days += 365
            if is_leap(current_year):
                total_days += 1

        # Add days for complete months
        for current_month in range(1, month):
            total_days += month_days[current_month - 1]

            if current_month == 2 and is_leap(year):
                total_days += 1

        # Add days within current month
        total_days += day - 1

        return weekdays[total_days % 7]

The implementation begins by storing weekday names in the exact order relative to the reference date. Since January 1, 1971 was Friday, index 0 maps to "Friday".

The month_days array stores the standard number of days for each month in a non leap year. February adjustments are handled separately to keep the logic clean.

The is_leap helper encapsulates the Gregorian leap year rules. This avoids duplicating leap year logic throughout the solution.

The first loop accumulates days from all fully completed years before the target year. Each year contributes either 365 or 366 days.

The second loop accumulates days from all fully completed months before the target month. If the current year is a leap year and the month is February, one additional day is added.

Finally, day - 1 is added because the first day of the month contributes zero elapsed days.

The modulo operation converts the total elapsed day count into a weekday index.

Go Solution

func dayOfTheWeek(day int, month int, year int) string {
    weekdays := []string{
        "Friday",
        "Saturday",
        "Sunday",
        "Monday",
        "Tuesday",
        "Wednesday",
        "Thursday",
    }

    monthDays := []int{
        31, 28, 31, 30, 31, 30,
        31, 31, 30, 31, 30, 31,
    }

    isLeap := func(y int) bool {
        return (y%400 == 0) || (y%4 == 0 && y%100 != 0)
    }

    totalDays := 0

    // Add days for complete years
    for currentYear := 1971; currentYear < year; currentYear++ {
        totalDays += 365

        if isLeap(currentYear) {
            totalDays++
        }
    }

    // Add days for complete months
    for currentMonth := 1; currentMonth < month; currentMonth++ {
        totalDays += monthDays[currentMonth-1]

        if currentMonth == 2 && isLeap(year) {
            totalDays++
        }
    }

    // Add days within current month
    totalDays += day - 1

    return weekdays[totalDays%7]
}

The Go implementation follows the same logical structure as the Python solution.

Go uses slices instead of Python lists, but the indexing behavior is equivalent. The leap year helper is implemented as an anonymous function assigned to isLeap.

Since the constraints are very small, integer overflow is not a concern. Standard Go int values are more than sufficient for the number of days involved.

No special handling for nil values is required because the input is guaranteed valid.

Worked Examples

Example 1

Input:

day = 31, month = 8, year = 2019

Step 1: Count full years

We count days from 1971 through 2018.

Component Value
Normal years 48
Leap years 12
Total days 48 × 365 + 12 = 17532

Step 2: Count full months in 2019

Months before August:

Month Days
January 31
February 28
March 31
April 30
May 31
June 30
July 31
Total 212

Step 3: Add current month offset

day - 1 = 30

Step 4: Compute total

Calculation Value
Full years 17532
Full months 212
Current month offset 30
Total days 17774

Step 5: Compute weekday

17774 % 7 = 1

Index 1 in the weekday array is:

"Saturday"

Final answer:

"Saturday"

Example 2

Input:

day = 18, month = 7, year = 1999

Step 1: Count full years

Component Value
Total elapsed days before 1999 10226

Step 2: Count months before July

Month Days
January 31
February 28
March 31
April 30
May 31
June 30
Total 181

Step 3: Add current month offset

18 - 1 = 17

Step 4: Total days

10226 + 181 + 17 = 10424

Step 5: Weekday

10424 % 7 = 2

Index 2 corresponds to:

"Sunday"

Final answer:

"Sunday"

Example 3

Input:

day = 15, month = 8, year = 1993

Step 1: Count full years

Component Value
Total elapsed days before 1993 8035

Step 2: Count months before August

Month Days
January 31
February 28
March 31
April 30
May 31
June 30
July 31
Total 212

Step 3: Add current month offset

15 - 1 = 14

Step 4: Total days

8035 + 212 + 14 = 8261

Step 5: Weekday

8261 % 7 = 2

Index 2 corresponds to:

"Sunday"

Final answer:

"Sunday"

Complexity Analysis

Measure Complexity Explanation
Time O(years + months) Iterates through years and months before target date
Space O(1) Uses only fixed size arrays and counters

The algorithm performs a loop across years from 1971 to the target year and another loop across months within the target year. Since the maximum year difference is small, the runtime is extremely efficient in practice.

The space complexity remains constant because we only store a few arrays and integer variables regardless of input size.

Test Cases

solution = Solution()

# Provided examples
assert solution.dayOfTheWeek(31, 8, 2019) == "Saturday"  # Example 1
assert solution.dayOfTheWeek(18, 7, 1999) == "Sunday"    # Example 2
assert solution.dayOfTheWeek(15, 8, 1993) == "Sunday"    # Example 3

# Reference date
assert solution.dayOfTheWeek(1, 1, 1971) == "Friday"     # Base reference date

# Leap year checks
assert solution.dayOfTheWeek(29, 2, 1972) == "Tuesday"   # Leap day exists
assert solution.dayOfTheWeek(28, 2, 1972) == "Monday"    # Day before leap day
assert solution.dayOfTheWeek(1, 3, 1972) == "Wednesday"  # Day after leap day

# Century leap year
assert solution.dayOfTheWeek(29, 2, 2000) == "Tuesday"   # 2000 is leap year

# End of year
assert solution.dayOfTheWeek(31, 12, 1999) == "Friday"   # End of century

# Beginning of year
assert solution.dayOfTheWeek(1, 1, 2000) == "Saturday"   # New year rollover

# Maximum constraint
assert solution.dayOfTheWeek(31, 12, 2100) == "Friday"   # Upper bound

# Non leap year February
assert solution.dayOfTheWeek(28, 2, 2019) == "Thursday"  # Normal February

# Transition across months
assert solution.dayOfTheWeek(1, 3, 2019) == "Friday"     # Month boundary

Test Summary

Test Why
31/8/2019 Validates standard case
18/7/1999 Validates another normal date
15/8/1993 Validates repeated weekday result
1/1/1971 Verifies reference date
29/2/1972 Verifies leap day handling
28/2/1972 Checks day before leap day
1/3/1972 Checks day after leap day
29/2/2000 Verifies century leap year rule
31/12/1999 Verifies year end transition
1/1/2000 Verifies new year transition
31/12/2100 Verifies upper constraint boundary
28/2/2019 Verifies non leap February
1/3/2019 Verifies month transition

Edge Cases

Leap Year February

Leap years are the most common source of bugs in calendar problems. February normally has 28 days, but leap years add an extra day. Forgetting this adjustment causes all later weekday calculations in that year to become incorrect.

This implementation handles the issue using the is_leap helper function. Whenever February is processed during a leap year, one additional day is added to the total count.

Reference Date Alignment

Off by one errors are very easy to introduce when counting elapsed days. For example, incorrectly adding day instead of day - 1 would shift every answer by one weekday.

The implementation carefully treats January 1, 1971 as zero elapsed days. This ensures the reference weekday "Friday" maps correctly to index 0.

Century Leap Year Rules

Many implementations incorrectly assume every year divisible by 4 is a leap year. That rule fails for century years like 1900, which are not leap years unless divisible by 400.

This solution uses the complete Gregorian rule:

(y % 400 == 0) or (y % 4 == 0 and y % 100 != 0)

This correctly handles year 2000, which is a leap year because it is divisible by 400.