Frontend School

Longest Subarray with At Most K Distinct Hotels

DSA
medium

Longest Subarray with At Most K Distinct Hotels

Medium
Sliding Window
Hash Map
Arrays

Overview

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.

What you need to do / Task

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.

Input & output

  • Input:
    • 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.
  • Output:
    • An integer (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).

Clarifications

  • The 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).
  • All hotel IDs are non-negative integers.
  • A contiguous subarray means elements must be adjacent in the original array.

Examples

1

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.

2

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.

3

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.

4

Example 4

Input:

hotelIds = [], k = 2

Output:

0

Note:

An empty array contains no bookings, so the length of the longest subarray is 0.

5

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

Constraints & assumptions

  • 0 <= hotelIds.length <= 10^5
  • 0 <= hotelIds[i] <= 10^9
  • 0 <= k <= hotelIds.length
  • Time complexity: O(N), where N is the length of hotelIds.
  • Space complexity: O(K) in the worst case, as the hash map will store at most K distinct elements (or O(N) if K is very large and all elements are distinct).

Out of scope

  • Handling invalid input types (e.g., hotelIds not an array, k not an integer). Assume valid inputs as per constraints.
  • Optimizing for extremely large distinct hotel IDs beyond 10^9 that might cause hash collisions in specific language implementations (standard integers and hash maps are fine).

What interviewers evaluate

  • Correctness of the sliding window logic, especially handling window expansion and contraction.
  • Efficient use of a frequency map (e.g., Map in JS/TS) to track distinct elements within the current window.
  • Ability to handle edge cases like empty arrays, k=0, or k being larger than the total distinct elements.
  • Clear, readable, and well-structured code.

Loading editor...