Let us go through a handful of problems that relate to sorting.
If the arrays (A1 (with M elements) and A2 (with N elements)) are sorted, and we need to find intersection (elements that occur in both) of these two arrays. We can assume that element in the result must be unique.
Example: Input: A1 = [1,2,3], A2 = [3,4] Output: [3]
There are several ways to go about doing this problem:
It is important to consider the scale of M and N before we decide on which one to go with. Here are some observations:
With that, here is how an algorithm when arrays are sorted works and it follows the fist case of walking the two arrays using two pointers:
public int intersection_two_sorted_array(int[] A1, int[] A2) {
int N = A1.length;
int M = A2.length;
HashSet<Integer> resultSet = new HashSet<>();
//Here, i is pointing to the first array i.e A1 and j is pointing to second array i.e. A2
int i = 0, j = 0;
while (i < N && j < M) {
if (A1[i] < A2[j]) {
i++;
} else if (A1[i] > A2[j]) {
j++;
} else if (A1[i] == A2[j]) {
resultSet.add(A1[i]);
i++;
j++;
}
}
return resultSet;
}
What happens if the arrays are not sorted? We can either sort the two array and apply the above approach. A more efficient method might be to use a set.
There are several problems that focus on sorting elements in an array when the total number of unique elements in the array is 3. We can use Dutch National flag approach to sort the array in a single pass and in an O(N) time-complexity. For example, an array of elements that consist of only 0, 1, and 2 can be done efficiently using dutch sort; the values (0, 1, or 2) do not matter as long as all elements are of two unique types. In this case, the goal is to sort this array in such a way that all the 0s appear first, followed by all the 1s, and then all the 2s. This style of sorting was formulated by Dutch Scientist Edgar Dijkstra (yep, the same scientist who invented Dijkstra's algorithm!).
We can also have a simplified variant that asks to sort an array that consists of only two unique values.
We can use the same technique to also sort elements in an array when the unique values are not necessarily of 2 or 3 but their types are 2 or 3. For example, we can use this technique to sort arrays such that we have all even numbers appear first in the array followed by all odd numbers. There is no need to sort even numbers among themselves.
Given an array nums that consists of values 0, 1, and 2, we need to sort them such that all the 0s appear first, followed by all the 1s, and then all the 2s.
To do that, we can consider variables lo, mid, and hi such that
It is easy to think of the first three ranges as invariants of the array -- the first range always has 0s, the second range always has 1s and the third range always as 2.
To do that, we follow the following approach:
Here is how the algorithm works:
public int dutch_solution_with_3_values(int[] nums) {
int lo = 0, mid = 0, hi = nums.length - 1;
while (mid <= hi) {
if (nums[mid] == 0) { // if current is 0, then swap it with the lo
nums[mid] = nums[lo];
nums[lo] = 0;
mid++; lo++;
} else if (nums[mid] == 1) {
mid++;
} else { // nums[mid] equals 2.
nums[mid] = nums[hi];
nums[hi] = 2;
hi--;
}
}
}
Once again, an easier way to solve the above problem is simply count the number of 0s, 1s, and 2s and then add those many 0s at the start, followed by all 1s, and followed by all 2s. But, this requires doing two-passes on the array. Further, this would not work if we are asked to sort by element types and not values of elements. For example, if we have an array that consist of even numbers, multiples of 10, and odd numbers, and we are asked to re-arrange them such that we have all multiples of 10, followed by all even numbers (the ones that are not multiple of 10), and odd numbers, then we cannot use the count method.
Given an array nums that consists of values 0 and 1, we need to sort them such that all the 0s appear first, followed by all the 1s.
We now have two colors which is a simpler variant. In this case, we would only have 3 ranges: To do that, we can consider two variables lo and hi such that
In this case, the invariant are: a[0..lo] are all 0s and a[hi..N-1] are all 1s; a[lo..hi-1] are unknown.
Here is how the algorithm works:
Here is how the algorithm works:
public int dutch_solution_with_2_values(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
if (nums[lo] == 0) {
lo++;
} else { // nums[lo] equals 1.
nums[lo] = nums[hi];
nums[hi] = 1;
hi--;
}
}
}
Once again, an easier way to solve the above problem is simply count the number of 0s and 1s and add those many 0s at the start, followed by all 1s. Once again, this requires doing two-passes on the array and this method would not work if we are asked to sort by element types and not values of elements.
Given two arrays A1 and A2, we need to sort the A1 such that the relative ordering of items in A1 are same as that of A2. Elements that don't appear in A2 should be placed at the end of A1 in ascending order. We can assume that the following two conditions hold: all elements of A2 are distinct and all elements in A2 are also in A1.
Example: Input: A1 = [3, 4, 3, 4, 2, 1, 1, 1, 2, 3, 10, 0], A2 = [0, 2,4,3] Output: [0, 2, 2, 4, 4, 3, 3, 3, 1, 1, 1, 10]
This problem is a cool example of sorting. The goal here is to add a comparator function when sorting that follows a set of rules. We can start by adding all elements of A2 in a map with value as the key and index as the value -- we do this so that we can use the index (after looking up in the map with the the value of an element from A1) to determine which of the two elements should appears first.
Here is how we can write the comparator function:
We provide the code below in Java. Note that in Java, for Arrays.sort() to work with a lambda-based comparator, the array must NOT be of primitives. The only Arrays.sort() that works with primitive (like int[]) is the Arrays.sort(arr) itself. So, we have to convert it to Integer[] and back.
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public int[] relativeSortArray(int[] A1, int[] A2) {
for (int i = 0; i < A2.length; i++)
map.put(A2[i], i);
Integer[] arr = Arrays.stream(A1).boxed().toArray(Integer[]::new);
Arrays.sort(arr, (a, b) -> {
if (map.containsKey(a) && map.containsKey(b))
return map.get(a)-map.get(b);
else if (map.containsKey(a))
return -1;
else if (map.containsKey(b))
return 1;
else return (a-b);
});
return Arrays.stream(arr).mapToInt(j->j).toArray();
}
}