2777. Date Range Generator


Problem Description

The problem requires us to create a range of dates that starts with a given "start" date and ends at an "end" date, including both start and end dates. The range should be generated using a given "step" value, which specifies the interval between consecutive dates in terms of days. We want to yield each date in this range as a string in the format "YYYY-MM-DD".

Intuition

To solve this problem, we use the JavaScript Date object, which enables us to work easily with dates. The procedure includes:

  1. Parsing the provided "start" and "end" string dates into JavaScript Date objects, which allows us to manipulate dates with built-in methods.

  2. Iterating from the start date to the end date, increasing the date by the step value every iteration. We achieve this by using the getDate and setDate methods that the Date object provides. The getDate method gets the day of the month from a Date object and setDate sets the day of the month to a specified number. By adding the step to the current day, we move our date forward by that many days.

  3. During each iteration, we convert the current date to an ISO string using toISOString. ISO strings are in the format "YYYY-MM-DDTHH:MM:SS.ZZZZ". However, since we only need the date part without the time, we use slice to obtain the first 10 characters of the ISO string which represent the date in the required "YYYY-MM-DD" format.

  4. Yielding the formatted date string using yield, which is part of creating a generator. Generators are special functions in JavaScript that can be exited and re-entered later with their context (variable bindings) being saved between re-entries.

  5. Continuing this process until the current date exceeds the end date, at which point the generator finishes.

This solution effectively gives us a custom range of dates, and by using a generator, we can efficiently go through the range one date at a time without needing to precompute the entire range at once.

Solution Approach

The solution to this problem involves a step-by-step approach using a generator function to yield the desired range of dates one by one. Here's how the solution is implemented:

  1. Initialize Dates: First, we need to convert the input start and end strings into Date objects using JavaScript's new Date() constructor. This allows us to perform date arithmetic and make use of Date object methods.

  2. Create Generator Function: We then declare a generator function called dateRangeGenerator that takes start, end, and step as arguments. A generator function is defined with function* syntax and is capable of yielding values one at a time with the yield keyword.

  3. Iterate Through Dates: Inside the generator function, we initiate a while loop that will continue as long as the currentDate is less than or equal to the endDate.

  4. Yield Current Date: For each iteration within the loop, the current date (formatted as "YYYY-MM-DD" using toISOString().slice(0, 10)) is yielded. This means that every time the generator's next() method is called, it will return an object with a value of the current date string and a done status indicating whether the generator has finished iterating.

  5. Increment Date: To move to the next date in the range, we use currentDate.getDate() to get the day of the month for currentDate, add the step value to it, and update currentDate with this new value using currentDate.setDate(). This effectively increments currentDate by the step number of days.

  6. Finish Iteration: As soon as currentDate exceeds endDate, the condition in the while loop becomes false, and the generator finishes its execution. Any further calls to next() after this point will return an object with a done status of true, indicating there are no more values to yield.

By utilizing a generator function and the JavaScript Date object, the solution elegantly traverses a range of dates and provides them on-demand, handling date arithmetic internally without the caller needing to manage the date range state. This allows for an efficient, on-the-fly generation of date strings that can be iterated over using the generator's next() method.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we want to create a range of dates from "2021-11-01" to "2021-11-05" with a step of 2 days. We will use the outlined solution approach to generate the desired date strings.

  1. Initialize Dates: We convert the input strings "2021-11-01" and "2021-11-05" to JavaScript Date objects:

    1const startDate = new Date("2021-11-01");
    2const endDate = new Date("2021-11-05");
  2. Create Generator Function: We create a generator function dateRangeGenerator which takes startDate, endDate, and step as parameters:

    1function* dateRangeGenerator(start, end, step) {
    2    // Generator function body will be implemented here
    3}
  3. Iterate Through Dates: We initiate a loop inside the generator function, where we will generate dates from startDate to endDate. We use a while loop for this purpose:

    1let currentDate = new Date(start.getTime()); // avoid modifying the original start date
    2
    3while (currentDate <= end) {
    4    // The body of the loop will yield dates and increment `currentDate`
    5}
  4. Yield Current Date: During each iteration, we format the currentDate as a string and yield it:

    1yield currentDate.toISOString().slice(0, 10);
  5. Increment Date: After yielding the date, we increment currentDate by the step value. In this example, we add 2 days:

    1const nextDay = currentDate.getDate() + step;
    2currentDate.setDate(nextDay); // This will increment `currentDate` by 2 days.
  6. Finish Iteration: The loop continues until currentDate is greater than endDate. When that condition is met, the loop terminates, and the generator finishes:

    1// Loop has ended, so the generator is complete.

Putting it all together, our generator function will be used as follows:

1const dateRange = dateRangeGenerator(startDate, endDate, 2);
2console.log(dateRange.next().value); // "2021-11-01"
3console.log(dateRange.next().value); // "2021-11-03"
4console.log(dateRange.next().value); // "2021-11-05"
5console.log(dateRange.next().done);  // true, as no more dates are left

The output of each console.log illustrates how the generator yields each date string when .next() is called. After the last date, calling .next() indicates that the generator is finished by returning {done: true}.

Solution Implementation

1from datetime import datetime, timedelta
2
3# This generator function yields a range of dates, incrementing by a given step in days.
4# Parameters:
5# - start_date_str: The start date in ISO format (YYYY-MM-DD).
6# - end_date_str: The end date in ISO format (YYYY-MM-DD).
7# - step_days: The number of days to increment each time.
8# It yields a string representing the current date in ISO format (YYYY-MM-DD) at each iteration.
9def date_range_generator(start_date_str, end_date_str, step_days):
10    # Convert the start and end date strings into datetime objects.
11    start_date = datetime.fromisoformat(start_date_str)
12    end_date = datetime.fromisoformat(end_date_str)
13    # Initialize the current date to the start date.
14    current_date = start_date
15
16    # Continue yielding dates until the current date exceeds the end date.
17    while current_date <= end_date:
18        # Yield the current date as a string in ISO date format.
19        yield current_date.strftime('%Y-%m-%d')
20        # Increment the current date by the step value in days.
21        current_date += timedelta(days=step_days)
22
23# Usage example:
24date_generator = date_range_generator('2023-04-01', '2023-04-04', 1)
25for date in date_generator:
26    print(date)  # Prints '2023-04-01', '2023-04-02', '2023-04-03', '2023-04-04'
27
1import java.time.LocalDate;
2import java.time.temporal.ChronoUnit;
3import java.util.Iterator;
4import java.util.NoSuchElementException;
5
6/**
7 * This Iterable class provides a range of dates, incrementing by a given step in days.
8 * Parameters:
9 * - start: The start date in ISO format (YYYY-MM-DD).
10 * - end: The end date in ISO format (YYYY-MM-DD).
11 * - step: The number of days to increment each time.
12 * It yields a string representing the current date in ISO format (YYYY-MM-DD) on each iteration.
13 */
14public class DateRange implements Iterable<String> {
15
16    private LocalDate startDate;
17    private LocalDate endDate;
18    private int step;
19
20    public DateRange(String start, String end, int step) {
21        this.startDate = LocalDate.parse(start);
22        this.endDate = LocalDate.parse(end);
23        this.step = step;
24    }
25
26    @Override
27    public Iterator<String> iterator() {
28        return new Iterator<String>() {
29
30            private LocalDate currentDate = startDate;
31
32            @Override
33            public boolean hasNext() {
34                // Check if the current date has not passed the end date
35                return !currentDate.isAfter(endDate);
36            }
37
38            @Override
39            public String next() {
40                if (!hasNext()) {
41                    throw new NoSuchElementException("No more dates to generate.");
42                }
43                // Store the current date as it should be returned
44                LocalDate current = currentDate;
45                // Increment the current date by the step value in days
46                currentDate = currentDate.plusDays(step);
47                // Return the current date as a string in ISO date format
48                return current.toString();
49            }
50        };
51    }
52
53}
54
55// Usage example:
56
57public class Main {
58    public static void main(String[] args) {
59        DateRange dateRange = new DateRange("2023-04-01", "2023-04-04", 1);
60        for (String date : dateRange) {
61            System.out.println(date); // Outputs each date in the range
62        }
63    }
64}
65
1#include <iostream>
2#include <ctime>
3#include <string>
4
5// This class represents a generator that yields a range of dates, incrementing by a given step in days.
6class DateRangeGenerator {
7public:
8    // Constructs the generator with start, end dates and step value.
9    // - startDate: The start date in ISO format (YYYY-MM-DD).
10    // - endDate: The end date in ISO format (YYYY-MM-DD).
11    // - stepDays: The number of days to increment each time.
12    DateRangeGenerator(const std::string& startDate, const std::string& endDate, int stepDays)
13        : endDate(ConvertToDate(endDate)), step(stepDays) {
14        currentDate = ConvertToDate(startDate);
15    }
16
17    // Checks if there are more dates to generate.
18    bool HasNext() const {
19        return currentDate <= endDate;
20    }
21
22    // Returns the next date in the range, moving forward by the step value.
23    std::string Next() {
24        if (!HasNext()) {
25            return ""; // End of the range, no more dates to generate.
26        }
27
28        std::string currentDateString = ConvertToString(currentDate);
29        IncrementDate(currentDate, step); // Move to the next date.
30        return currentDateString;
31    }
32
33private:
34    // Converts ISO date string to tm structure.
35    tm ConvertToDate(const std::string& isoDate) const {
36        tm date = {};
37        sscanf(isoDate.c_str(), "%d-%d-%d", &date.tm_year, &date.tm_mon, &date.tm_mday);
38        date.tm_year -= 1900; // tm_year is years since 1900.
39        date.tm_mon -= 1;     // tm_mon is 0-based.
40        return date;
41    }
42
43    // Converts tm structure to ISO date string.
44    std::string ConvertToString(const tm& date) const {
45        char buffer[11];
46        // Add 1900 to tm_year to get the full year and 1 to tm_mon as it is 0-based.
47        snprintf(buffer, sizeof(buffer), "%04d-%02d-%02d", date.tm_year + 1900, date.tm_mon + 1, date.tm_mday);
48        return std::string(buffer);
49    }
50
51    // Increments the date by given step value in days.
52    void IncrementDate(tm& date, int days) const {
53        const time_t ONE_DAY = 24 * 60 * 60; // One day in seconds.
54        // Convert tm structure to time_t.
55        time_t date_time = mktime(&date);
56        // Increment the date by the number of days converted to seconds.
57        date_time += days * ONE_DAY;
58        // Convert back to tm structure.
59        date = *localtime(&date_time);
60    }
61
62    tm currentDate; // Current date to yield.
63    tm endDate;   // End date for the range.
64    int step;     // Increment step in days.
65};
66
67/*
68// Usage example:
69int main() {
70    // Create a date range generator from April 1st to April 4th with a step of 1 day.
71    DateRangeGenerator dateGenerator("2023-04-01", "2023-04-04", 1);
72
73    // Iterate through the generated dates and print them.
74    while (dateGenerator.HasNext()) {
75        std::cout << dateGenerator.Next() << std::endl;
76    }
77
78    return 0;
79}
80*/
81
1// This generator function yields a range of dates, incrementing by a given step in days.
2// Parameters:
3// - start: The start date in ISO format (YYYY-MM-DD).
4// - end: The end date in ISO format (YYYY-MM-DD).
5// - step: The number of days to increment each time.
6// It yields a string representing the current date in ISO format (YYYY-MM-DD) at each iteration.
7function* dateRangeGenerator(start: string, end: string, step: number): Generator<string> {
8    // Convert the start and end strings into Date objects.
9    const startDate = new Date(start);
10    const endDate = new Date(end);
11    // Initialize the current date to the start date.
12    let currentDate = startDate;
13
14    // Continue yielding dates until the current date exceeds the end date.
15    while (currentDate <= endDate) {
16        // Yield the current date as a string in ISO date format.
17        yield currentDate.toISOString().slice(0, 10);
18        // Increment the current date by the step value in days.
19        currentDate.setDate(currentDate.getDate() + step);
20    }
21}
22
23/*
24// Usage example:
25const dateGenerator = dateRangeGenerator('2023-04-01', '2023-04-04', 1);
26console.log(dateGenerator.next().value); // '2023-04-01'
27console.log(dateGenerator.next().value); // '2023-04-02'
28console.log(dateGenerator.next().value); // '2023-04-03'
29console.log(dateGenerator.next().value); // '2023-04-04'
30console.log(dateGenerator.next().done); // true (indicates that the generator is finished)
31*/
32

Time and Space Complexity

The time complexity of the dateRangeGenerator function is O(N) where N is the number of dates generated between the start and end dates with the specified step. This is because the function generates each date in the range one by one in a loop, and the number of iterations of the loop equals the number of dates.

The space complexity of the function is O(1) since it yields the dates one by one and does not store all the dates in memory. The storage used does not grow with the size of the date range; the function only keeps track of the current date and the parameters provided.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄