Flights with a precise mix

HardArraysHash mapsSliding window

A long tasting counter holds cups in a fixed order, with each cup labeled by its blend ID. A flight takes a nonempty contiguous section of the counter. A flight qualifies when it contains exactly kinds distinct blend IDs and between minCups and maxCups cups, inclusive. Repeated cups of a blend contribute to the length but count as only one distinct blend. Count all qualifying flights. Different start or end positions describe different flights, even if the blend sequences match. Return the count without rearranging the cups.

Example 1

INPUT[1,2,1,3], 2, 2, 3OUTPUT4

The qualifying inclusive index ranges are [0, 1], [1, 2], [2, 3], and [0, 2]. The other length-3 flight has three blends.

Example 2

INPUT[7,7,7], 1, 2, 3OUTPUT3

Both length-2 flights and the length-3 flight have exactly one distinct blend. Single cups are too short.

Keep in mind

1 <= blends.length <= 20,000
Each blend ID is an integer from 0 to 1,000,000.
1 <= kinds <= blends.length
1 <= minCups <= maxCups <= blends.length
The result fits exactly in a JavaScript Number.

Hint

Count flights with at most kinds blends, then subtract those with at most kinds - 1. For a fixed right endpoint, intersect the valid starting positions with those allowed by the two length limits.

/** @param {number[]} blends
 *  @param {number} kinds
 *  @param {number} minCups
 *  @param {number} maxCups
 *  @returns {number} */
function solve(blends, kinds, minCups, maxCups) {
  // Count flights satisfying both the blend and length rules.
}

/** @param {number[]} blends
 *  @param {number} kinds
 *  @param {number} minCups
 *  @param {number} maxCups
 *  @returns {number} */
function solve(blends, kinds, minCups, maxCups) {
  // Count flights satisfying both the blend and length rules.
}

INPUT[1,2,1,3], 2, 2, 3

EXPECTED OUTPUT4

Public samples only. These checks do not award ranked points.

Flights with a precise mix — JavaScript coding practice · HackerBrewery