Brute Force Solution

The brute force solution would involve parsing the date string, determining if the year is a leap year, and then summing the days in each month up to the given month.

Code (Python):

def dayOfYear_brute_force(date):
    year, month, day = map(int, date.split('-'))
    
    days_in_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    
    if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
        days_in_month[2] = 29
        
    day_number = 0
    for i in range(1, month):
        day_number += days_in_month[i]
    
    day_number += day
    return day_number

Big O Analysis:

• Time Complexity: O(M), where M is the month number. In the worst case, we iterate through all the months.
• Space Complexity: O(1), as we use a fixed-size array to store the days in each month.

Optimal Solution

The optimal solution is similar to the brute force approach, but can be slightly improved by pre-calculating leap year status and reducing redundant operations.

Code (Python):

def dayOfYear(date):
    year, month, day = map(int, date.split('-'))
    
    is_leap = (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)
    
    days_before_month = [0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334]
    
    day_number = days_before_month[month - 1] + day
    
    if is_leap and month > 2:
        day_number += 1
        
    return day_number

Big O Analysis:

• Time Complexity: O(1), as the operations performed are constant regardless of the input size.
• Space Complexity: O(1), as we use a fixed-size array to store the cumulative days.

Edge Cases

• Invalid Date: The problem statement specifies that the input date is always a valid Gregorian calendar date between Jan 1st, 1900 and Dec 31st, 2019, so no input validation is required.
• Leap Year: Correctly handling leap years is crucial. The year 2000 was a valid leap year even though it is divisible by 100, because it is also divisible by 400.