Katkat
Back

Find Kth Unique Maximum

SoFiSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently manage deduplication and order-statistics using hash maps or sorting techniques while handling multiple input collections.

Problem Statement

Given two integer arrays nums1 and nums2, find the k-th largest unique element present in the combined collection. A unique element is defined as an integer that appears exactly once in the total combined dataset (considering both arrays).

If there are fewer than k unique elements in the combined data, return -1.

Function Signature

def kth_unique_maximum(nums1: List[int], nums2: List[int], k: int) -> int

Examples

Example 1:

  • nums1 = [3, 2, 1, 3], nums2 = [4, 1, 5]
  • Combined: [3, 2, 1, 3, 4, 1, 5]
  • Frequencies: {3: 2, 2: 1, 1: 2, 4: 1, 5: 1}
  • Unique elements: [2, 4, 5]
  • Sorted unique elements: [5, 4, 2]
  • If k = 2, return 4.

Example 2:

  • nums1 = [1, 1], nums2 = [2, 2], k = 1
  • Unique elements: []
  • Return -1.

Constraints

  • nums1.length, nums2.length <= 10^5
  • Element values are between -10^6 and 10^6
  • 1 <= k <= 10^5

Hints

Hint 1

Consider using a hash map to count the occurrences of every number across both input arrays.

Hint 2

Filter the hash map to keep only those keys that have a frequency count of exactly one.

Hint 3

After collecting all unique elements, you can either sort them in descending order or use a min-heap to find the k-th largest value.

Follow-up questions

  • How would your approach change if the input arrays were so large they could not fit into memory?
  • If the frequency of elements was not needed, but we only cared about the existence of duplicates, could you solve this using less space?
  • How would you optimize the search for the k-th largest element if we already had a sorted list of all unique elements?