PROBLEM DESCRIPTION
Given two sorted arrays arr1[] and arr2[] of sizes n and m in non-decreasing order. Merge them in sorted order without using any extra space. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.
SOLUTION
INITIAL APPROACH (ACCEPTED)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution
{
public static void merge(long arr1[], long arr2[], int n, int m)
{
// end of arr1
int i = n-1;
// start of arr2
int j = 0;
// keep comparing the pairs and swap when necessary
while(i >= 0 && j < m){
// if end element in arr1 is larger than start element at arr2
// we should swap these elements
if(arr1[i] > arr2[j]){
long t = arr1[i];
arr1[i] = arr2[j];
arr2[j] = t;
}
// check next pair
i--;
j++;
}
// we will have the first inital numbers in arr1
// and next elements in arr2
// but they won't be in sorted order
// so sort them explicitly
Arrays.sort(arr1);
Arrays.sort(arr2);
}
}
OPTIMIZATION (GAP ALGORITHM)
Instead of using Arrays.sort(), we can make use of the gap algorithm, which is an optimization of the Shell Sort technique, to merge two arrays in sorted order while swapping the elements directly.
Steps to Implement the Gap Algorithm
Calculate Total Length:
totalLength = n + m(combined length of both arrays).
Initialize the Gap:
- Set the initial gap as
gap = ceil(totalLength / 2). This is calculated as(totalLength / 2 + totalLength % 2)to avoid using floating-point arithmetic.
- Set the initial gap as
Iterate and Compare Elements:
- Initialize two pointers:
left = 0right = gap(start right pointer at the gap distance from the left pointer).
- Initialize two pointers:
Compare and Swap Elements:
- Compare elements at positions
leftandright. If the element atleftis larger than the element atright, swap them. - Move both
leftandrightto the next elements (left++andright++), continuing untilrightis within the bounds of the combined arrays.
- Compare elements at positions
Handle Array Bounds during the above iteration:
- Case 1:
left < nandright < n- Both pointers are in
arr1: Comparearr1[left]witharr1[right].
- Both pointers are in
- Case 2:
left < nandright >= nleftis inarr1andrightis inarr2: Comparearr1[left]witharr2[right - n].
- Case 3:
left >= nandright >= n- Both pointers are in
arr2: Comparearr2[left - n]witharr2[right - n].
- Both pointers are in
- Case 1:
Update Gap:
- Reduce the gap using
gap = gap / 2 + gap % 2to ensure it’s the ceiling of the halved gap. If the gap becomes 1, make sure to avoid infinite loops.
- Reduce the gap using
Repeat Until Gap is Zero:
- Continue this process, updating the gap and iterating through the arrays until the gap is zero.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution
{
//Function to merge the arrays.
public static void merge(long arr1[], long arr2[], int n, int m)
{
// length of combined array
long total = n + m;
// this is equivalent of ceil(total/2)
int gap = (int) total/2 + (int) total%2;
while(gap > 0){
// init:
// left will start from index 0
// right will start from left + gap
int left = 0;
int right = gap;
// while right is within bounds
while(right < n + m){
// left in arr1 and right in arr2
if(left < n && right >= n){
swapIfGreater(arr1, arr2, left, right-n);
// both in arr2 (if left is on arr2, right has to be on arr2)
}else if(left >= n){
swapIfGreater(arr2, arr2, left-n, right-n);
// both are in arr1
}else{
swapIfGreater(arr1, arr1, left, right);
}
left++;
right++;
}
// if gap is 1, then ceil of (1/2) will be again 1 and it will cause infinite loop
// so we break if gap reaches 1
if(gap == 1)
break;
// reduce gap by half
gap = gap/2 + gap%2;
}
}
// swap the elements at position i in arr1 and position j in arr2, if arr1[i] > arr2[j]
public static void swapIfGreater(long[] arr1, long[] arr2, int i, int j){
if(arr1[i] > arr2[j]){
long t = arr1[i];
arr1[i] = arr2[j];
arr2[j] = t;
}
}
}