How do you solve Day of the Week on LeetCode?

Day of the Week (LeetCode #1185) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: Understanding leap years is crucial for accurate calculations.

What is the brute force solution for Day of the Week?

The brute force approach for Day of the Week is Brute Force, with O(n²) time complexity and O(1) space complexity. We can calculate the day of the week by counting the total number of days from a known reference date (January 1, 1971) to the given date. This involves checking each year and month to see how many days have passed. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Day of the Week?

Day of the Week uses the following concepts: Math. The recommended patterns to study are: Mathematical Formulas, Modular Arithmetic.

What are the interview tips for Day of the Week?

Explain your thought process clearly. Be prepared to discuss edge cases, like leap years. Practice implementing Zeller's Congruence to gain confidence.

What are common mistakes when solving Day of the Week?

Forgetting to adjust for leap years. Not handling January and February correctly in Zeller's formula.

#1185

Day of the Week

Easy

MathMathematical FormulasModular Arithmetic

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

We can use Zeller's Congruence, a mathematical formula that directly computes the day of the week for any date. This approach is efficient and avoids the need to count days manually.

⚙️

Algorithm

3 steps

1Step 1: Adjust the month and year for January and February (consider them as months 13 and 14 of the previous year).
2Step 2: Apply Zeller's Congruence formula: h = (q + (13(m + 1) / 5) + K + (K / 4) + (J / 4) - 2J) % 7.
3Step 3: Map the result to the corresponding day of the week.

solution.py10 lines

1def dayOfTheWeek(day, month, year):
2    if month < 3:
3        month += 12
4        year -= 1
5    q = day
6    m = month
7    K = year % 100
8    J = year // 100
9    h = (q + (13 * (m + 1)) // 5 + K + (K // 4) + (J // 4) - 2 * J) % 7
10    return ['Saturday', 'Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday'][h]

ℹ

Complexity note: The time complexity is O(1) because the calculations do not depend on the size of the input; they are performed in constant time.

1Understanding leap years is crucial for accurate calculations.
2Zeller's Congruence is a powerful formula that simplifies the problem.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.