Katkat
Back

Solve array duplicates and two-type subarray

AmazonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently detect duplicates using hashing and to apply the sliding window technique to find subarrays that meet specific frequency constraints.

Part 1: Duplicate Detection

Given an array of integers nums, return true if any value appears at least twice in the array, and false if every element is distinct.

Part 2: Longest Subarray with Two Distinct Values

Given an integer array nums, return the length of the longest subarray that contains exactly two distinct values. If no such subarray exists, return 0.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1 (Duplicates): Input: nums = [1, 2, 3, 1] Output: true

Example 2 (Two-Type Subarray): Input: nums = [1, 2, 1, 3, 3, 3] Output: 4 Explanation: The longest subarray with exactly two distinct values is [1, 2, 1] (length 3) or [3, 3, 3] (wait, that is one type). Actually, [1, 2, 1] has two types, and [2, 1] has two types. A better example: [1, 2, 1, 2] has two distinct values and length 4.

Function Signatures

def contains_duplicate(nums: list[int]) -> bool:
    pass

def longest_subarray_with_two_types(nums: list[int]) -> int:
    pass

Hints

Hint 1

For duplicate detection, consider using a hash set to keep track of seen elements as you iterate through the array.

Hint 2

For the two-type subarray problem, maintain a sliding window with a hash map to count the frequencies of the distinct elements currently in the window.

Hint 3

When the hash map size exceeds two, shrink the window from the left until the map size returns to two.

Follow-up questions

  • How would your approach for duplicate detection change if you were required to use O(1) extra space and could modify the input array?
  • How does the time complexity change if you need to find a subarray with *at most* K distinct values instead of exactly two?
  • What if the input array is sorted? Can you optimize the two-type subarray problem to run in O(n) time with O(1) space?