I was solving this problem.
Given two sorted arrays arr1[] and arr2[] in non-decreasing order with size n and m. The task is to merge the two sorted arrays into one sorted array (in non-decreasing order).
Note: Expected time complexity is O((n+m) log(n+m)). DO NOT use extra space.
The below code has the time complexity of O(n log m). Still, it gives me a timeout error.
Where am I going wrong?
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t-- > 0){
StringTokenizer st = new StringTokenizer(br.readLine());
int len1 = Integer.parseInt(st.nextToken());
int len2 = Integer.parseInt(st.nextToken());
int[] nums1 = new int[len1];
int[] nums2 = new int[len2];
st = new StringTokenizer(br.readLine());
for(int i = 0; i<len1; i++)
nums1[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i = 0; i<len2; i++)
nums2[i] = Integer.parseInt(st.nextToken());
int temp;
for(int i =0; i<len1; i++){
if (nums1[i] > nums2[0]){
temp = nums1[i];
nums1[i] = nums2[0];
nums2[0] = temp;
Heapify(nums2,0,len2);
}
}
for(int i = 0; i<len1; i++)
System.out.print(nums1[i]+" ");
Arrays.sort(nums2);
for(int i = 0; i<len2; i++)
System.out.print(nums2[i]+" ");
System.out.println();
}
}
static void Heapify(int[] nums, int i, int len){
int l = 2 * i+1;
int r = 2 * i + 2;
int smallest = i;
if (l < len && nums[l] < nums[i] ){
smallest = l;
}
if (r < len && nums[r] < nums[smallest] ){
smallest = r;
}
if (smallest != i){
int temp = nums[i];
nums[i] = nums[smallest];
nums[smallest] = temp;
Heapify(nums,smallest,len);
}
}
}
The website has some problems. Submitted same solution for many times.
The timeout was due to there were a lot of read and write operations involved.
You optimised it for read operations using BufferedReader.
I optimised it for write operations using BufferedWriter in the following implementation:
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t-- > 0){
StringTokenizer st = new StringTokenizer(br.readLine());
int len1 = Integer.parseInt(st.nextToken());
int len2 = Integer.parseInt(st.nextToken());
int[] nums1 = new int[len1];
int[] nums2 = new int[len2];
st = new StringTokenizer(br.readLine());
for(int i = 0; i<len1; i++)
nums1[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i = 0; i<len2; i++)
nums2[i] = Integer.parseInt(st.nextToken());
int temp;
for(int i =0; i<len1; i++){
if (nums1[i] > nums2[0]){
temp = nums1[i];
nums1[i] = nums2[0];
nums2[0] = temp;
Heapify(nums2,0,len2);
}
}
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i<len1; i++)
log.write(nums1[i]+" ");
Arrays.sort(nums2);
for(int i = 0; i<len2; i++)
log.write(nums2[i]+" ");
log.write("\n");
log.flush();
}
}
static void Heapify(int[] nums, int i, int len){
int l = 2 * i+1;
int r = 2 * i + 2;
int smallest = i;
if (l < len && nums[l] < nums[i] ){
smallest = l;
}
if (r < len && nums[r] < nums[smallest] ){
smallest = r;
}
if (smallest != i){
int temp = nums[i];
nums[i] = nums[smallest];
nums[smallest] = temp;
Heapify(nums,smallest,len);
}
}
}
The Geeks for Geeks verdict is Accepted for the above code:
PS: Try to submit this same solution for multiple times. You will get correct answer as verdict.