Problem Description

Given a date specified by three integers day, month, and year, return the corresponding day of the week as a string. The returned value should be one of: "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", or "Saturday".

The input guarantees that the date is valid according to the Gregorian calendar (the calendar system in common use today). The problem assumes all dates are after 1971.

Constraints:

• day, month, and year together represent a valid date.
• Return the day of the week as a string, matching the capitalization and spelling specified above.

Thought Process

At first glance, this problem seems to require determining which day of the week a particular date falls on. While you could try to simulate the passage of days from a known "anchor" date, this would be slow and error-prone, especially for dates far in the future or past.

A brute-force approach might involve counting days from a fixed starting point (like January 1, 1971) and incrementing a counter, but this is inefficient and can be tricky due to leap years and different month lengths.

Instead, we can use a well-known algorithm or built-in library to calculate the day of the week directly. Many programming languages have date libraries that handle this, but it's also possible to use formulas like Zeller's Congruence or the Doomsday algorithm.

The key is to convert the given date to a weekday index (0-6), then map that to the correct weekday name.

Solution Approach

There are two main approaches:

• 1. Use Built-in Date Libraries: Most modern languages provide a standard way to parse a date and retrieve the day of the week. This is the simplest and most reliable method.
• 2. Manual Calculation (e.g. Zeller's Congruence): If built-in libraries are not allowed, we can use a mathematical formula to compute the day of the week. Zeller's Congruence is a classic algorithm for this.

For most Leetcode submissions, the first approach (using built-in libraries) is acceptable and concise. Here's the step-by-step approach:

1. Convert the input day, month, and year into a date object (or use them directly in the formula).
2. Use the language's date handling to get the day of the week as an integer (e.g., 0 for Sunday, 1 for Monday, etc.).
3. Map this integer to the correct weekday name according to the required output.
4. Return the weekday name as a string.

If using Zeller's Congruence:

• If the month is January or February, subtract 1 from the year and add 12 to the month (treating them as months 13 and 14 of the previous year).
• Plug the values into the formula to get the weekday index.
• Map the index to the weekday name.

Example Walkthrough

Example: day = 31, month = 8, year = 2019

1. We create a date for August 31, 2019.
2. Using a built-in library (or Zeller's Congruence), we determine which day of the week it is.
3. For this date, the result is Saturday.
4. We return the string "Saturday".

Step-by-step using Zeller's Congruence:

• Since August > 2, we use the year as is.
• Let q = 31 (day), m = 8 (month), y = 2019 (year).
• Apply the formula:
  h = (q + [13(m+1)/5] + K + [K/4] + [J/4] + 5J) % 7
  Where K = year % 100, J = year // 100.
• Plug values in: K = 19, J = 20
• Calculate h and map to the weekday (0=Saturday, 1=Sunday, ...).
• For this input, h = 0, so the answer is "Saturday".

Time and Space Complexity

Brute-force approach: If you were to count days from an anchor date, the time complexity would be O(N), where N is the number of days between the anchor and the target date. This is inefficient for dates far apart.

Optimized approach (using built-in libraries or Zeller's Congruence): Both have O(1) time and O(1) space complexity, since the calculation involves only a fixed number of arithmetic operations or a simple lookup.

Summary

The problem can be solved efficiently by leveraging either standard date libraries or a mathematical formula like Zeller's Congruence. Both approaches yield the day of the week in constant time and space. The elegance of the solution comes from recognizing that we do not need to simulate every day, but can instead use a direct computation or reliable library call.

Code Implementation

import datetime

class Solution:
    def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
        d = datetime.date(year, month, day)
        # weekday() returns 0 for Monday
        return days[d.weekday()]
      

class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        vector<string> days = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        // Zeller's Congruence
        if (month < 3) {
            month += 12;
            year -= 1;
        }
        int K = year % 100;
        int J = year / 100;
        int h = (day + 13 * (month + 1) / 5 + K + K/4 + J/4 + 5*J) % 7;
        return days[h];
    }
};
      

class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        String[] days = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        // Zeller's Congruence
        if (month < 3) {
            month += 12;
            year -= 1;
        }
        int K = year % 100;
        int J = year / 100;
        int h = (day + 13 * (month + 1) / 5 + K + K/4 + J/4 + 5*J) % 7;
        return days[h];
    }
}
      

var dayOfTheWeek = function(day, month, year) {
    const days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"];
    // JavaScript Date: month is 0-based
    let d = new Date(year, month - 1, day);
    return days[d.getDay()];
};