Longest Subarray with At Most K Distinct Hotels
Oyo analyzes customer booking histories to understand preferences and offer personalized recommendations. One key metric is identifying periods where a customer consistently books from a limited set of hotel types. This problem helps us find the longest such period in a customer's booking history.
Implement a function longestSubarrayWithAtMostKDistinct that takes an array of integers hotelIds (representing hotel IDs booked by a customer) and an integer k (the maximum number of distinct hotel IDs allowed). Your function should return the length of the longest contiguous subarray (sequence of bookings) where the number of unique hotel IDs is at most k.
hotelIds: An array of integers (number[] in TypeScript, number[] in JavaScript). Each integer represents a unique hotel ID.k: An integer (number) representing the maximum allowed number of distinct hotel IDs in the subarray.number) representing the length of the longest contiguous subarray meeting the criteria. Return 0 if no such subarray exists (e.g., hotelIds is empty or k is 0 and hotelIds is not empty).hotelIds array can be empty.k can be 0. If k is 0, the only valid subarray is an empty one, so the length should be 0 (unless the input hotelIds is also empty).Examples
Example 1
Input:
hotelIds = [1, 2, 1, 3, 2, 1], k = 2
Output:
3
Note:
The longest subarray with at most 2 distinct hotel IDs is [1, 2, 1] (indices 0-2), which has distinct IDs {1, 2} and a length of 3.
Example 2
Input:
hotelIds = [5, 5, 5, 5], k = 1
Output:
4
Note:
The entire array [5, 5, 5, 5] has only 1 distinct hotel ID (5), which is <= k. Its length is 4.
Example 3
Input:
hotelIds = [1, 2, 3, 4, 5], k = 3
Output:
3
Note:
Subarrays like [1, 2, 3], [2, 3, 4], or [3, 4, 5] all have 3 distinct IDs and a length of 3. This is the maximum possible length.
Example 4
Input:
hotelIds = [], k = 2
Output:
0
Note:
An empty array contains no bookings, so the length of the longest subarray is 0.
Example 5
Input:
hotelIds = [1, 2, 3], k = 0
Output:
0
Note:
With k=0, no subarray containing any distinct hotel ID is allowed. The only valid subarray is an empty one, so the length is 0.
Constraints
0 <= hotelIds.length <= 10^50 <= hotelIds[i] <= 10^90 <= k <= hotelIds.lengthhotelIds.hotelIds not an array, k not an integer). Assume valid inputs as per constraints.10^9 that might cause hash collisions in specific language implementations (standard integers and hash maps are fine).Map in JS/TS) to track distinct elements within the current window.k=0, or k being larger than the total distinct elements.Loading editor...