Median of Two Sorted Arrays

🎯

Median of Two Sorted Arrays

hardMIXEDAmazonGoogleFacebook

Imagine merging two sorted lists of customer transaction amounts from two different branches to find the median transaction value across both branches combined.

💡 This problem is about finding the median of two sorted arrays without merging them fully. Beginners often struggle because the naive approach is inefficient, and the optimal solution requires understanding binary search on partitions rather than just values.

📋

Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Input: Two integer arrays nums1 and nums2 sorted in non-decreasing order. Output: A single float representing the median of the combined sorted array formed by merging nums1 and nums2.

1 ≤ m, n ≤ 10^5-10^6 ≤ nums1[i], nums2[i] ≤ 10^6nums1 and nums2 are sorted in non-decreasing order

💡

Example

Input"nums1 = [1, 3], nums2 = [2]"

Output2.0

Merged array is [1, 2, 3], median is 2

Input"nums1 = [1, 2], nums2 = [3, 4]"

Output2.5

Merged array is [1, 2, 3, 4], median is (2 + 3) / 2 = 2.5

• One array empty → median is median of the non-empty array
• Arrays of very different sizes → median still valid
• Arrays with duplicate elements → median accounts for duplicates
• Arrays with negative and positive numbers → median correctly computed

⚠️

Common Mistakes

Not swapping arrays to ensure binary search on smaller array

Binary search range becomes large, causing inefficiency or errors

✅ Always swap so that binary search is on the smaller array

Incorrect handling of edge partitions (i == 0 or i == m)

Index out of bounds or wrong median calculation

✅ Use sentinel values like -∞ and +∞ for out-of-bound partition edges

Confusing median calculation for odd and even combined lengths

Wrong median returned, failing test cases

✅ Check parity of total length and compute median accordingly

Trying to merge fully in optimal approach

Loses logarithmic time advantage, leading to TLE

✅ Use binary search partition without merging arrays

Off-by-one errors in partition indices

Incorrect partitioning causing invalid median

✅ Carefully calculate partition indices and test with examples

🧠

Brute Force (Merge and Find Median)

💡 This approach exists to build intuition by directly merging arrays and then finding the median. It is simple but inefficient for large inputs, highlighting the need for better methods.

Intuition

Merge both sorted arrays into one sorted array and then find the median of the merged array.

Algorithm

1. Initialize two pointers for nums1 and nums2.
2. Iterate through both arrays, merging them into a new sorted array.
3. Once merged, find the median based on the total length (odd or even).
4. Return the median value.

💡 The main challenge is merging two arrays correctly and then handling median calculation for odd and even combined lengths.

</>

Code

def findMedianSortedArrays(nums1, nums2):
    merged = []
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    while i < len(nums1):
        merged.append(nums1[i])
        i += 1
    while j < len(nums2):
        merged.append(nums2[j])
        j += 1
    n = len(merged)
    if n % 2 == 1:
        return float(merged[n // 2])
    else:
        return (merged[n // 2 - 1] + merged[n // 2]) / 2.0

# Driver code
if __name__ == '__main__':
    print(findMedianSortedArrays([1,3], [2]))  # Output: 2.0
    print(findMedianSortedArrays([1,2], [3,4]))  # Output: 2.5

Line Notes

merged = []Initialize a new list to hold merged elements

while i < len(nums1) and j < len(nums2):Loop until one array is fully traversed

if nums1[i] < nums2[j]:Compare current elements to maintain sorted order

return float(merged[n // 2])Return median for odd length merged array

import java.util.*;
public class Solution {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];
        int total = m + n;
        if (total % 2 == 1) {
            return (double) merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1,3}, new int[]{2})); // 2.0
        System.out.println(findMedianSortedArrays(new int[]{1,2}, new int[]{3,4})); // 2.5
    }
}

Line Notes

int[] merged = new int[m + n];Create array to hold merged elements

while (i < m && j < n)Merge until one array is exhausted

if (nums1[i] < nums2[j])Pick smaller element to maintain order

return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;Calculate median for even length

#include <iostream>
#include <vector>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    vector<int> merged;
    int i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j]) {
            merged.push_back(nums1[i++]);
        } else {
            merged.push_back(nums2[j++]);
        }
    }
    while (i < nums1.size()) merged.push_back(nums1[i++]);
    while (j < nums2.size()) merged.push_back(nums2[j++]);
    int n = merged.size();
    if (n % 2 == 1) return (double)merged[n / 2];
    return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
}
int main() {
    vector<int> a1 = {1,3};
    vector<int> a2 = {2};
    cout << findMedianSortedArrays(a1, a2) << endl; // 2.0
    vector<int> b1 = {1,2};
    vector<int> b2 = {3,4};
    cout << findMedianSortedArrays(b1, b2) << endl; // 2.5
    return 0;
}

Line Notes

vector<int> merged;Use vector to store merged elements dynamically

while (i < nums1.size() && j < nums2.size())Merge arrays until one is exhausted

merged.push_back(nums1[i++]);Add smaller element and increment pointer

return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;Compute median for even length merged array

function findMedianSortedArrays(nums1, nums2) {
    let merged = [];
    let i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            merged.push(nums1[i++]);
        } else {
            merged.push(nums2[j++]);
        }
    }
    while (i < nums1.length) merged.push(nums1[i++]);
    while (j < nums2.length) merged.push(nums2[j++]);
    let n = merged.length;
    if (n % 2 === 1) return merged[Math.floor(n / 2)];
    return (merged[n / 2 - 1] + merged[n / 2]) / 2;
}

// Test cases
console.log(findMedianSortedArrays([1,3], [2])); // 2.0
console.log(findMedianSortedArrays([1,2], [3,4])); // 2.5

Line Notes

let merged = [];Initialize array to hold merged elements

while (i < nums1.length && j < nums2.length)Merge until one array is fully traversed

merged.push(nums1[i++]);Add smaller element and move pointer

return (merged[n / 2 - 1] + merged[n / 2]) / 2;Calculate median for even length merged array

⏱

Complexity

TimeO(m + n)

SpaceO(m + n)

We merge both arrays fully, which takes linear time and space proportional to the sum of their lengths.

💡 For arrays of size 100,000 each, this means 200,000 operations and storing 200,000 elements, which is inefficient.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays, motivating the need for a better solution.

🧠

Better Approach (Two Pointer Partial Merge)

💡 This approach improves efficiency by merging only up to the median point instead of the entire arrays, reducing unnecessary work.

Intuition

Since median depends only on the middle elements, merge just enough elements from both arrays to find the median without full merge.

Algorithm

1. Calculate the total length and the median index.
2. Use two pointers to iterate through nums1 and nums2.
3. Merge elements until reaching the median index.
4. Calculate and return the median based on merged elements so far.

💡 The key is to stop merging early, which requires careful pointer management and median calculation.

</>

Code

def findMedianSortedArrays(nums1, nums2):
    m, n = len(nums1), len(nums2)
    total = m + n
    i = j = 0
    prev = curr = 0
    for _ in range(total // 2 + 1):
        prev = curr
        if i < m and (j >= n or nums1[i] < nums2[j]):
            curr = nums1[i]
            i += 1
        else:
            curr = nums2[j]
            j += 1
    if total % 2 == 1:
        return float(curr)
    else:
        return (prev + curr) / 2.0

# Driver code
if __name__ == '__main__':
    print(findMedianSortedArrays([1,3], [2]))  # 2.0
    print(findMedianSortedArrays([1,2], [3,4]))  # 2.5

Line Notes

total = m + nCalculate combined length to find median position

for _ in range(total // 2 + 1):Iterate only up to median index

if i < m and (j >= n or nums1[i] < nums2[j]):Choose smaller element from nums1 or nums2

return (prev + curr) / 2.0Calculate median for even total length

public class Solution {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int i = 0, j = 0, prev = 0, curr = 0;
        for (int k = 0; k <= total / 2; k++) {
            prev = curr;
            if (i < m && (j >= n || nums1[i] < nums2[j])) {
                curr = nums1[i++];
            } else {
                curr = nums2[j++];
            }
        }
        if (total % 2 == 1) return (double) curr;
        return (prev + curr) / 2.0;
    }
    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1,3}, new int[]{2})); // 2.0
        System.out.println(findMedianSortedArrays(new int[]{1,2}, new int[]{3,4})); // 2.5
    }
}

Line Notes

int total = m + n;Calculate total length for median index

for (int k = 0; k <= total / 2; k++)Loop only until median position

if (i < m && (j >= n || nums1[i] < nums2[j]))Pick smaller element from nums1 or nums2

return (prev + curr) / 2.0;Return median for even combined length

#include <iostream>
#include <vector>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    int total = m + n;
    int i = 0, j = 0, prev = 0, curr = 0;
    for (int k = 0; k <= total / 2; k++) {
        prev = curr;
        if (i < m && (j >= n || nums1[i] < nums2[j])) {
            curr = nums1[i++];
        } else {
            curr = nums2[j++];
        }
    }
    if (total % 2 == 1) return (double)curr;
    return (prev + curr) / 2.0;
}
int main() {
    vector<int> a1 = {1,3};
    vector<int> a2 = {2};
    cout << findMedianSortedArrays(a1, a2) << endl; // 2.0
    vector<int> b1 = {1,2};
    vector<int> b2 = {3,4};
    cout << findMedianSortedArrays(b1, b2) << endl; // 2.5
    return 0;
}

Line Notes

int total = m + n;Calculate total length to find median index

for (int k = 0; k <= total / 2; k++)Iterate only up to median element

if (i < m && (j >= n || nums1[i] < nums2[j]))Choose smaller element from nums1 or nums2

return (prev + curr) / 2.0;Calculate median for even total length

function findMedianSortedArrays(nums1, nums2) {
    let m = nums1.length, n = nums2.length;
    let total = m + n;
    let i = 0, j = 0, prev = 0, curr = 0;
    for (let k = 0; k <= Math.floor(total / 2); k++) {
        prev = curr;
        if (i < m && (j >= n || nums1[i] < nums2[j])) {
            curr = nums1[i++];
        } else {
            curr = nums2[j++];
        }
    }
    if (total % 2 === 1) return curr;
    return (prev + curr) / 2;
}

console.log(findMedianSortedArrays([1,3], [2])); // 2.0
console.log(findMedianSortedArrays([1,2], [3,4])); // 2.5

Line Notes

let total = m + n;Calculate combined length for median index

for (let k = 0; k <= Math.floor(total / 2); k++)Loop only until median element is reached

if (i < m && (j >= n || nums1[i] < nums2[j]))Pick smaller element from nums1 or nums2

return (prev + curr) / 2;Return median for even total length

⏱

Complexity

TimeO(m + n) but only up to half the combined length

SpaceO(1)

We only merge elements until the median position, reducing work compared to full merge, and use constant extra space.

💡 For arrays of size 100,000 each, this means about 100,000 operations, which is better but still linear.

Interview Verdict: Accepted and more efficient than brute force but not optimal

This approach is a practical improvement but interviewers expect a logarithmic time solution.

🧠

Optimal Approach (Binary Search on Partition)

💡 This approach uses binary search to partition the arrays so that the left halves contain the median elements, achieving O(log(min(m,n))) time.

Intuition

Partition the two arrays such that all elements on the left are less than or equal to those on the right, then compute median from partition edges.

Algorithm

1. Ensure nums1 is the smaller array to minimize binary search range.
2. Set binary search boundaries on nums1 indices.
3. While searching, partition nums1 and nums2 such that left partitions have half the total elements.
4. Check if partition is valid: max left ≤ min right for both arrays.
5. If valid, compute median from max left and min right elements.
6. Else adjust binary search boundaries accordingly.

💡 The challenge is correctly defining partitions and handling edge cases when partitions are at array boundaries.

</>

Code

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

# Driver code
if __name__ == '__main__':
    print(findMedianSortedArrays([1,3], [2]))  # 2.0
    print(findMedianSortedArrays([1,2], [3,4]))  # 2.5

Line Notes

if len(nums1) > len(nums2):Ensure binary search is on smaller array for efficiency

half_len = (m + n + 1) // 2Calculate half length for partitioning

max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1]Handle edge case when partition is at start

if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1:Check if partition is valid

public class Solution {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length, n = nums2.length;
        int low = 0, high = m;
        int halfLen = (m + n + 1) / 2;
        while (low <= high) {
            int i = (low + high) / 2;
            int j = halfLen - i;
            int maxLeftNums1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int minRightNums1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int maxLeftNums2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int minRightNums2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
            if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1) {
                if ((m + n) % 2 == 1) {
                    return Math.max(maxLeftNums1, maxLeftNums2);
                } else {
                    return (Math.max(maxLeftNums1, maxLeftNums2) + Math.min(minRightNums1, minRightNums2)) / 2.0;
                }
            } else if (maxLeftNums1 > minRightNums2) {
                high = i - 1;
            } else {
                low = i + 1;
            }
        }
        throw new IllegalArgumentException("Input arrays are not sorted");
    }
    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1,3}, new int[]{2})); // 2.0
        System.out.println(findMedianSortedArrays(new int[]{1,2}, new int[]{3,4})); // 2.5
    }
}

Line Notes

if (nums1.length > nums2.length)Swap arrays to binary search smaller one

int halfLen = (m + n + 1) / 2;Calculate half length for partitioning

int maxLeftNums1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];Handle partition at start of nums1

if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1)Check if partition is valid

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
    int m = nums1.size(), n = nums2.size();
    int low = 0, high = m;
    int halfLen = (m + n + 1) / 2;
    while (low <= high) {
        int i = (low + high) / 2;
        int j = halfLen - i;
        int maxLeftNums1 = (i == 0) ? INT_MIN : nums1[i - 1];
        int minRightNums1 = (i == m) ? INT_MAX : nums1[i];
        int maxLeftNums2 = (j == 0) ? INT_MIN : nums2[j - 1];
        int minRightNums2 = (j == n) ? INT_MAX : nums2[j];
        if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1) {
            if ((m + n) % 2 == 1) return (double)max(maxLeftNums1, maxLeftNums2);
            return (max(maxLeftNums1, maxLeftNums2) + min(minRightNums1, minRightNums2)) / 2.0;
        } else if (maxLeftNums1 > minRightNums2) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }
    throw invalid_argument("Input arrays are not sorted");
}
int main() {
    vector<int> a1 = {1,3};
    vector<int> a2 = {2};
    cout << findMedianSortedArrays(a1, a2) << endl; // 2.0
    vector<int> b1 = {1,2};
    vector<int> b2 = {3,4};
    cout << findMedianSortedArrays(b1, b2) << endl; // 2.5
    return 0;
}

Line Notes

if (nums1.size() > nums2.size())Swap arrays to ensure binary search on smaller array

int halfLen = (m + n + 1) / 2;Calculate half length for partitioning

int maxLeftNums1 = (i == 0) ? INT_MIN : nums1[i - 1];Handle partition at start of nums1

if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1)Check if partition is valid

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    let m = nums1.length, n = nums2.length;
    let low = 0, high = m;
    let halfLen = Math.floor((m + n + 1) / 2);
    while (low <= high) {
        let i = Math.floor((low + high) / 2);
        let j = halfLen - i;
        let maxLeftNums1 = (i === 0) ? -Infinity : nums1[i - 1];
        let minRightNums1 = (i === m) ? Infinity : nums1[i];
        let maxLeftNums2 = (j === 0) ? -Infinity : nums2[j - 1];
        let minRightNums2 = (j === n) ? Infinity : nums2[j];
        if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1) {
            if ((m + n) % 2 === 1) {
                return Math.max(maxLeftNums1, maxLeftNums2);
            } else {
                return (Math.max(maxLeftNums1, maxLeftNums2) + Math.min(minRightNums1, minRightNums2)) / 2;
            }
        } else if (maxLeftNums1 > minRightNums2) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }
    throw new Error("Input arrays are not sorted");
}

console.log(findMedianSortedArrays([1,3], [2])); // 2.0
console.log(findMedianSortedArrays([1,2], [3,4])); // 2.5

Line Notes

if (nums1.length > nums2.length)Swap arrays to binary search smaller one

let halfLen = Math.floor((m + n + 1) / 2);Calculate half length for partitioning

let maxLeftNums1 = (i === 0) ? -Infinity : nums1[i - 1];Handle partition at start of nums1

if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1)Check if partition is valid

⏱

Complexity

TimeO(log(min(m, n)))

SpaceO(1)

Binary search is performed on the smaller array, reducing the search space logarithmically.

💡 For arrays of size 100,000, this means about 17 operations (log2 100,000), which is extremely efficient.

Interview Verdict: Accepted and optimal solution

This is the best approach to implement in interviews for this problem due to its efficiency and elegance.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the optimal binary search partition approach is expected; the others are useful for explanation and understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m + n)	O(m + n)	No	N/A	Mention only - never code
2. Partial Merge	O(m + n) up to median	O(1)	No	N/A	Good to mention as improvement
3. Binary Search Partition	O(log(min(m,n)))	O(1)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Discuss improvements and partial merge approach.Step 4: Introduce the optimal binary search partition approach.Step 5: Code the optimal solution carefully, explaining each step.Step 6: Test with edge cases and discuss complexity.

Time Allocation

Clarify: 3min → Approach discussion: 5min → Code optimal: 10min → Test & explain: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from naive to optimal, mastery of binary search in non-traditional contexts, and coding accuracy.

Common Follow-ups

• What if arrays are not sorted? → You must sort first or use a different approach.
• How to find the kth smallest element? → Similar binary search partition logic applies.

💡 These follow-ups test your ability to adapt the solution to variations and understand the underlying pattern.

🔍

Pattern Recognition

When to Use

1) Two sorted arrays given, 2) Need median or kth element, 3) Want better than linear merge, 4) Problem hints at binary search or partitioning

Signature Phrases

'median of two sorted arrays''logarithmic time complexity''partition arrays''kth smallest element'

NOT This Pattern When

Merging arrays fully or using simple two-pointer merge without binary search is a different, less efficient pattern.

Similar Problems

Find Kth Smallest Element in Two Sorted Arrays - uses similar partition logicMedian of Sorted Array - simpler median problemKth Smallest Element in a Sorted Matrix - binary search on value or partition

Practice

1. What is the time complexity of the optimal binary search solution for finding the smallest divisor given an array of size n and maximum element max_num?

medium

A. O(n + log max_num)

B. O(n * max_num)

C. O(log n * max_num)

D. O(n log max_num)

Solution

1. Step 1: Identify the binary search iterations

   Binary search runs over the range [1, max_num], so it takes O(log max_num) steps.

2. Step 2: Analyze the feasibility check cost

   Each feasibility check sums over all n elements, costing O(n).

3. Step 3: Combine complexities

   Total time is O(n * log max_num), since feasibility is done each binary search iteration.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Binary search log factor times linear feasibility -> [OK]

Hint: Binary search log factor times linear feasibility check [OK]

Common Mistakes:

• Confusing max_num with n in complexity
• Forgetting feasibility check cost per iteration
• Assuming linear search complexity applies

2. Consider the following buggy code snippet for checking if arrival is possible on time. Which line contains the subtle bug that can cause incorrect feasibility results?

from math import ceil

def can_arrive(dist, hour, speed):
    total_time = 0.0
    for i in range(len(dist)):
        total_time += ceil(dist[i] / speed)
    total_time -= ceil(dist[-1] / speed)  # Adjust last segment
    total_time += dist[-1] / speed
    return total_time <= hour

medium

A. Line 5: total_time += ceil(dist[i] / speed)

B. Line 6: total_time -= ceil(dist[-1] / speed) # Adjust last segment

C. Line 4: for i in range(len(dist))

D. Line 7: total_time += dist[-1] / speed

Solution

1. Step 1: Analyze loop bounds

   The loop iterates over all segments including the last, adding ceil for all, which overestimates time for last segment.

2. Step 2: Identify correct approach

   Only the first n-1 segments should use ceil; the last segment should add exact division time without ceiling.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop should be for i in range(len(dist) - 1) [OK]

Hint: Last segment time must not be ceiled [OK]

Common Mistakes:

• Applying ceil to last segment
• Incorrect loop range including last segment

3. What is the time complexity of the optimal binary search algorithm that finds the single non-duplicate element in a sorted array where every other element appears twice?

medium

A. O(n) because each element is checked at least once

B. O(log n) because the search space halves each iteration based on parity checks

C. O(n log n) due to repeated comparisons and index parity calculations

D. O(1) since only a few elements are compared at each step

Solution

1. Step 1: Identify loop behavior

   The while loop halves the search space each iteration by adjusting low or high based on parity comparisons.

2. Step 2: Confirm complexity

   Halving search space each iteration leads to O(log n) time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search is classic O(log n) [OK]

Hint: Halving search space -> logarithmic time [OK]

Common Mistakes:

• Confusing linear scan with binary search
• Assuming parity checks add extra complexity
• Misreading O(1) as possible for search

4. Suppose the problem is modified so that the traveler can reuse the same speed for multiple trips (i.e., multiple independent journeys with the same speed constraint). Which modification to the binary search approach is necessary to handle this scenario correctly?

hard

A. Perform binary search separately for each trip and take the maximum minimum speed

B. Use a single binary search over speed and check feasibility across all trips combined

C. Switch to a brute force linear search since binary search no longer applies

D. Use dynamic programming to store feasibility states for each trip and speed

Solution

1. Step 1: Understand the reuse scenario

   All trips must be completed at the same speed, so feasibility must be checked collectively.

2. Step 2: Adapt binary search feasibility check

   Perform binary search on speed and verify if all trips can be completed on time at that speed combined.

3. Step 3: Reject separate searches or brute force

   Separate searches ignore the single speed constraint; brute force is inefficient; DP is unnecessary.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Single binary search with combined feasibility check handles reuse [OK]

Hint: Single binary search with combined feasibility check [OK]

Common Mistakes:

• Binary searching each trip separately
• Switching to brute force unnecessarily

5. Suppose you want to compute x^n where n can be a very large 64-bit integer, possibly negative, and you want to avoid recursion and minimize space. Which modification to the iterative fast exponentiation algorithm is necessary to handle this scenario correctly?

hard

A. Switch to a recursive approach with memoization to handle large n efficiently.

B. Use a 64-bit integer type for n and handle negative exponents by converting to positive with care to avoid overflow.

C. Use floating-point arithmetic for n to handle large exponents approximately.

D. Precompute all powers up to n and store them in an array for O(1) queries.

Solution

1. Step 1: Recognize 64-bit integer challenges

   Large 64-bit n can overflow if negated directly (e.g., -2^63).

2. Step 2: Modify handling of negative n

   Use a 64-bit type and convert negative n to positive carefully (e.g., use unsigned or long long) to avoid overflow, then apply iterative fast exponentiation.

3. Step 3: Avoid recursion and extra space

   Iterative approach with careful type handling keeps O(1) space and avoids stack overflow.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Proper integer type and careful negation handle large negative exponents safely [OK]

Hint: Use 64-bit int and careful negation for large negative n [OK]

Common Mistakes:

• Using recursion causing stack overflow
• Using float for exponent causing precision loss
• Precomputing all powers causing huge memory use