Katkat
Back

Find median of merged RLE arrays

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to find the median of two sorted, run-length encoded arrays without fully decompressing them, focusing on efficiency and pointer manipulation.

Problem Statement

Run-Length Encoding (RLE) is a data compression technique where consecutive identical elements are stored as a sequence of (value, frequency) pairs. You are given two RLE-encoded arrays, arr1 and arr2, representing two sorted integer sequences.

Your task is to find the median of the combined (decomposed) sequences. Because the total number of elements could be massive, you must implement an algorithm that runs in sub-linear time relative to the total number of elements (ideally proportional to the number of RLE pairs).

Function Signature

def find_median_rle(arr1: list[tuple[int, int]], arr2: list[tuple[int, int]]) -> float:

Constraints

  • Each arr is sorted by the value of the elements.
  • value is an integer, frequency is a positive integer.
  • Total number of elements in each array can be up to 10^12, but the number of RLE pairs is at most 10^5.

Examples

Example 1:

  • arr1 = [(1, 2), (3, 2)] (Decomposed: [1, 1, 3, 3])
  • arr2 = [(2, 1), (4, 1)] (Decomposed: [2, 4])
  • Combined: [1, 1, 2, 3, 3, 4], Median: (2 + 3) / 2 = 2.5

Example 2:

  • arr1 = [(1, 3)] (Decomposed: [1, 1, 1])
  • arr2 = [(2, 2)] (Decomposed: [2, 2])
  • Combined: [1, 1, 1, 2, 2], Median: 1.0

Edge Cases

  • Arrays of different lengths.
  • One array being empty.
  • Cases where the median lands exactly between two different RLE blocks.

Hints

Hint 1

Instead of decompressing, calculate the total length `N` of the combined sequences to identify the target index (or indices) of the median.

Hint 2

Use two pointers to traverse the RLE pairs simultaneously, effectively 'simulating' the merge of two sorted lists without expanding the counts.

Hint 3

Keep track of the cumulative count of elements processed so far to determine exactly which RLE pair contains the median index.

Follow-up questions

  • How would you modify your solution if the input arrays were not sorted by value, but you needed to find the median of the multiset of all values?
  • What is the time and space complexity of your approach in terms of the number of RLE pairs `M` and `N`?
  • If one of the arrays is significantly smaller than the other, can you optimize the search further using binary search on the RLE blocks?