Identify any missing periods and combine the years into a single range

Question

Identify any missing periods and combine the years into a single range

I am working on restructuring year ranges with gaps and consolidating them. For example, converting [{start: 2002, end: 2020}, {start: 2020, end: null}] to {start: 2002, end: null} or [{2002, 2004},{2006, 2008}, {2008, null}] to [{2002-2004}, {2006-null}].

This task is related to tracking politicians' party memberships using an API, dealing with complications when they switch parties or rejoin previous ones.

interface YearRange{
    start: number
    end: number
}

function analyzeYearGaps(yearRanges: any[]) {
        let startingYears: number[] = [];
        let endingYears: (number | null)[] = [];
        let timePeriods: (number | null)[] = [];
    
        for (let y of yearRanges) {
            startingYears.push(y.start);
            endingYears.push(y.end);
        }
    
        let matchedEndingYears: (number | null)[] = [];
        let unmatchedEndingYears: (number | null)[] = [];
        for (let e of endingYears) {
            const found = startingYears.find((s) => s == e);
            if (found) {
                matchedEndingYears.push(found);
            } else if (!found) {
                unmatchedEndingYears.push(e);
            }
        }
    
        if (unmatchedEndingYears.length > 0) {
            let start: number;
            for (let e of unmatchedEndingYears) {
                let lesser: number[] = [];
                if (e == null) {
                    if (startingYears.length > 1) {
                        start = Math.min(...startingYears);
                    } else {
                        start = startingYears[0];
                    }
                } else if (e != null) {
                    lesser = startingYears.filter((s) => s < e);
                    start = Math.max(...lesser);
                }
    
                timePeriods.push({ start: start, end: e });
            }
        } else if (unmatchedEndingYears.length == 0) {
            let start: number = Math.min(...startingYears);
            let end: number | null;
            if (endingYears.includes(null)) {
                end = null;
            } else {
                end = Math.max(...endingYears);
            }
            timePeriods.push({ start: start, end: end });
        }
        console.log(timePeriods);
        return timePeriods;
    }

javascript arrays typescript

Answer 1

Answer №1

Breaking down your code into smaller functions would enhance readability and facilitate debugging.

UPDATE with reduce Method O(N)

Upon reviewing @yogi's feedback, a more elegant solution involves sorting the array initially with complexity O(N).

function mergeRange(ranges) {
    ranges.sort((r1,r2)=> r1.start-r2.start);
    return ranges.reduce((result, current) => {
        if (result.length === 0) return [current];
        const lastRange = result[result.length - 1];
        if (lastRange.end === NOW || lastRange.end >= current.start) {
            lastRange.end = (lastRange.end === NOW || current.end === NOW) ? NOW : Math.max(lastRange.end, current.end)
        } else {
            result.push(current);
        }
        return result;
    }, []);
}

ORIGINAL APPROACH O(N2)

This method outlines building the result list by sequentially adding range:

If the range does not overlap with any other range in the result list, it's added without merging
If the range overlaps with one or multiple ranges from the results list, they are merged

const indexRanges = [{start: 2002, end: 2004}, {start: 2003, end: 2006},{start: 2007, end: 2008}, {start: 2008, end: null}]
const NOW = null;

console.log(mergeRange(indexRanges));

function mergeRange(ranges) {
  let resultRangeList = [];
  for (let range of ranges) {
    // Ranges from resultRangeList that do not overlap with current range
    const nonOverlappingRanges = [];
    // Initialized mergedRange to current range
    let mergedRange = range;
    resultRangeList.forEach((existingRange) => {
        if (hasOverlap(existingRange, mergedRange)) {
            // If merged range overlaps with an existing range, merge them and update mergedRange
            mergedRange = getMergedRange(existingRange, mergedRange);
        } else {
            // Otherwise, add existing range to non-overlapping ranges
            nonOverlappingRanges.push(existingRange);
        }
    })
    // Update result list with non-overlapping ranges and new merged range
    resultRangeList = [...nonOverlappingRanges, mergedRange];
  }
  // Return sorted result list from earliest to oldest dates
  return resultRangeList.sort((r1, r2) => r1.start - r2.start);
}

// Determine merged range when given two overlapping ranges
function getMergedRange(range1, range2) {
    const start = Math.min(range1.start, range2.start);
    const end = (range1.end === NOW || range2.end === NOW) ? NOW : Math.max(range1.end, range2.end);
    return {start, end};
}

// Check if two ranges overlap
function hasOverlap(range1, range2) {
    return isWithinRange(range1, range2.start) || isWithinRange(range1, range2.end);
}

// Verify if a year falls within a specific range
function isWithinRange(range, aYear) {
    const start = num(range.start);
    const end = num(range.end);
    const year = num(aYear);
    return start <= year && year <= end;
}

// Convenience function to convert all years to numbers easily (especially for cases where end year is null)
function num(year) {
    return year === NOW ? Number.MAX_VALUE : year;
}

Answer 2

Breaking down your code into smaller functions would enhance readability and facilitate debugging.

UPDATE with reduce Method O(N)

Upon reviewing @yogi's feedback, a more elegant solution involves sorting the array initially with complexity O(N).

function mergeRange(ranges) {
    ranges.sort((r1,r2)=> r1.start-r2.start);
    return ranges.reduce((result, current) => {
        if (result.length === 0) return [current];
        const lastRange = result[result.length - 1];
        if (lastRange.end === NOW || lastRange.end >= current.start) {
            lastRange.end = (lastRange.end === NOW || current.end === NOW) ? NOW : Math.max(lastRange.end, current.end)
        } else {
            result.push(current);
        }
        return result;
    }, []);
}

ORIGINAL APPROACH O(N2)

This method outlines building the result list by sequentially adding range:

If the range does not overlap with any other range in the result list, it's added without merging
If the range overlaps with one or multiple ranges from the results list, they are merged

const indexRanges = [{start: 2002, end: 2004}, {start: 2003, end: 2006},{start: 2007, end: 2008}, {start: 2008, end: null}]
const NOW = null;

console.log(mergeRange(indexRanges));

function mergeRange(ranges) {
  let resultRangeList = [];
  for (let range of ranges) {
    // Ranges from resultRangeList that do not overlap with current range
    const nonOverlappingRanges = [];
    // Initialized mergedRange to current range
    let mergedRange = range;
    resultRangeList.forEach((existingRange) => {
        if (hasOverlap(existingRange, mergedRange)) {
            // If merged range overlaps with an existing range, merge them and update mergedRange
            mergedRange = getMergedRange(existingRange, mergedRange);
        } else {
            // Otherwise, add existing range to non-overlapping ranges
            nonOverlappingRanges.push(existingRange);
        }
    })
    // Update result list with non-overlapping ranges and new merged range
    resultRangeList = [...nonOverlappingRanges, mergedRange];
  }
  // Return sorted result list from earliest to oldest dates
  return resultRangeList.sort((r1, r2) => r1.start - r2.start);
}

// Determine merged range when given two overlapping ranges
function getMergedRange(range1, range2) {
    const start = Math.min(range1.start, range2.start);
    const end = (range1.end === NOW || range2.end === NOW) ? NOW : Math.max(range1.end, range2.end);
    return {start, end};
}

// Check if two ranges overlap
function hasOverlap(range1, range2) {
    return isWithinRange(range1, range2.start) || isWithinRange(range1, range2.end);
}

// Verify if a year falls within a specific range
function isWithinRange(range, aYear) {
    const start = num(range.start);
    const end = num(range.end);
    const year = num(aYear);
    return start <= year && year <= end;
}

// Convenience function to convert all years to numbers easily (especially for cases where end year is null)
function num(year) {
    return year === NOW ? Number.MAX_VALUE : year;
}

Identify any missing periods and combine the years into a single range

Answer №1

UPDATE with reduce Method O(N)

ORIGINAL APPROACH O(N2)

Similar questions

Sort an array according to the positions specified in another array

How can you prevent an element from overflowing when employing window.pageYOffset and using a switch case to alter the background color at specified pixel thresholds?

When transitioning between views in Angular App, it freezes due to the large data response from an HTTP request

Check to see if a guest has shown support or followed an outside party

Ways to determine if an HTML element contains a child element that is a hyperlink

The resource was treated as an image but sent with the MIME type application/octet-stream

Is there a way to assign a role to a user without requiring them to send a message beforehand?

Steps to reset default behavior after using event.preventDefault()

Display JSON information in a table using AngularJS

What could be causing the error in Angular 2 when using multiple conditions with ng-if?

jQuery UI Error: e.widget.extend cannot be used as a function

There was an issue with the NextJS axios request as it returned a status code

Applying a consistent script with varying inputs on the same HTML page

Creating an Array in AngularJS with ng-model and submitting it with jQuery: A comprehensive guide

Angular.js model that is updated by checkboxes

What are the Functions of Ctrl-K on Stack Overflow?

AngularJS bracket-enhanced template

Position the center of an Angular Material icon in the center

What are the steps to implement the jQuery slide menu effect on a website?

Error: Next.js is throwing a SyntaxError due to encountering an unexpected token 'export'