Leetcode 4. Median of Two Sorted Arrays

 4. Median of Two Sorted Arrays

Hard

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)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

To solve this problem efficiently with the time complexity requirement of O(log(m+n)), we need to leverage a binary search approach.

Problem Overview:

• You are given two sorted arrays, nums1 and nums2.
• The task is to find the median of the combined sorted array without actually merging the arrays, as that would take O(m + n) time, which doesn't meet the time complexity requirement.
• The median is:
  • If the combined array length is odd, the median is the middle element.
  • If the combined array length is even, the median is the average of the two middle elements.

Approach:

We can solve this problem using binary search:

• We will binary search on the smaller of the two arrays (nums1 or nums2) to partition both arrays such that:
  • The left half contains the first half of the merged array.
  • The right half contains the second half of the merged array.
• The key observation is to balance the sizes of the two partitions (left and right).
• The median will be derived from the largest element in the left partition and the smallest element in the right partition.

Steps:

1. Partitioning the arrays: Partition the smaller array into two halves, and based on this, calculate the corresponding partition in the larger array.
2. Binary Search: Perform a binary search on the smaller array (nums1), and for each partition point i, determine the corresponding partition j in nums2.
3. Check the partition validity: Ensure that:
   • nums1[i-1] <= nums2[j] (The left part of nums1 is less than or equal to the right part of nums2)
   • nums2[j-1] <= nums1[i] (The left part of nums2 is less than or equal to the right part of nums1)
4. Compute the median:
   • If the total number of elements is odd, the median is the maximum of the left side.
   • If the total number of elements is even, the median is the average of the maximum of the left side and the minimum of the right side.

Code Implementation:

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.Length > nums2.Length) {
            var temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.Length;
        int n = nums2.Length;
        int left = 0, right = m;
        
        while (left <= right) {
            int i = left + (right - left) / 2; // partition index for nums1
            int j = (m + n + 1) / 2 - i; // partition index for nums2

            // Check if partition is valid
            int maxLeft1 = (i == 0) ? int.MinValue : nums1[i - 1];
            int minRight1 = (i == m) ? int.MaxValue : nums1[i];
            int maxLeft2 = (j == 0) ? int.MinValue : nums2[j - 1];
            int minRight2 = (j == n) ? int.MaxValue : nums2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // Correct partitioning found
                if ((m + n) % 2 == 0) {
                    // Even total length: average of max of left and min of right
                    return (Math.Max(maxLeft1, maxLeft2) + Math.Min(minRight1, minRight2)) / 2.0;
                } else {
                    // Odd total length: max of left part
                    return Math.Max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                // We need to move the partition in nums1 to the left
                right = i - 1;
            } else {
                // We need to move the partition in nums1 to the right
                left = i + 1;
            }
        }

        // If no valid partition is found, return 0 (this shouldn't happen with valid input)
        return 0;
    }
}

Explanation of Code:

1. Initial Check for Array Sizes: We ensure that nums1 is the smaller array for efficiency. This allows us to perform binary search on the smaller array, reducing the number of elements we need to check.
2. Binary Search: We perform a binary search on the smaller array nums1. For each partition in nums1, we calculate the corresponding partition in nums2 to ensure the combined left part has as many elements as the right part.
3. Partition Validation: We check if the partition is valid:
   • The largest element of the left part of nums1 (maxLeft1) should be less than or equal to the smallest element of the right part of nums2 (minRight2), and vice versa for nums2 and nums1.
4. Median Calculation:
   • If the combined number of elements is even, the median is the average of the maximum of the left part and the minimum of the right part.
   • If the combined number of elements is odd, the median is the maximum of the left part.

Time Complexity:

• Binary Search: We perform binary search on the smaller array, so the time complexity is O(log(min(m, n))), where m and n are the lengths of the two arrays.

• Overall Time Complexity: Since we are only doing binary search on the smaller array, the time complexity is O(log(min(m, n))), which is efficient for this problem.

Example Walkthrough:

Example 1:

Input:

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

• The merged array is [1, 2, 3].
• The median is 2.

Output:

2.00000

Example 2:

Input:

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

• The merged array is [1, 2, 3, 4].
• The median is (2 + 3) / 2 = 2.5.

Output:

2.50000

This approach satisfies the problem's constraints and efficiently finds the median in O(log(min(m, n))) time.

For the problem "Median of Two Sorted Arrays," we can explore at least three different approaches to solving it, each with varying levels of time complexity and space complexity. Here's a breakdown of three different approaches:

---

1. Binary Search Approach (Optimal)

This is the optimal approach and follows the hint to use binary search on the smaller array. It achieves the required time complexity of O(log(min(m, n))).

Explanation:

• The idea is to partition both arrays into two halves.
• The left half of the combined array contains the same number of elements as the right half.
• Perform binary search on the smaller array, and for each partition in that array, calculate the corresponding partition in the larger array.
• After the partitioning, check whether the left and right parts of the arrays satisfy the conditions for being a valid median split.

Code:

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.Length > nums2.Length) {
            var temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.Length;
        int n = nums2.Length;
        int left = 0, right = m;

        while (left <= right) {
            int i = left + (right - left) / 2;
            int j = (m + n + 1) / 2 - i;

            int maxLeft1 = (i == 0) ? int.MinValue : nums1[i - 1];
            int minRight1 = (i == m) ? int.MaxValue : nums1[i];
            int maxLeft2 = (j == 0) ? int.MinValue : nums2[j - 1];
            int minRight2 = (j == n) ? int.MaxValue : nums2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((m + n) % 2 == 0) {
                    return (Math.Max(maxLeft1, maxLeft2) + Math.Min(minRight1, minRight2)) / 2.0;
                } else {
                    return Math.Max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }

        return 0;
    }
}

Time Complexity:

• Time Complexity: O(log(min(m, n)))
• Space Complexity: O(1)

---

2. Merge and Find Median (Brute Force)

In this approach, we merge the two sorted arrays into one and then find the median of the merged array. Although this approach is easy to implement, it doesn't meet the time complexity requirement of O(log(m + n)) and has a higher time complexity.

Explanation:

• Merge the two sorted arrays into a single sorted array.
• Once the arrays are merged, calculate the median.
• If the combined array length is even, the median is the average of the two middle elements.
• If the length is odd, the median is the middle element.

Code:

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.Length + nums2.Length];
        int i = 0, j = 0, k = 0;

        while (i < nums1.Length && j < nums2.Length) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }

        while (i < nums1.Length) {
            merged[k++] = nums1[i++];
        }

        while (j < nums2.Length) {
            merged[k++] = nums2[j++];
        }

        int mid = merged.Length / 2;
        if (merged.Length % 2 == 0) {
            return (merged[mid - 1] + merged[mid]) / 2.0;
        } else {
            return merged[mid];
        }
    }
}

Time Complexity:

• Time Complexity: O(m + n) (Merging both arrays)
• Space Complexity: O(m + n) (Space for the merged array)

---

3. Two Pointers Approach (Optimal for Merge)

This approach is similar to the merge step in the previous approach but avoids explicitly creating a new merged array. Instead, it uses two pointers to traverse through both arrays and find the median directly.

Explanation:

• Use two pointers, one for each array (nums1 and nums2).
• Traverse through both arrays simultaneously and keep track of the current merged index.
• Once you’ve traversed half of the total number of elements, compute the median based on the merged data at that point.

Code:

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.Length;
        int n = nums2.Length;
        int totalLen = m + n;

        int i = 0, j = 0;
        int prev = -1, current = -1;

        for (int count = 0; count <= totalLen / 2; count++) {
            prev = current;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                current = nums1[i++];
            } else {
                current = nums2[j++];
            }
        }

        if (totalLen % 2 == 0) {
            return (prev + current) / 2.0;
        } else {
            return current;
        }
    }
}

Time Complexity:

• Time Complexity: O(m + n) (Linear traversal through both arrays)
• Space Complexity: O(1) (Constant space usage)

---

Comparison of Approaches:

Approach	Time Complexity	Space Complexity	Pros	Cons
Binary Search Approach	O(log(min(m, n)))	O(1)	Optimal, efficient for large arrays	More complex to understand and implement
Merge and Find Median	O(m + n)	O(m + n)	Simple to understand and implement	Not optimal for large arrays
Two Pointers Approach	O(m + n)	O(1)	Simple, avoids extra space usage	Less efficient than binary search approach

---

Conclusion:

• The Binary Search Approach is the most efficient, meeting the time complexity requirement of O(log(min(m, n))).
• The Merge and Find Median Approach is the most intuitive but has a higher time complexity of O(m + n) and space complexity of O(m + n).
• The Two Pointers Approach is a good middle ground with a time complexity of O(m + n) but is more space efficient compared to the merge approach.

You can choose the approach based on the problem constraints and efficiency needs.

Leetcode 1335. Minimum Difficulty of a Job Schedule

 1335. Minimum Difficulty of a Job Schedule

Hard

, Dynamic Programming

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day.

You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

 

Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

 

Constraints:

• 1 <= jobDifficulty.length <= 300
• 0 <= jobDifficulty[i] <= 1000
• 1 <= d <= 10

To solve this problem efficiently using dynamic programming (DP), we need to approach it by dividing the list of jobs into d non-empty subarrays. The problem is about finding the minimum difficulty schedule, where the difficulty of each subarray is the maximum difficulty of the jobs scheduled on that day.

Problem Breakdown:

• We are tasked with dividing the jobs into d groups (or days). Each group must contain at least one job.
• The difficulty of a day is the maximum difficulty of any job assigned to that day, and the total difficulty of the schedule is the sum of the maximum difficulties across all days.

Approach:

Dynamic Programming Approach:

We'll use a 2D DP array dp[i][j] where:

• i represents the number of jobs considered.
• j represents the number of days used to schedule the first i jobs.
• dp[i][j] will store the minimum difficulty for scheduling the first i jobs into j days.

Steps:

1. Base Case:

   • dp[0][0] = 0: No jobs, no days, zero difficulty.
   • dp[i][0] = infinity for i > 0: Impossible to schedule jobs with zero days.
   • dp[i][j] = infinity initially for all other values, indicating impossible cases.

2. DP Transition:

   • For each possible number of days j, and for each possible last job i in the partition, we calculate the difficulty of the current day. This is done by considering all jobs from some earlier job k to i as part of the last day and computing the maximum difficulty for that day.
   • For each partition from k to i, update dp[i][j] as: $$dp[i][j] = \min(dp[i][j], dp[k][j-1] + \text{max difficulty from job } k \text{ to job } i)$$
   • This way, we try to partition the jobs into j groups, calculating the difficulty of each partition.

3. Final Answer:

   • After filling the DP table, the result will be in dp[n][d] where n is the total number of jobs and d is the number of days.

4. Edge Case:

   • If the number of jobs is less than the number of days (n < d), return -1 because it's impossible to schedule jobs.

Code Implementation:

public class Solution {
    public int MinDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.Length;
        
        // Edge case: If there are fewer jobs than days, return -1
        if (n < d) return -1;
        
        // DP array where dp[i][j] represents the minimum difficulty of scheduling first i jobs into j days
        int[,] dp = new int[n + 1, d + 1];
        
        // Initialize the dp array with a large number (int.MaxValue)
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= d; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        
        // Base case: 0 jobs and 0 days results in 0 difficulty
        dp[0, 0] = 0;
        
        // Iterate over number of days
        for (int j = 1; j <= d; j++) {
            // Iterate over number of jobs to be scheduled
            for (int i = j; i <= n; i++) { // Need at least 'j' jobs to schedule 'j' days
                int maxJobDifficulty = 0;
                // Try partitioning the jobs in different ways
                for (int k = i - 1; k >= j - 1; k--) {
                    maxJobDifficulty = Math.Max(maxJobDifficulty, jobDifficulty[k]);
                    dp[i, j] = Math.Min(dp[i, j], dp[k, j - 1] + maxJobDifficulty);
                }
            }
        }
        
        // The answer is the minimum difficulty of scheduling all jobs in 'd' days
        return dp[n, d];
    }
}

Explanation:

1. DP Table Initialization:

   • We initialize a DP table dp[n+1][d+1] with a very large value (int.MaxValue) to indicate that a schedule is not possible for that configuration. We also set the base case dp[0][0] = 0, as there is no difficulty when there are no jobs and no days.

2. DP Transitions:

   • We iterate over each possible day count (j), and for each day, we check how to split the first i jobs into j groups. We consider each possible partition from k to i, where k is the job index before the current partition.
   • For each partition, we compute the maximum job difficulty for the jobs assigned to that day and add it to the previous day's difficulty (dp[k][j-1]).

3. Final Answer:

   • Once all the DP table entries are filled, dp[n][d] holds the minimum possible difficulty for scheduling all n jobs into d days.

Time Complexity:

• Time Complexity: O(n * n * d). We have three nested loops:
  • The outer loop runs d times (for the days).
  • The second loop runs n times (for the jobs).
  • The innermost loop runs up to n times (to check all possible previous jobs in the current partition).
• Space Complexity: O(n * d) for the DP table.

Example Walkthrough:

Example 1:

Input:

jobDifficulty = [6, 5, 4, 3, 2, 1], d = 2

Output:

7

• Day 1: Jobs [6, 5, 4, 3, 2] (max difficulty = 6).
• Day 2: Jobs [1] (max difficulty = 1).
• Total difficulty = 6 + 1 = 7.

Example 2:

Input:

jobDifficulty = [9, 9, 9], d = 4

Output:

-1

• More days than jobs, so it's impossible to schedule.

Example 3:

Input:

jobDifficulty = [1, 1, 1], d = 3

Output:

3

• Each day gets one job, and the difficulty of each day is 1.
• Total difficulty = 1 + 1 + 1 = 3.

This dynamic programming approach ensures that we explore all valid job partitions while optimizing for the minimum difficulty. Let me know if you have more questions!