In this post we will attempt to solve the LeetCode 1185 Day of the Week problem.
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"}.
In a nutshell we are given a date in day, month, and year and we need to return a string that contains the name of the day. The problem is very easy to understand.
When I read it, I figured that the standard approach of using the date and time classes and functions provided by different programming languages was going to have poor performance. Let’s see what we find out after we complete a first pass of the function of interest and have the runtime statistics.
We will solve the problem using the Java programming language and the VSCode IDE on a Windows platform. You should consider using the online IDE provided by LeetCode. I will only use it to test the function of interest.
In addition to solving the problem, we will need a simple test scaffold to collect the input data, create and populate variables as needed, call the function of interest and display the output. This code IS NOT PART OF THE SOLUTION!
public String dayOfTheWeek(int day, int month, int year) {
}
The prototype for the function of interest matches the description of the problem. Please make sure that you read the current description from the LeetCode website before proceeding with a solution. Requirements may be adjusted with time.
6, 12, 2021 main <<< day: 6 month: 12 year: 2021 main <<< output ==>Monday<== 31, 8, 2019 main <<< day: 31 month: 8 year: 2019 main <<< output ==>Saturday<== main <<< output ==>Saturday<== 18, 7, 1999 main <<< day: 18 month: 7 year: 1999 main <<< output ==>Sunday<== main <<< output ==>Sunday<== 15, 8, 1993 main <<< day: 15 month: 8 year: 1993 main <<< output ==>Sunday<== main <<< output ==>Sunday<==
The first line in each test contains the date expressed in day, month and year. Our test code displays the values after it has read and parsed the input line and has assigned the values to int variables. This is done to make sure all is well so far. Then the function of interest is called and the returned value is displayed. The great thing with this problem is that we can check the result with most online calendars.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read day, month and year ****
int[] arr = Arrays.stream(br.readLine().trim().split(", "))
.mapToInt(Integer::parseInt)
.toArray();
// **** for ease of use ****
int day = arr[0];
int month = arr[1];
int year = arr[2];
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< day: " + day + " month: " + month + " year: " + year);
// **** call function of interest and return output ****
System.out.println("main <<< output ==>" + dayOfTheWeek0(day, month, year) + "<==");
// **** call function of interest and return output ****
System.out.println("main <<< output ==>" + dayOfTheWeek(day, month, year) + "<==");
}
Our test scaffold reads the input line into an array of int[]. For ease of use the values are assigned to variables. We could just have called the function of interest with the contents of the array directly.
Two versions of the function of interest are called and their respective values are displayed.
/**
* Given a date, return the corresponding day of the week for that date.
*
* Runtime: 28 ms, faster than 5.17% of Java online submissions for Day of the Week.
* Memory Usage: 38.7 MB, less than 14.14% of Java online submissions for Day of the Week.
*
* 43 / 43 test cases passed.
* Status: Accepted
* Runtime: 28 ms
* Memory Usage: 38.7 MB
*/
static public String dayOfTheWeek0(int day, int month, int year) {
// **** formatter, format date, day of week, and get display name ****
DateTimeFormatter formatter = DateTimeFormatter.ofPattern("d/M/yyyy");
LocalDate date = LocalDate.parse("" + day + "/" + month + "/" + year, formatter);
DayOfWeek dow = date.getDayOfWeek();
return dow.getDisplayName(TextStyle.FULL, Locale.US);
}
This function uses some classes in standard libraries. Different languages provide similar sets of classes and functions.
There is little to add regarding the actual code.
Take a look at the comment section of this function in the code. The solution was accepted but we should be able to do better!
I went online and did a search on GeeksforGeeks, stackoverflow and Wikipedia.
/**
* Given a date, return the corresponding day of the week for that date.
*
* Execution: O(1) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 37.4 MB, less than 42.41% of Java online submissions.
*
* 43 / 43 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 37.4 MB
*/
static public String dayOfTheWeek(int day, int month, int year) {
// **** sanity check(s) ****
// if (day < 1 || day > 31) return "";
// if (month < 1 || month > 12) return "";
// **** initialization ****
int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
String dayOfWeek[] = {
"Sunday",
"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saturday"
};
// **** due to Sakamoto's method ****
if (month < 3) year -= 1;
// **** return string representation of day of the week ****
return dayOfWeek[(year + year / 4 - year / 100 + year / 400 + t[month - 1] + day) % 7];
}
We start by performing some sanity checks. I checked back into the Constraints section in the problem definition and there is no need to check the arguments. They are valid values!
We then create a table with some integer values followed by a table with the strings associated with the days of the week. The contents of the `t` array is the Table of Month Offsets. The Wikipedia article Determination of the day of the week provides a very good description of the contents of this table.
Please take a look at the comments section of this implementation. It is considerably faster than the first.
/**
* Check if the specified year is or is not a leap year.
*
* !!!! NOT PART OF SOLUTION !!!!
*/
static private boolean isLeapYear(int year) {
// **** check if year is multiple of 400 (leap year) ****
if (year % 400 == 0) return true;
// **** check if year is multiple of 100 (not a leap year) ****
if (year % 100 == 0) return false;
// **** check if year is multiple of 4 (leap year) ****
if (year % 4 == 0) return true;
// **** not a leap year ****
return false;
}
While I was experimenting with different algorithms, I wrote this function whose calculations are used in the last line of the second implementation. I left the function because it helps understand how one can determine if a year is a leap year.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named DayOfWeek.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge, and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John