To Find the Nth Number in the Merged and Sorted Lists of Given Ranges.

Brute Force Approach-

• We will be taking an array and inserting all the elements of every range.
• If the array contains any duplicate element then remove it.
• Sort the array.
• Find the nth element.
• This brute force will take nlogn time if  N=largestnumber - smallestnumber where largestnumber is the maximum number from the ranges given and the smallestnumber is the minimum from the ranges given.
   

Implementation

We will be using the binary search algorithm over the answer for this problem.

A binary search algorithm divides the sorted array into two halves by calculating the middle element.

We will store the minimum element from the Left array and the maximum element from the Right array.

Binary search will work from a range of minimum elements to maximum elements.

class Solution {

   public static long Nth(int[] Left, int[] Right, int n) {
      // Store the size of the ranges
      int K = Left.length;

     // Calculate the max and min values
     long min = 2000000000, max = -2000000000;
     for (int i = 0; i < K; i++) {
         if (Left[i] < min)
           min = Left[i];
         if (Right[i] > max)
           max = Right[i];
     }

     // Binary search
     while (min <= max) {
        long mid = (min + max) / 2;
        long t = 0;

    for (int i = 0; i < K; i++) {
       if (mid >= Left[i]) {
          if (mid <= Right[i]) {
             t += mid - Left[i] + 1;
          } else {
             t += Right[i] - Left[i] + 1;
        }
     }
  }


   if (t > n) {
     max = mid - 1;
   } else {
     min = mid + 1;
    }
  }
  return min;
}

// Main function
public static void main(String args[]) {
   int[] Left = { 1, 4 }, Right = { 4, 5 };
   int N = 3;
   System.out.println(Nth(Left, Right, N));
 }

}

You can also try this code with Online Java Compiler

Run Code

Output

4

Analysis of Complexity

Time Complexity: The time complexity to solve this problem is O(N*log(max-min)), where min and max are the integers stored from the left and the right array, respectively.

Space Complexity: The auxiliary space is O(n).

FAQs

1. What is the Time complexity of this problem?
   The time complexity to solve this problem is O(N*log(max-min)), where min and max are the integers stored from the left and the right array, respectively.
    
2. What do you mean by greedy approach?
   A greedy algorithm is used in optimization problems, attempts to find the optimal solution to solve the entire problem.

Key Takeaways

This blog has covered the problem based on Sorting, where we have to find the Nth number in the sorted and merged list of given ranges. We have covered this problem by finding the min and max element from the left and right array, respectively, and applying the Binary search algorithm until max>=min.

Recommended Problem - Merge K Sorted Arrays

You can also view Top Problems Related To Sorting Based Problems.

Along with this, you can use Coding Ninjas Studio for various DSA questions typically asked in interviews for more practice.