Dual Sorted Median - FAANG Problems | Repovive

FNG5. Dual Sorted Median

1s256 MB

This problem is based on an Apple interview problem described here.

Two sorted integer arrays are given. Print twice their combined median.

For an odd total length, print 2 * median.

\begin{array}{l} n \quad m \\ a_1 \quad \cdots \quad a_n \\ b_1 \quad \cdots \quad b_m \end{array}

$\text{one integer: twice the combined median}$

Input

2 1
1 3
2

Explanation

\begin{array}{l} \\ \text{1. Determine Combined Array Composition:} \\ \quad \bullet \text{ Input Array } A = [1, \; 3], \quad B = [2] \\ \quad \bullet \text{ Combined Sorted State } = [1, \; 2, \; 3] \implies \text{Total Elements } (N + M) = \mathbf{3 \quad (\text{Odd})} \\ \\ \text{2. Median Extraction \& Scale Calculation:} \\ \quad \bullet \text{ Exact Middle Position Index } = \lfloor 3 / 2 \rfloor = 1 \\ \quad \bullet \text{ Median Element Value } = \mathbf{2} \\ \quad \bullet \text{ Twice the Median } = 2 \times 2 = \mathbf{4} \\ \\ \hline \text{\textbf{Output: }} \text{4} \end{array}

Output

Input

2 2
1 2
3 4

Explanation

\begin{array}{l} \\ \text{1. Determine Combined Array Composition:} \\ \quad \bullet \text{ Input Array } A = [1, \; 2], \quad B = [3, \; 4] \\ \quad \bullet \text{ Combined Sorted State } = [1, \; 2, \; 3, \; 4] \implies \text{Total Elements } (N + M) = \mathbf{4 \quad (\text{Even})} \\ \\ \text{2. Median Extraction \& Scale Calculation:} \\ \quad \bullet \text{ Left-Center Element Value (Index 1) } = \mathbf{2} \\ \quad \bullet \text{ Right-Center Element Value (Index 2) } = \mathbf{3} \\ \quad \bullet \text{ Standard Combined Median Value } = (2 + 3) / 2 = 2.5 \\ \quad \bullet \text{ Twice the Median } = 2 \times 2.5 = 2 + 3 = \mathbf{5} \\ \\ \hline \text{\textbf{Output: }} \text{5} \end{array}

Output

\begin{array}{l} n \quad m \\ a_1 \quad \cdots \quad a_n \\ b_1 \quad \cdots \quad b_m \end{array}

$\text{one integer: twice the combined median}$

\begin{array}{l} \\ \text{1. Determine Combined Array Composition:} \\ \quad \bullet \text{ Input Array } A = [1, \; 3], \quad B = [2] \\ \quad \bullet \text{ Combined Sorted State } = [1, \; 2, \; 3] \implies \text{Total Elements } (N + M) = \mathbf{3 \quad (\text{Odd})} \\ \\ \text{2. Median Extraction \& Scale Calculation:} \\ \quad \bullet \text{ Exact Middle Position Index } = \lfloor 3 / 2 \rfloor = 1 \\ \quad \bullet \text{ Median Element Value } = \mathbf{2} \\ \quad \bullet \text{ Twice the Median } = 2 \times 2 = \mathbf{4} \\ \\ \hline \text{\textbf{Output: }} \text{4} \end{array}

\begin{array}{l} \\ \text{1. Determine Combined Array Composition:} \\ \quad \bullet \text{ Input Array } A = [1, \; 2], \quad B = [3, \; 4] \\ \quad \bullet \text{ Combined Sorted State } = [1, \; 2, \; 3, \; 4] \implies \text{Total Elements } (N + M) = \mathbf{4 \quad (\text{Even})} \\ \\ \text{2. Median Extraction \& Scale Calculation:} \\ \quad \bullet \text{ Left-Center Element Value (Index 1) } = \mathbf{2} \\ \quad \bullet \text{ Right-Center Element Value (Index 2) } = \mathbf{3} \\ \quad \bullet \text{ Standard Combined Median Value } = (2 + 3) / 2 = 2.5 \\ \quad \bullet \text{ Twice the Median } = 2 \times 2.5 = 2 + 3 = \mathbf{5} \\ \\ \hline \text{\textbf{Output: }} \text{5} \end{array}