Median of Two Sorted Arrays

▶

Steps

setup

Ensure nums1 is smaller array

Check if nums1 is larger than nums2. If so, swap them to minimize binary search range.

💡 Binary search is performed on the smaller array to optimize performance.

Line:

if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1

💡 Ensures binary search is done on the smaller array for efficiency.

setup

Initialize binary search boundaries

Set low and high pointers for binary search on nums1 indices from 0 to length of nums1.

💡 Binary search boundaries define the search space for partition index i.

Line:

m, n = len(nums1), len(nums2)
low, high = 0, m
half_len = (m + n + 1) // 2

💡 Initial boundaries cover all possible partition indices in nums1.

compare

Calculate partition indices i and j

Calculate i as midpoint of low and high, and j as half_len - i to partition nums1 and nums2.

💡 Partition indices split arrays into left and right halves for median calculation.

Line:

i = (low + high) // 2
j = half_len - i

💡 Partitions are complementary to cover half the total elements.

compare

Determine max_left and min_right for nums1

Find max_left_nums1 as nums1[i-1] and min_right_nums1 as nums1[i], handling edge cases.

💡 These values define the boundary elements around the partition in nums1.

Line:

max_left_nums1 = nums1[i - 1] if i != 0 else float('-inf')
min_right_nums1 = nums1[i] if i != m else float('inf')

💡 Edge cases use infinities to simplify comparisons.

compare

Determine max_left and min_right for nums2

Find max_left_nums2 as nums2[j-1] and min_right_nums2 as nums2[j], handling edge cases.

💡 These values define the boundary elements around the partition in nums2.

Line:

max_left_nums2 = nums2[j - 1] if j != 0 else float('-inf')
min_right_nums2 = nums2[j] if j != n else float('inf')

💡 Edge cases use infinities to simplify comparisons.

compare

Check if partition is valid

Check if max_left_nums1 ≤ min_right_nums2 and max_left_nums2 ≤ min_right_nums1 to validate partition.

💡 Valid partition means left halves contain smaller elements than right halves.

Line:

if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1:

💡 Correct partition found to compute median.

reconstruct

Compute median for odd total length

Since total length is odd, median is max(max_left_nums1, max_left_nums2).

💡 Median is the middle element of merged sorted array.

Line:

if (m + n) % 2 == 1:
    return float(max(max_left_nums1, max_left_nums2))

💡 Median is 2.0, the maximum of left partition elements.

reconstruct

Return median result

Return the computed median value 2.0 as the final answer.

💡 The algorithm terminates with the correct median.

Line:

return 2.0

💡 Median successfully found using binary search partition.

reconstruct

Final state with answer

Final visualization state showing the answer 2.0 and no active pointers.

💡 This final state confirms the median found.

💡 The algorithm completed successfully.

compare

Confirm no further binary search needed

Since partition is valid and median found, no further binary search iterations are needed.

💡 This step clarifies the binary search loop termination condition.

Line:

while low <= high:
    ...
    if partition valid:
        return median
    else adjust low/high

💡 Understanding loop termination is key to grasping algorithm efficiency.

def findMedianSortedArrays(nums1, nums2):  # STEP 1
    if len(nums1) > len(nums2):  # STEP 1
        nums1, nums2 = nums2, nums1  # STEP 1
    m, n = len(nums1), len(nums2)  # STEP 2
    low, high = 0, m  # STEP 2
    half_len = (m + n + 1) // 2  # STEP 2
    while low <= high:  # STEP 3
        i = (low + high) // 2  # STEP 3
        j = half_len - i  # STEP 3
        max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1]  # STEP 4
        min_right_nums1 = float('inf') if i == m else nums1[i]  # STEP 4
        max_left_nums2 = float('-inf') if j == 0 else nums2[j - 1]  # STEP 5
        min_right_nums2 = float('inf') if j == n else nums2[j]  # STEP 5
        if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1:  # STEP 6
            if (m + n) % 2 == 1:  # STEP 7
                return float(max(max_left_nums1, max_left_nums2))  # STEP 7
            else:  # STEP 7
                return (max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2.0  # STEP 7
        elif max_left_nums1 > min_right_nums2:  # STEP 6
            high = i - 1  # STEP 6
        else:  # STEP 6
            low = i + 1  # STEP 6

📊

Median of Two Sorted Arrays - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and comparison reveals how the algorithm efficiently finds the median without merging arrays.

setup

1

0

3

1

setup

low

1

0

3

1

compare

low

1

0

i

3

1

compare

1

0

i

3

1

compare

2

0

compare

1

0

j

3

1

record

1

0

j

3

1

Result: 2

record

1

0

3

1

Result: 2

record

1

0

3

1

Result: 2

compare

1

0

3

1

Result: 2

Key Takeaways

✓ Binary search on the smaller array efficiently finds the correct partition for median calculation.

This insight is hard to see from code alone because the partition logic is subtle and involves complementary indices.

✓ Using infinities for edge cases simplifies boundary comparisons without extra conditionals.

Visualizing these sentinel values clarifies how the algorithm handles partitions at array ends.

✓ The median is computed directly from partition boundary elements without merging arrays.

Seeing the partition elements highlighted helps understand how the median relates to these values.

Practice

1. You are given a string of digits and a target integer. You need to insert binary operators (+, -, *) between the digits to form expressions that evaluate to the target. Which algorithmic approach guarantees finding all valid expressions?

easy

A. Backtracking with enumeration of all possible operator insertions and operand splits

B. Greedy algorithm that inserts operators based on local evaluation to reach the target quickly

C. Dynamic programming that stores intermediate results for sub-expressions without operator insertion

D. Divide and conquer by splitting the string into halves and solving independently

Solution

1. Step 1: Understand problem requirements

   The problem requires generating all valid expressions by inserting operators between digits to match a target value, which demands exploring all combinations.

2. Step 2: Identify suitable algorithm

   Backtracking with enumeration systematically tries all splits and operator insertions, guaranteeing all solutions are found. Greedy or divide and conquer approaches fail to explore all combinations, and DP without operator insertion does not apply.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking enumerates all expressions [OK]

Hint: All expressions require exploring all splits and operators [OK]

Common Mistakes:

• Thinking greedy can find all expressions
• Assuming DP without operator insertion suffices

2. Given a list of unique words, you need to find all pairs of distinct indices (i, j) such that the concatenation of words[i] + words[j] forms a palindrome. Which approach guarantees an optimal solution in terms of time complexity for large inputs?

easy

A. Brute force nested loops checking all pairs and verifying palindrome by concatenation

B. Building a Trie of reversed words and tracking palindrome suffixes to find pairs efficiently

C. Dynamic programming to find palindromic substrings and then pairing indices accordingly

D. Greedy approach by sorting words and pairing those with matching prefixes and suffixes

Solution

1. Step 1: Understand brute force limitations

   Brute force checks all pairs, resulting in O(n^2 * k) time, which is inefficient for large n.

2. Step 2: Recognize Trie-based optimization

   Building a Trie of reversed words allows prefix matching and palindrome suffix tracking, reducing redundant checks and achieving O(n * k^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie-based approach is known optimal for palindrome pairs [OK]

Hint: Trie with palindrome suffixes optimizes palindrome pair search [OK]

Common Mistakes:

• Assuming brute force is acceptable for large inputs
• Confusing palindrome substring DP with pair finding
• Believing greedy prefix-suffix matching suffices

3. You are given an array representing the elevation map where the width of each bar is 1. You need to find how much water can be trapped after raining. Which approach guarantees an optimal solution with linear time and constant space complexity?

easy

A. Use nested loops to find the maximum height to the left and right of each bar and calculate trapped water accordingly.

B. Use two pointers starting from both ends, moving inward, updating left_max and right_max, and accumulating trapped water based on comparisons.

C. Use dynamic programming with a 2D table storing water trapped between every pair of bars.

D. Use a greedy approach that always traps water at the current lowest bar without considering future bars.

Solution

1. Step 1: Understand problem constraints

   The problem requires calculating trapped water efficiently with minimal space.

2. Step 2: Evaluate approaches

   Nested loops (brute force) are O(n²), DP with 2D table is inefficient, greedy fails on complex cases. The two-pointer approach uses O(n) time and O(1) space by moving pointers inward and updating max heights.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer approach is known optimal for trapping rain water [OK]

Hint: Two pointers with max updates -> optimal O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing greedy with two-pointer approach
• Assuming DP with 2D table is needed
• Believing brute force is acceptable for large inputs

4. Examine the following buggy code snippet for the optimized trie approach. Which line contains the subtle bug that can cause incorrect results or runtime errors when no elements in nums are less than or equal to m in a query?

class TrieNode:
    def __init__(self):
        self.children = [null, null]

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def maxXor(self, num):
        node = self.root
        # Bug: missing check for empty trie
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if node.children[toggled_bit]:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children[bit]
        return max_xor

# rest of code omitted for brevity

medium

A. Line missing check if trie is empty before traversal in maxXor

B. Line 'if not node.children[bit]: node.children[bit] = TrieNode()' in insert method

C. Line with 'node = self.root' in maxXor method

D. Line 'node = node.children[bit]' in else branch of maxXor

Solution

1. Step 1: Identify missing empty trie check

   maxXor should return -1 if trie is empty (no children at root), but this check is missing.

2. Step 2: Consequence of missing check

   Without this, traversal accesses null children causing runtime error or incorrect results when no nums ≤ m.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding 'if not node.children[0] and not node.children[1]: return -1' fixes bug [OK]

Hint: Always check if trie is empty before querying [OK]

Common Mistakes:

• Forgetting empty trie check
• Incorrect bit indexing
• Misplaced node updates

5. Suppose the problem is modified so that nodes can be revisited multiple times without penalty, but the goal remains to visit all nodes at least once with the shortest path length. Which modification to the bidirectional BFS with state compression algorithm is necessary to handle this variant correctly?

hard

A. Remove the visited bitmask and track only the current node in BFS states

B. Modify the bitmask to track the count of visits per node instead of a binary visited flag

C. Use a simple BFS without bitmask since revisits are allowed and shortest path is trivial

D. Keep the visited bitmask but allow revisiting states with the same mask and node multiple times

Solution

1. Step 1: Understand problem change

   Allowing multiple revisits without penalty means the visited state must track how many times each node is visited if that affects path validity.

2. Step 2: Modify state representation

   Binary bitmask is insufficient; need to track counts per node, e.g., using a vector or multi-bit encoding per node, to correctly represent states and avoid incorrect pruning.

3. Step 3: Implication on BFS

   State space grows, but correctness requires this richer state representation to find shortest path under new rules.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting visits per node is necessary when revisits are allowed without penalty [OK]

Hint: Bitmask alone can't track multiple visits; need counts per node [OK]

Common Mistakes:

• Removing bitmask entirely loses track of visited nodes
• Allowing revisits without state changes causes incorrect pruning
• Assuming simple BFS suffices without state tracking