Day of the Week

Easy

#1110Time: O(Y + M), where Y is the number of years between the given year and the reference year (1971), and M is the number of months. Given the constraints (1971-2100), the number of iterations is small and bounded, so it can be considered O(1). However, compared to other approaches, it's less efficient as it involves loops.Space: O(1), as we only use a few variables and constant-size arrays to store data.

Patterns

Math

Prompt

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month and year respectively.

Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"

Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"

Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"

Constraints:

The given dates are valid dates between the years 1971 and 2100.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves selecting a known date and its corresponding day of the week as a reference point. We then calculate the total number of days that have passed between this reference date and the target date. The day of the week for the target date can be determined by taking this total number of days, adding the reference day's index, and finding the result modulo 7.

Algorithm

1. Define an array for the days of the week and an array for the number of days in each month.
1. Initialize a counter totalDays to 0.
1. Iterate from the reference year (1971) to year - 1. In each iteration, add 365 or 366 to totalDays based on whether the year is a leap year.
1. Iterate from month 1 to month - 1. In each iteration, add the number of days in that month to totalDays. Account for leap years for February.
1. Add the given day to totalDays.
1. Calculate the final day index using the total days and the reference day (Friday for Jan 1, 1971). The formula is (totalDays + 4) % 7.
1. Return the day of the week from the array using the calculated index.

Walkthrough

We'll use January 1st, 1971, as our reference date. A quick search reveals this day was a Friday. We can represent the days of the week with numbers, for example, Sunday=0, Monday=1, ..., Friday=5, Saturday=6. The algorithm proceeds as follows:

Calculate the total number of days from the reference year (1971) up to the year just before the input year. This involves iterating through each year and adding 365 days for a common year and 366 for a leap year.
Calculate the total number of days in the months preceding the input month within the input year. We'll use a pre-filled array for the number of days in each month, and we must remember to adjust for February in a leap year.
Add the input day to the total count.
Since our reference is Jan 1st, 1971, we have counted the days from Jan 1st, 1971, to the given date. The total number of days elapsed is total days - 1.
The final day of the week is (total elapsed days + reference day index) % 7. Since Jan 1, 1971 was a Friday (index 5), the formula is (total_days_from_1971_start + 5 - 1) % 7 which simplifies to (totalDays + 4) % 7. A year is a leap year if it is divisible by 4, except for years divisible by 100 but not by 400. The rule is: (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0).

1class Solution {2    public String dayOfTheWeek(int day, int month, int year) {3        String[] daysOfWeek = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};4        int[] daysInMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};5 6        // Reference date: Jan 1, 1971 was a Friday.7        int totalDays = 0;8 9        // 1. Count days for full years passed since 197110        for (int y = 1971; y < year; y++) {11            totalDays += isLeapYear(y) ? 366 : 365;12        }13 14        // 2. Count days for full months passed in the current year15        for (int m = 1; m < month; m++) {16            if (m == 2 && isLeapYear(year)) {17                totalDays += 29;18            } else {19                totalDays += daysInMonth[m];20            }21        }22 23        // 3. Count days in the current month24        totalDays += day;25 26        // Jan 1, 1971 was a Friday. Our daysOfWeek array starts with Sunday.27        // The index of Friday is 5.28        // The number of days passed since Jan 1, 1971 is `totalDays - 1`.29        // The index of the day is ( (days passed) + (index of ref day) ) % 730        // index = ( (totalDays - 1) + 5 ) % 7 = (totalDays + 4) % 731        return daysOfWeek[(totalDays + 4) % 7];32    }33 34    private boolean isLeapYear(int year) {35        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);36    }37}

Complexity

Time

O(Y + M), where Y is the number of years between the given year and the reference year (1971), and M is the number of months. Given the constraints (1971-2100), the number of iterations is small and bounded, so it can be considered O(1). However, compared to other approaches, it's less efficient as it involves loops.

Space

O(1), as we only use a few variables and constant-size arrays to store data.

Trade-offs

Pros

Intuitive and easy to understand the logic.
Doesn't rely on complex mathematical formulas.
Demonstrates handling of dates and leap years from first principles.

Cons

More code to write compared to other methods.
Prone to off-by-one errors in counting days or handling the reference date.
Less efficient than a direct formula if the year range were large.

Modern programming languages provide robust libraries for handling dates and times. In Java, we can use the java.time.LocalDate class (introduced in Java 8) or the older java.util.Calendar class. This approach leverages the built-in functionality to parse the date and directly query the day of the week.

Algorithm

1. Import the necessary java.time.LocalDate class.
1. Create an instance of LocalDate by calling LocalDate.of(year, month, day).
1. Call the getDayOfWeek() method on the LocalDate instance to get the DayOfWeek enum.
1. Use getDisplayName(TextStyle.FULL, Locale.ENGLISH) to get the full name of the day in English (e.g., "Saturday").
1. Return the resulting string.

Walkthrough

The java.time package is the modern and recommended way to handle dates in Java. We can create a LocalDate object representing the given date using the LocalDate.of(year, month, day) factory method. Once we have the LocalDate object, we can call the getDayOfWeek() method. This method returns a DayOfWeek enum value (e.g., DayOfWeek.SATURDAY). The final step is to convert this enum value into the required string format. The DayOfWeek enum values are in all caps (e.g., "SATURDAY"). We need to convert this to title case (e.g., "Saturday").

1import java.time.LocalDate;2import java.time.format.TextStyle;3import java.util.Locale;4 5class Solution {6    public String dayOfTheWeek(int day, int month, int year) {7        // Create a LocalDate object from the given year, month, and day8        LocalDate date = LocalDate.of(year, month, day);9        10        // Get the DayOfWeek enum11        java.time.DayOfWeek dayOfWeekEnum = date.getDayOfWeek();12        13        // Format the enum name to the required title case string14        // e.g., MONDAY -> Monday15        return dayOfWeekEnum.getDisplayName(TextStyle.FULL, Locale.ENGLISH);16    }17}

Complexity

Time

O(1). The underlying implementation is highly optimized and performs the calculation in constant time for any valid date.

Space

O(1). A few objects are created, but the space usage does not depend on the input values.

Trade-offs

Pros

Extremely simple and concise code.
Highly reliable and less error-prone, as it relies on a well-tested standard library.
Handles all date-related complexities (like leap years, calendar changes) transparently.

Cons

May not be permitted in an interview setting that aims to test fundamental algorithm design.
It abstracts away the core logic of how the day of the week is actually calculated.

This approach uses a direct mathematical formula to compute the day of the week without any iteration. Several such formulas exist, like Zeller's Congruence. A particularly elegant and simple one is Sakamoto's algorithm. It involves a few arithmetic operations and a small lookup table for month offsets.

Algorithm

1. Define an array for the days of the week strings, ordered from Sunday to Saturday.
1. Define the month offset table t.
1. Check if the month is January or February. If so, decrement the year by 1.
1. Apply Sakamoto's formula to calculate the day index.
1. Use the calculated index to retrieve the day name from the daysOfWeek array.
1. Return the day name.

Walkthrough

Sakamoto's algorithm calculates the day of the week (where Sunday = 0, Monday = 1, etc.) for any Gregorian date. The formula is: dayOfWeek = (year + year/4 - year/100 + year/400 + t[month-1] + day) % 7 The components are:

year, month, day: The input date.
t: A lookup table for the number of days passed in the year before the given month begins. The table is t = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}.
An important adjustment: if the month is January or February (month < 3), we treat it as part of the previous year. So, we decrement year by 1. This is because the leap day (Feb 29) affects the calculation for all subsequent days in that year. The terms year/4 - year/100 + year/400 account for the number of leap years that have occurred since year 0. The final result of the formula is an integer from 0 to 6, which can be mapped to the corresponding day of the week string.

1class Solution {2    public String dayOfTheWeek(int day, int month, int year) {3        String[] daysOfWeek = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};4        5        // Sakamoto's algorithm6        int[] t = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};7        8        if (month < 3) {9            year -= 1;10        }11        12        int dayIndex = (year + year / 4 - year / 100 + year / 400 + t[month - 1] + day) % 7;13        14        return daysOfWeek[dayIndex];15    }16}

Complexity

Time

O(1). The calculation involves a fixed number of arithmetic operations, regardless of the input date. This is the most computationally efficient approach.

Space

O(1). We use a constant-size array for the month offsets and another for the day names.

Trade-offs

Pros

The fastest possible runtime performance.
Elegant and purely mathematical.
Demonstrates deep knowledge of calendar algorithms.

Cons

The formula is non-obvious and difficult to derive or remember from scratch. It can seem like "magic".
Less readable than the counting approach for someone unfamiliar with the algorithm.

Solutions

Solution

1import java.util.Calendar ; class Solution { private static final String [] WEEK = { "Sunday" , "Monday" , "Tuesday" , "Wednesday" , "Thursday" , "Friday" , "Saturday" }; public static String dayOfTheWeek ( int day , int month , int year ) { Calendar calendar = Calendar . getInstance (); calendar . set ( year , month - 1 , day ); return WEEK [ calendar . get ( Calendar . DAY_OF_WEEK ) - 1 ]; } }

1class Solution {2public:3  string dayOfTheWeek(int d, int m, int y) {4    if (m < 3) {5      m += 12;6      y -= 1;7    }8    int c = y / 100;9    y %= 100;10    int w = (c / 4 - 2 * c + y + y / 4 + 13 * (m + 1) / 5 + d - 1) % 7;11    vector<string> weeks = {"Sunday",   "Monday", "Tuesday", "Wednesday",12                            "Thursday", "Friday", "Saturday"};13    return weeks[(w + 7) % 7];14  }15};

1class Solution:2    def dayOfTheWeek(self, day: int, month: int,3                     year: int) -> str: return datetime . date(year, month, day). strftime('%A')

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1import java.util.Calendar ; class Solution { private static final String [] WEEK = { "Sunday" , "Monday" , "Tuesday" , "Wednesday" , "Thursday" , "Friday" , "Saturday" }; public static String dayOfTheWeek ( int day , int month , int year ) { Calendar calendar = Calendar . getInstance (); calendar . set ( year , month - 1 , day ); return WEEK [ calendar . get ( Calendar . DAY_OF_WEEK ) - 1 ]; } }

1class Solution {2public:3  string dayOfTheWeek(int d, int m, int y) {4    if (m < 3) {5      m += 12;6      y -= 1;7    }8    int c = y / 100;9    y %= 100;10    int w = (c / 4 - 2 * c + y + y / 4 + 13 * (m + 1) / 5 + d - 1) % 7;11    vector<string> weeks = {"Sunday",   "Monday", "Tuesday", "Wednesday",12                            "Thursday", "Friday", "Saturday"};13    return weeks[(w + 7) % 7];14  }15};

1class Solution:2    def dayOfTheWeek(self, day: int, month: int,3                     year: int) -> str: return datetime . date(year, month, day). strftime('%A')

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.