Find gaps and consolidate year ranges

hoker7 0
Viewed 21

I am trying to reformat year ranges where there are gaps and consolidate year ranges. E.G. [{start: 2002, end: 2020}, {start: 2020, end: null}] to {start: 2002, end: null} E.G. [{2002, 2004},{2006, 2008}, {2008, null}] to [{2002-2004}, {2006-null}]

Relates to politician's party memberships through an API, difficulties where they change parties or rejoin parties.

interface yearRange{
    start: number
    end: number
}

function checkYearGaps(yearRanges: any[]) {
        let startYears: number[] = [];
        let endYears: (number | null)[] = [];
        let period: (number | null)[] = [];
    
        for (let y of yearRanges) {
            startYears.push(y.start);
            endYears.push(y.end);
        }
    
        let matchedEndYears: (number | null)[] = [];
        let unmatchedEndYears: (number | null)[] = [];
        for (let e of endYears) {
            const found = startYears.find((s) => s == e);
            if (found) {
                matchedEndYears.push(found);
            } else if (!found) {
                unmatchedEndYears.push(e);
            }
        }
    
        if (unmatchedEndYears.length > 0) {
            let start: number;
            for (let e of unmatchedEndYears) {
                let lesser: number[] = [];
                if (e == null) {
                    if (startYears.length > 1) {
                        start = Math.min(...startYears);
                    } else {
                        start = startYears[0];
                    }
                } else if (e != null) {
                    lesser = startYears.filter((s) => s < e);
                    start = Math.max(...lesser);
                }
    
                period.push({ start: start, end: e });
            }
        } else if (unmatchedEndYears.length == 0) {
            let start: number = Math.min(...startYears);
            let end: number | null;
            if (endYears.includes(null)) {
                end = null;
            } else {
                end = Math.max(...endYears);
            }
            period.push({ start: start, end: end });
        }
        console.log(period);
        return period;
    }
arrays typescript javascript
1 Answers

I would suggest you to split your code in smaller functions so that it makes it easier to read/debug.

EDIT using reduce O(N)

After seeing @yogi's comment there is a much more elegant solution by sorting the array first 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;
    }, []);
}

INITIAL SOLUTION O(N2)

Here is an approach to build the result list by adding range one by one:

  • if the range overlaps no other ranges from the result list, we just add it to the result list
  • if the range overlaps one or multiple ranges in the result list, we merge them
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 don't overlap with current range
    const nonOverlappingRanges = [];
    // mergedRange that we initialize to range
    let mergedRange = range;
    resultRangeList.forEach((existingRange) => {
        if (hasOverlap(existingRange, mergedRange)) {
            // if the merged range overlaps with an existing range, we merge them and update mergedRange
            mergedRange = getMergedRange(existingRange, mergedRange);
        } else {
            // else with add the existin range to the non overlapping ranges
            nonOverlappingRanges.push(existingRange);
        }
    })
    // we update the result list with non overlapping ranges and the new merged range
    resultRangeList = [...nonOverlappingRanges, mergedRange];
  }
  // we return the result sorted from earliest to oldest dates
  return resultRangeList.sort((r1, r2) => r1.start - r2.start);
}

// Given 2 ranges that overlap, it returns the merged range
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 2 ranges overlap
function hasOverlap(range1, range2) {
    return isWithinRange(range1, range2.start) || isWithinRange(range1, range2.end);
}

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

// utils to easily convert all years into number (notably because end year can be null)
function num(year) {
    return year === NOW ? Number.MAX_VALUE : year;
}
user32523270
Related