LeetCode 2777 - Date Range Generator

The problem asks us to generate a sequence of dates starting from a given start date and ending at a given end date, incrementing by a fixed number of days defined by step.

leetcodemedium

LeetCode Problem 2777

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

The problem asks us to generate a sequence of dates starting from a given start date and ending at a given end date, incrementing by a fixed number of days defined by step. Both start and end are strings in the YYYY-MM-DD format, and the output must also yield strings in this same format. The generator should produce dates lazily, one at a time, in sequence, without precomputing the entire list.

The inputs represent specific calendar dates, while step controls the interval between consecutive dates. The output is expected to respect the inclusive range, meaning that if the end date aligns with a step, it should be included.

The constraints tell us that start will never be later than end, the maximum range is moderate (up to 1500 days), and step is between 1 and 1000. These constraints indicate that a simple iteration with day increments is feasible, and there are no negative or malformed ranges.

Edge cases to be aware of include when start equals end, when step is larger than the total range (yielding only the start date), and when the step does not perfectly divide the range (the last date before end should still be included if within bounds).

Approaches

The brute-force approach would convert the start and end dates to date objects, iterate from start to end one day at a time, and yield every date that aligns with the step. This works correctly but is inefficient if the step is large, as it still iterates daily even if most iterations are skipped.

The optimal approach observes that Python and Go allow direct addition of a fixed number of days to a date object. By incrementing the current date by step days directly in each iteration, we avoid unnecessary intermediate computations and only generate exactly the dates we need. This leverages the fact that date arithmetic is O(1) in modern date libraries.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Iterate daily from start to end, yield only matching step
Optimal O(m) O(1) Increment current date by step directly, yields only needed dates

Where n is the number of days between start and end and m is the number of yielded dates (m ≈ n/step).

Algorithm Walkthrough

  1. Parse the input start and end strings into date objects. This allows for arithmetic operations on dates.
  2. Initialize a current variable to the start date.
  3. While current is less than or equal to end, yield the current date formatted back as YYYY-MM-DD.
  4. Increment current by step days.
  5. Continue until current exceeds end.

Why it works: The invariant is that current always points to the next valid date to yield. Since we increment by step each time and stop when exceeding end, we guarantee all dates in the inclusive range that match the step are returned in order. The use of date arithmetic handles month and year rollovers correctly.

Python Solution

from datetime import datetime, timedelta
from typing import Generator

def dateRangeGenerator(start: str, end: str, step: int) -> Generator[str, None, None]:
    start_date = datetime.strptime(start, "%Y-%m-%d").date()
    end_date = datetime.strptime(end, "%Y-%m-%d").date()
    current = start_date
    delta = timedelta(days=step)
    
    while current <= end_date:
        yield current.strftime("%Y-%m-%d")
        current += delta

The code first converts input strings into date objects to allow arithmetic operations. timedelta(days=step) represents the interval between yielded dates. The loop checks if the current date is within bounds, yields the formatted string, and then moves current forward by step days. This directly implements the optimal approach.

Go Solution

package main

import (
    "time"
    "fmt"
)

func dateRangeGenerator(start string, end string, step int) <-chan string {
    out := make(chan string)
    go func() {
        defer close(out)
        startDate, _ := time.Parse("2006-01-02", start)
        endDate, _ := time.Parse("2006-01-02", end)
        for current := startDate; !current.After(endDate); current = current.AddDate(0, 0, step) {
            out <- current.Format("2006-01-02")
        }
    }()
    return out
}

The Go implementation differs in that it returns a channel instead of a Python generator. We use time.Parse to convert strings to time.Time objects, current.AddDate(0, 0, step) to increment the date, and current.Format("2006-01-02") to format the string. The channel allows lazy consumption similar to Python’s generator.

Worked Examples

Example 1:

Iteration Current Date Output
1 2023-04-01 2023-04-01
2 2023-04-02 2023-04-02
3 2023-04-03 2023-04-03
4 2023-04-04 2023-04-04

Example 2:

Iteration Current Date Output
1 2023-04-10 2023-04-10
2 2023-04-13 2023-04-13
3 2023-04-16 2023-04-16
4 2023-04-19 2023-04-19

Example 3:

Iteration Current Date Output
1 2023-04-10 2023-04-10

Complexity Analysis

Measure Complexity Explanation
Time O(m) Only yields the necessary dates, where m = ceil((end-start)/step)
Space O(1) Constant extra space for current date and delta

Because we avoid iterating day by day unnecessarily, the generator only computes the dates needed, making it efficient. Storage is constant as we yield values one at a time.

Test Cases

# provided examples
assert list(dateRangeGenerator("2023-04-01", "2023-04-04", 1)) == ["2023-04-01","2023-04-02","2023-04-03","2023-04-04"]
assert list(dateRangeGenerator("2023-04-10", "2023-04-20", 3)) == ["2023-04-10","2023-04-13","2023-04-16","2023-04-19"]
assert list(dateRangeGenerator("2023-04-10", "2023-04-10", 1)) == ["2023-04-10"]

# edge cases
assert list(dateRangeGenerator("2023-04-01", "2023-04-01", 10)) == ["2023-04-01"] # step larger than range
assert list(dateRangeGenerator("2023-04-01", "2023-04-05", 2)) == ["2023-04-01","2023-04-03","2023-04-05"] # step divides range partially
assert list(dateRangeGenerator("2023-12-30", "2024-01-02", 1)) == ["2023-12-30","2023-12-31","2024-01-01","2024-01-02"] # crossing year boundary
Test Why
start = end checks minimal range
step > range ensures only start is yielded
step divides range partially confirms last date handling
year boundary validates date arithmetic across months/years

Edge Cases

First, when the start date equals the end date, a naive loop might skip iteration. Our implementation correctly yields the single date.

Second, when step is larger than the total range, a loop incrementing by step must not skip the first date. The algorithm correctly yields only the start date.

Third, when the range crosses month or year boundaries, date arithmetic could be error-prone. Using Python datetime.date or Go time.Time ensures proper handling of month lengths, leap years, and year transitions automatically.